Parsing boolean expression without left hand recursion

grammar, parsing, peg, pegjs

Solution

Something like this ought to do it:

expression
 = bool_expression

bool_expression
 = add_expression "==" bool_expression
 / add_expression "!=" bool_expression
 / add_expression

add_expression
 = mult_expression "+" add_expression
 / mult_expression "-" add_expression
 / mult_expression

mult_expression
 = atom "*" mult_expression
 / atom "/" mult_expression
 / atom

atom
 = function_call 
 / string
 / real_number
 / integer
 / identifier

function_call
 = identifier "(" (expression ("," expression)*)? ")"

string
 = "'" [^']* "'"

identifier
 = [a-zA-Z_]+

integer
 = [0-9]+

real_number
 = integer "." integer?
 / "." integer

Problem

I'm trying to match this ``` f(some_thing) == 'something else' ``` - f(some_thing) is a function call, which is an expression - == is a boolean operator - 'something else' is a string, which also is an expression so the boolean expression should be ``` expression operator expression ``` The problem is I can't figure out how to do that without left recursion These are my rules ``` expression = bool_expression / function_call / string / real_number / integer / identifier bool_expression = l:expression space* op:bool_operator space* r:expression { return ... } ``` Using grammar notation, I have ``` O := ==|<=|>=|<|>|!= // operators E := B|.... // expression, many non terminals B := EOE ``` Because my grammar is EOE I don't know how to use the left hand algorithm which is ``` A := Ab|B transforms into A := BA' A':= e|bA ``` Where e is empty and b is a terminal

Original source