search

gnebehay / parser

A simple parser for mathematical expressions.
MIT License
169 stars 17 forks source link

Computes "7-4+2" as 1, not 5 #3

Closed AZHenley closed 4 years ago

AZHenley commented 4 years ago

The parser treats all operators as right associative so that "7-4+2" is treated as 7-(4+2) and evaluates to 1 instead of 5.

gnebehay commented 4 years ago

Thanks for spotting this, will look into it!

gnebehay commented 4 years ago

Added this as a known issue to the Readme, will try to investigate more how to solve this, but currently it looks like a surprising limitation of LL(1) parsers that you cannot have left-associativity. https://cs.stackexchange.com/a/43071

AZHenley commented 4 years ago

The typical solution is to write the grammar to allow repetition for each rule:

expression ::= term {( "-" | "+" ) term}
term ::= unary {( "/" | "*" ) unary}
unary ::= ["+" | "-"] primary
gnebehay commented 4 years ago

ah, that makes sense, will give it a try!