algorithm - Recursive Descent precedence parsing - matching lower precedence prefix expressions -

algorithm - Recursive Descent precedence parsing - matching lower precedence prefix expressions -

note: more detailed version of recursive descent precedence parsing missing prefix expression

i'm building simple language parser, , having issue lower precedence prefix expressions. here's illustration grammar:

e = e8 e8 = e7 'or' e8 | e7 e7 = e6 'xor' e7 | e6 e6 = e5 'and' e6 | e5 e5 = 'not' e5 | e4 e4 = e3 '==' e4 | e3 '!=' e4 | e3 e3 = e2 '<' e3 | e2 '>' e3 | e2 e2 = e1 '+' e2 | e1 '-' e2 | e1 '*' e2 | e1 '+' e2 | e1 e1 = '(' e ')' | 'true' | 'false' | '0'..'9'

however, grammar doesn't work correctly not, if it's used rhs of higher precedence infix operator, i.e.:

true == not false

this due == operator requiring e3 on rhs, cannot 'not' operation.

i'm unsure right way express grammar? still possible using simplistic recursive descent approach, or need move more featured algorithm (shunting yard or precedence climbing).

here examples need parse correctly:

input true == 1 < 2, output ==(true, <(1, 2)) input 1 < 2 == true, output ==(<(1, 2), true) input not true == false, output not(==(true, false)) input true == not false, output ==(true, not(false)) ** doesn't work input true < not false, output <(true, not(false)) ** doesn't work

i have attempted alter levels e4, e3, , e2 utilize e5 on rhs of infix expression, suggested in recursive descent precedence parsing missing prefix expression (i.e. e3 '==' e5, e3 '<' e5, etc). breaks precedence between these levels, i.e. true == 1 < 2 incorrectly parsed as<(==(true, 1), 2)`.

when sticking way language defined, cannot have

true == not false

as valid term in language. because then

not false == true

would ambigous: parse tree either

not | == / \ false true

or

== / \ not true | false

note that

true == not (false)

is valid term in language. more intuitive definition of language set not-level e5 downwards e2.

true == not false not false == true

are both valid , not binds false. , alternative meaning of sec look expressed as

not (false == true)

if these options still not satisfy you, have change/extend tool. e.g. yacc/bison parser allows explicitely define operator precedences; see e.g. here

algorithm parsing operator-precedence recursive-descent