Generate a Reverse Polish Stack

[Allan]

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;


[jwilt]

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]

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

[Allan]

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]

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;