数学表达式的语法规则（无左递归）

Question

我正在尝试找出任何数学表达式的语法规则。

我正在使用 EBNF（下面链接的维基文章）来推导语法规则。

我设法想出了一个可以用一段时间的方法，但是语法规则失败 onScreenTime + (((count) - 1) * 0.9)。

规则如下：

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

mathRhs ::= mathOperator mathRhsGroup
          | mathOperator mathOperand mathRhs?

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

您可以安全地假设 mathOperand 是正数或负数，或变量。您还可以假设 mathOperator 表示任何数学运算符，如 + 或 -。

另外，LPAREN 和 RPAREN 分别是 '(' 和 ')'。

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

编辑忘记提及它在 (count) - 1 上失败了。它说 RPAREN 预期而不是 - 1.

编辑 2 我修改后的 EBNF 现在看起来像这样：

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

Answer 1

看看任何编程语言的表达式语法：

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 ')'
    ;

作为 reader 的练习留下的求幂：请注意，求幂运算符是 right-associative。这是在 yacc 表示法中。注意您使用的是 EBNF，而不是 BNF。

EDIT 我的 non-left-recursive EBNF 不如我的 yacc 强，但是要分解 left-recursions 你需要一个像这样的方案例如：

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

等，其中 * 表示 'zero or more'。我在下面对此的评论大多是不正确的，应该被忽略。

Answer 2

您可能想看一下通常使用递归下降解析器实现的语言的表达式语法，其中需要 LL(1) 语法，不允许左递归。大多数（如果不是全部）Wirth 的语言都属于这一组。下面是经典 Modula-2 语法的示例。 EBNF 链接显示在每个规则旁边。

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

数学表达式的语法规则（无左递归）

Grammar Rule for Math Expressions (No Left-Recursion)

syntax

grammar

expression

ebnf