aptk.oprec - Operation Precedence ParserΒΆ

Operation precedence parsers are intended to parse expressions, where never is a sequence of non-terminals. Usually you will use it to parse (mathematical) expressions.

You can invoke OperationPrecedenceParser into your grammar by using:

:args-of OPTABLE string capturing non-capturing raw
         => aptk.oprec.OperatorPrecedenceParser

Then you can create rules like this:

my_rule_name1 := <OPTABLE{
                    :rule T <.term>
                    ...
                    }>

my_rule_name2 := <OPTABLE{
                    :rule T <.term2>
                    :rule W ""
                    :rule E
                    ...
                    }>

Every OPTABLE invokation creates a new rule.

In any Grammar-descending grammar this is already done for you and operation precedence is accessible via rule EXPR:

:grammar operation-precedence-parser-tests

expr  := <EXPR{
           :flags with-ops

           :op L E+E
       }>

You have to define a <term>, such that a term, which is the only non-terminal-rule in expressions, can be parsed:

term       := <number> | <ident>

Expression above parses for example following expressions:

<expr> ~~ 5 + 5 
       -> expr( E+E( number( '5' ), op( '+' ), number( '5' ) ) )

<expr> ~~ 1 + 2 + 3 
       -> expr( E+E( 
            E+E(
              number( '1' ), 
              op( '+' ),
              number( '2' ) 
            ),
            op( '+' ),
            number( '3' )
          ) )

You see in parse trees of expressions above, that the operator is also lexed (as “op”). This is triggered by flag with-ops. If you leave out this flag, operators are not lexed, as you see in further examples:

expr2 :- <EXPR{
           :op L E+E
           :op L E-E  = E+E
           :op L E*E  > E+E
           :op L E/E  = E*E
           :op L E**E > E*E
           :op L E++  > E**E
           :op R ++E  = E++
           :op R (E)  > E++
       }>

First example where operator precedence table is used:

<expr2> ~~ 5 + 5 * 4 
        -> expr2( E+E(
              number( '5' ), 
              E*E( number( '5' ), number( '4' ) ) 
           ) )

A more complex example:

<expr2> ~~ 5**2 + 4**2/3**1 * 2 + 1 
        ->  expr2( E+E(
               E+E(
                 E**E( number( '5' ), number( '2' ) ), 
                 E*E(
                   E/E(
                     E**E( number( '4' ), number( '2' ) ),
                     E**E( number( '3' ), number( '1' ) )
                   ),
                   number( '2' )
                 )
               ),
               number( '1' )
            ) )

Here you see how whitespace has influence on tokenizer:

<expr2> ~~ 1*3+++++1 
        -> expr2( E+E( 
             E*E( number( '1' ), E++( E++( number( '3' ) ) ) ), 
             number( '1' ) 
           ) )

<expr2> ~~ 1*3++ + ++1 
        -> expr2( E+E(
            E*E( number( '1' ), E++( number( '3' ) ) ),
            ++E( number( '1' ) )
        ) )

<expr2> ~~ 1*3+++(++1) 
        -> expr2( E+E( 
             E*E( number( '1' ), E++( number( '3' ) ) ), 
             (E)( ++E( number( '1' ) ) ) 
           ) )

<expr2> ~~ (1*3)++
        -> expr2( E++(
             (E)(
               E*E(
                 number( '1' ),
                 number( '3' )
               )
             )
           ) )

Here you see how operator precedence has influence on interpretation of a term ++1--:

prepostest1 := <EXPR{
               :op L ++E
               :op L E-- > ++E
              }>

<prepostest1> ~~ ++1-- -> prepostest1( ++E( E--( number( '1' ) ) ) )

prepostest2 := <EXPR{
               :op L ++E
               :op L E-- < ++E
              }>

<prepostest2> ~~ ++1-- -> prepostest2( E--( ++E( number( '1' ) ) ) )

postcirc1   :- <EXPR{
                  :op R E(E)
                  :op R E,E < E(E)
               }>

<postcirc1> ~~  sum(1, 2) 
            -> postcirc1( E(E)(
                 E,E(
                   number( '1' ),
                   number( '2' ) 
                 )
               ) )

<postcirc1> ~~  sum(1, 2, 3, 4)
            -> postcirc1( E(E)(
                 E,E(
                   number( '1' ),
                   E,E(
                     number( '2' ),
                     E,E(
                       number( '3' ),
                       number( '4' )
                     )
                   )
                 )
               ) )

Typical operator association you find here: