Generate a Reverse Polish Stack
Had to implement this for an internal product but then thought it could be useful for others:
- Code: Select all
EXPORT GenerateReversePolishStack(STRING Text) := FUNCTION
/*
Generates A reverse Polich Stack from text with operands of the form:
operand "qualifier"
And the operators (in order of precedence): NOT, AND, OR or XOR
Brackets can be used to enforce a different precedence.
e.g.
A"q1 with q4" AND (B"q2" OR C"q3")
Generates output of the form:
1 S7037 A q1 with q4
1 S6142 B q2
1 S1873 C q3
2 S8633 S6142 S1873
3 S7435 S7037 S8633
Returns an empty set if there is a syntax error.
*/
infile := DATASET(ROW(transform({ string line }, self.line := Text)));
ActionType := ENUM(UNSIGNED1,None,LogicalOr,LogicalAnd,LogicalXor,LogicalNot);
Symbol := RECORD
ActionType Action;
STRING5 id;
STRING key;
STRING Qualifier;
END;
Production := RECORD
DATASET(Symbol) itm;
END;
TYPEOF(Symbol.id) GetID := 'S'+INTFORMAT(HASH32(STD.System.Util.GetUniqueInteger(),RANDOM())%10000,SIZEOF(Symbol.id)-1,1);
PRULE := RULE TYPE (Production);
PATTERN ws := PATTERN('[[:space:]]');
TOKEN wordpat := PATTERN('[A-Za-z][A-Za-z0-9_]*');
PATTERN firstchar := PATTERN('[[:alnum:]\'*&%!~#;:@?<>=+\\-_(){},.[\\]]');
PATTERN subsequent := firstchar | ws;
PATTERN anything := firstchar+subsequent*;
PATTERN quotechar := '"';
TOKEN quotedword := quotechar anything quotechar;
PRULE forwardExpr := USE(Production, 'ExpressionRule');
PRULE op
:= wordpat quotedword TRANSFORM(Production,
SELF.itm := ROW({ActionType.None,GetID,$1,$2[2..length($2)-1]},Symbol);
)
| '(' forwardExpr ')'
| 'NOT' wordpat quotedword TRANSFORM(Production,
SELF.itm := ROW({ActionType.LogicalNot,GetID,$2,$3[2..length($3)-1]},Symbol);
)
| 'NOT' '(' forwardExpr ')' TRANSFORM(Production,
SELF.itm := $3.itm & ROW({ActionType.LogicalNot,GetID,$3.itm[COUNT($3.itm)].id,''},Symbol);
)
;
PRULE factor
:= op
| SELF 'AND' op TRANSFORM(Production,
SELF.itm := $1.itm & $3.itm & ROW({ActionType.LogicalAnd,GetID,$1.itm[COUNT($1.itm)].id,$3.itm[COUNT($3.itm)].id},Symbol)
)
;
PRULE term
:= factor
| SELF 'OR' factor TRANSFORM(Production,
SELF.itm := $1.itm & $3.itm & ROW({ActionType.LogicalOr ,GetID,$1.itm[COUNT($1.itm)].id,$3.itm[COUNT($3.itm)].id},Symbol)
)
| SELF 'XOR' factor TRANSFORM(Production,
SELF.itm := $1.itm & $3.itm & ROW({ActionType.LogicalXor,GetID,$1.itm[COUNT($1.itm)].id,$3.itm[COUNT($3.itm)].id},Symbol)
)
;
PRULE expr
:= term : DEFINE ('ExpressionRule');
p1 := PARSE(infile,line,expr,TRANSFORM(Production,SELF := $1),FIRST,WHOLE,SKIP(ws+),NOCASE,PARSE);
n1 := NORMALIZE(p1,LEFT.itm,TRANSFORM(Symbol,SELF := RIGHT)) : INDEPENDENT;
RETURN n1;
END;
- Allan
- Posts: 444
- Joined: Sat Oct 01, 2011 7:26 pm
Great post. Thanks, Allan.
Allan's algorithm is using this technique to generate a unique ID for tokens:
TYPEOF(Symbol.id) GetID := 'S'+INTFORMAT(HASH32(STD.System.Util.GetUniqueInteger(),RANDOM())%10000,SIZEOF(Symbol.id)-1,1);
Allan - did this work sufficiently for your purposes?
Others - is there another way to do this? I.e., to mark each token found with a unique ID.
Thanks.
Allan's algorithm is using this technique to generate a unique ID for tokens:
TYPEOF(Symbol.id) GetID := 'S'+INTFORMAT(HASH32(STD.System.Util.GetUniqueInteger(),RANDOM())%10000,SIZEOF(Symbol.id)-1,1);
Allan - did this work sufficiently for your purposes?
Others - is there another way to do this? I.e., to mark each token found with a unique ID.
Thanks.
- jwilt
- Posts: 56
- Joined: Wed Feb 27, 2013 7:46 pm
Hi jwit,
Yes this is working fine for me/us. The MOD 10000 has not throw up a clash and generated non-unique id's. (so far).
If you're concerned you could always increase the MOD to reduce the likelihood further, but you do have a valid point. Perhaps a datetime component could be added to the construction to generate Id's of the form S20170101084522_4976, but even then there is a very small chance of a clash. I would like to know of a fall proof way of generating unique ID's. So I'll watch this space.
Cheers
Allan
Yes this is working fine for me/us. The MOD 10000 has not throw up a clash and generated non-unique id's. (so far).
If you're concerned you could always increase the MOD to reduce the likelihood further, but you do have a valid point. Perhaps a datetime component could be added to the construction to generate Id's of the form S20170101084522_4976, but even then there is a very small chance of a clash. I would like to know of a fall proof way of generating unique ID's. So I'll watch this space.
Cheers
Allan
- Allan
- Posts: 444
- Joined: Sat Oct 01, 2011 7:26 pm
There is now STD.System.Util.GetUniqueInteger() which will eliminate any possibility of a clash in generated Identifier names.
- Code: Select all
IMPORT STD;
RID := {UNSIGNED8 id};
RID GetId(RID L) := TRANSFORM
SELF.id := STD.System.Util.GetUniqueInteger();
END;
n := NORMALIZE(DATASET([{0}],RID),2000,GetId(LEFT));
RT := RECORD
UNSIGNED8 id := n.id;
UNSIGNED8 cnt := COUNT(GROUP);
END;
TABLE(n,RT,id)(cnt > 1);
- Allan
- Posts: 444
- Joined: Sat Oct 01, 2011 7:26 pm
From comments back, this version replaces the output numeric operators with readable text:
- Code: Select all
EXPORT GenerateReversePolishStack(STRING Text) := FUNCTION
/*
Generates A reverse Polich Stack from text with operands of the form:
operand "qualifier"
And the operators (in order of precedence): NOT, AND, OR or XOR
Brackets can be used to enforce a different precedence.
e.g.
A"q1 with q4" AND (B"q2" OR C"q3")
Generates output of the form:
1 S7037 A q1 with q4
1 S6142 B q2
1 S1873 C q3
2 S8633 S6142 S1873
3 S7435 S7037 S8633
Returns an empty set if there is a syntax error.
*/
infile := DATASET(ROW(transform({ string line }, self.line := Text)));
ActionType := ENUM(UNSIGNED1,None,LogicalOr,LogicalAnd,LogicalXor,LogicalNot);
SET OF STRING ActionText := ['','Or','And','Xor','Not'];
Symbol := RECORD
STRING Action;
STRING5 id;
STRING key;
STRING Qualifier;
END;
Production := RECORD
DATASET(Symbol) itm;
END;
TYPEOF(Symbol.id) GetID := 'S'+INTFORMAT(HASH32(STD.System.Util.GetUniqueInteger(),RANDOM())%10000,SIZEOF(Symbol.id)-1,1);
PRULE := RULE TYPE (Production);
PATTERN ws := PATTERN('[[:space:]]');
TOKEN wordpat := PATTERN('[A-Za-z][A-Za-z0-9_]*');
PATTERN firstchar := PATTERN('[[:alnum:]\'*&%!~#;:@?<>=+\\-_(){},.[\\]]');
PATTERN subsequent := firstchar | ws;
PATTERN anything := firstchar+subsequent*;
PATTERN quotechar := '"';
TOKEN quotedword := quotechar anything quotechar;
PRULE forwardExpr := USE(Production, 'ExpressionRule');
PRULE op
:= wordpat quotedword TRANSFORM(Production,
SELF.itm := ROW({ActionText[ActionType.None],GetID,$1,$2[2..length($2)-1]},Symbol);
)
| '(' forwardExpr ')'
| 'NOT' wordpat quotedword TRANSFORM(Production,
SELF.itm := ROW({ActionText[ActionType.LogicalNot],GetID,$2,$3[2..length($3)-1]},Symbol);
)
| 'NOT' '(' forwardExpr ')' TRANSFORM(Production,
SELF.itm := $3.itm & ROW({ActionText[ActionType.LogicalNot],GetID,$3.itm[COUNT($3.itm)].id,''},Symbol);
)
;
PRULE factor
:= op
| SELF 'AND' op TRANSFORM(Production,
SELF.itm := $1.itm & $3.itm & ROW({ActionText[ActionType.LogicalAnd],GetID,$1.itm[COUNT($1.itm)].id,$3.itm[COUNT($3.itm)].id},Symbol)
)
;
PRULE term
:= factor
| SELF 'OR' factor TRANSFORM(Production,
SELF.itm := $1.itm & $3.itm & ROW({ActionText[ActionType.LogicalOr] ,GetID,$1.itm[COUNT($1.itm)].id,$3.itm[COUNT($3.itm)].id},Symbol)
)
| SELF 'XOR' factor TRANSFORM(Production,
SELF.itm := $1.itm & $3.itm & ROW({ActionText[ActionType.LogicalXor],GetID,$1.itm[COUNT($1.itm)].id,$3.itm[COUNT($3.itm)].id},Symbol)
)
;
PRULE expr
:= term : DEFINE ('ExpressionRule');
p1 := PARSE(infile,line,expr,TRANSFORM(Production,SELF := $1),FIRST,WHOLE,SKIP(ws+),NOCASE,PARSE);
n1 := NORMALIZE(p1,LEFT.itm,TRANSFORM(Symbol,SELF := RIGHT)) : INDEPENDENT;
RETURN n1;
END;
- Allan
- Posts: 444
- Joined: Sat Oct 01, 2011 7:26 pm
5 posts
• Page 1 of 1
Who is online
Users browsing this forum: No registered users and 1 guest