Search code examples
intellij-pluginpeggrammar-kit

Re-write Parsing Expression Grammar (PEG) without left recursion


Using https://github.com/JetBrains/Grammar-Kit how to rewrite grammar without left recursion?

grammar ::= exprs
exprs::= (sum_expr (';')?)*
private sum_expr::= sum_expr_infix | sum_expr_prefix
sum_expr_infix ::= number sum_expr_prefix


left sum_expr_prefix::= op_plus number


private op_plus ::= '+'    
number ::= float | integer
float ::= digit+ '.' digit*
integer ::= digit+
private digit ::=('0'|'1'|'2'|'3'|'4'|'5'|'6'|'7'|'8'|'9')

Sample input:

10+20+30.0;
10+20+30.0

Answer shall maintain parse tree property that nodes contain 2/3 children: enter image description here


Solution

  • this question lead in the right direction: Parsing boolean expression without left hand recursion

    grammar ::= e*
    e ::=  math separator?
    
    math ::= add
    add ::=
        mul op_plus math
     |  mul op_minus math
     |  mul
    
    
    mul ::=
        factorial op_mul mul
      | factorial op_div mul
      | factorial
    
    factorial ::= term op_factorial space* | term
    op_factorial ::= '!'
    
    term ::= parentheses | space* number space*
    parentheses ::= '(' math ')'
    
    
    op_minus ::= '-'
    op_plus ::= '+'
    op_div ::= '/'
    op_mul ::= '*'
    number ::= float | integer
    float ::= (digit+'.') digit*
    integer ::=digit+
    digit ::= '0'|'1'|'2'|'3'|'4'|'5'|'6'|'7'|'8'|'9'
    space ::= ' ' | '\t'
    separator ::= ';'
    

    test input:

    1!
    3*2+1
    3*2+1+3.0!
    3*2+1 + 3.0!
    1+1+(1+1)!