CODEWITHSUNDEEP
syntaxexpressiongrammarebnf
Kayler Renslow
Kayler Renslow

Reputation: 63

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

Upvotes: 3

Views: 6386

Answers (2)

trijezdci
trijezdci

Reputation: 5474

You may want to take a look at the expression grammar of languages that are typically implemented using recursive descent parsers for which LL(1) grammars are needed which do not allow left recursion. Most if not all of Wirth's languages fall into this group. Below is an example from the grammar of classic Modula-2. EBNF links are shown next to each rule.

http://modula-2.info/m2pim/pmwiki.php/SyntaxDiagrams/PIM4NonTerminals#expression

Upvotes: 0

user207421
user207421

Reputation: 310980

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.

Upvotes: 6

Related Questions