Search code examples
syntaxexpressiongrammarebnf

Grammar Rule for Math Expressions (No Left-Recursion)


I'm trying to figure out a grammar rule(s) for any mathematical expression.

I'm using EBNF (wiki article linked below) for deriving syntax rules.

I've managed to come up with one that worked for a while, but the grammar rule fails with onScreenTime + (((count) - 1) * 0.9).

The rule is as follows:

math ::= MINUS? LPAREN math RPAREN
       | mathOperand (mathRhs)+

mathRhs ::= mathOperator mathRhsGroup
          | mathOperator mathOperand mathRhs?

mathRhsGroup ::= MINUS? LPAREN mathOperand (mathRhs | (mathOperator mathOperand))+ RPAREN

You can safely assume mathOperand are positive or negative numbers, or variables. You can also assume mathOperator denotes any mathematical operator like + or -.

Also, LPAREN and RPAREN are '(' and ')' respectively.

EBNF: https://en.wikipedia.org/wiki/Extended_Backus%E2%80%93Naur_Form

EDIT Forgot to mention that it fails on (count) - 1. It says RPAREN expected instead of - 1.

EDIT 2 My revised EBNF now looks like this:

number ::= NUMBER_LITERAL //positive integer

mathExp ::= term_ ((PLUS | MINUS) term_)* // * is zero-or-more.

private term_ ::= factor_ ((ASTERISK | FSLASH) factor_)*

private factor_ ::= PLUS factor_
                  | MINUS factor_
                  | primary_

private primary_ ::= number
                   | IDENTIFIER
                   | LPAREN mathExp RPAREN

Solution

  • Have a look at the expression grammar of any programming language:

    expression
        : term
        | expression '+' term
        | expression '-' term
        ;
    
    term
        : factor
        | term '*' factor
        | term '/' factor
        | term '%' factor
        ;
    
    factor
        : primary
        | '-' factor
        | '+' factor
        ;
    
    primary
        : IDENTIFIER
        | INTEGER
        | FLOATING_POINT_LITERAL
        | '(' expression ')'
        ;
    

    Exponentiation left as an exercise for the reader: note that the exponentiation operator is right-associative. This is in yacc notation. NB You are using EBNF, not BNF.

    EDIT My non-left-recursive EBNF is not as strong as my yacc, but to factor out the left-recursions you need a scheme like for example:

    expression
        ::= term ((PLUS|MINUS) term)*
    term
        ::= factor ((FSLASH|ASTERISK) factor)*
    

    etc., where * means 'zero or more'. My comments on this below are mostly incorrect and should be ignored.