I'm trying to write a simple int expression parser using tatsu, a PEG-based Python parser generator. Here is my code:
import tatsu
grammar = r'''
start = expression $ ;
expression = add | sub | term ;
add = expression '+' term ;
sub = expression '-' term ;
term = mul | div | number ;
mul = term '*' number ;
div = term '/' number ;
number = [ '-' ] /\d+/ ;
'''
parser = tatsu.compile(grammar)
print(parser.parse('2-1'))
The output of this program is ['-', '1']
instead of the expected ['2', '-', '1']
.
I get the correct output if I either:
number = /\d+/ ;
expresssion = add | sub | mul | div | number ;
The last option actually works without leaving any feature out, but I don't understand why it works. What is going on?
EDIT: If I just flip the add/sub/mul/div rules to get rid of left recursion, it also works. But then evaluating the expressions becomes a problem, since the parse tree is flipped. (3-2-1
becomes 3-(2-1)
)
There are left recursion cases that TatSu doesn't handle, and work on fixing that is currently on hold.
You can use left/right join/gather operators to control the associativity of parsed expressions in a non-left-recursive grammar.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With