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: