如何修改解析语法以允许赋值和非赋值语句？

Question

所以问题是关于下面的语法。我正在研究一种微型解释语言，只是为了好玩（我们在 class 中学习了一些编译器设计，所以我想把它提升到一个新的水平并自己尝试一些东西）。我一直在尝试制作非终端符号 Expr.

Statement ::= Expr SC
Expr ::=           /* I need help here */
Assign ::= Name EQUAL Expr
AddSub ::= MulDiv {(+|-) AddSub}
MulDiv ::= Primary {(*|/) MulDiv}
Primary ::= INT | FLOAT | STR | LP Expr RP | Name
Name ::= ID {. Name}

Expr 必须使 Statement 必须考虑两种情况：

x = 789;（正则赋值，后接分号）
x+2;（没有赋值，只是计算，丢弃；后跟分号）

第二个案例的目的是为以后更多的改变打下基础。我在考虑一元递增和递减运算符，以及函数调用；两者都不需要赋值才有意义。

我看过其他语法（即C#），但太复杂和冗长，难以理解。当然，我不是在寻找解决方案，而只是寻求有关如何修改语法的指导。

感谢所有帮助。

编辑：我应该说我最初的想法是 Expr ::= Assign | AddSub，但这行不通，因为它会产生歧义，因为两者都可以以非终端符号 Name 开头。我已经制作了我的 tokenizer，它允许一个标记向前看（peek），但我没有为非终端做这样的事情，因为它会试图解决一个可以避免的问题（歧义）。在语法中，终结符是全大写的。

Answer 1

最简单的解决方案是 C 的设计者实际采用的解决方案，因此也是各种 C 派生的解决方案：将赋值简单地视为另一个运算符，而不将其限制在语句的顶层。因此，在 C 中，以下是没有问题的：

while ((ch = getchar()) != EOF) { ... }

不是每个人都会考虑这种好的风格，但它确实很常见（特别是在 for 语句的子句中，其语法或多或少要求赋值是一个表达式）。

有两个小并发症，比较容易完成：

从逻辑上讲，与大多数运算符不同，赋值关联到右侧，因此 a = b = 0 被解析为 a = (b = 0) 而不是 (a = b) = 0（这是非常出乎意料的).它的结合力也很弱，至少在右边是这样。

关于它应该多紧地绑定到左边的观点各不相同。在 C 中，大多数情况下遵循严格的优先级模型，因此 a = 2 + b = 3 被拒绝，因为它被解析为 a = ((2 + b) = 3)。 a = 2 + b = 3 可能看起来很糟糕，但也要考虑 a < b ? (x = a) : (y = a)。在 C++ 中，三元运算符的结果可以是引用，您可以将其写为 (a < b ? x : y) = a，其中需要括号，即使赋值的优先级低于三元运算符。
但是，
None 这些选项很难用语法实现。
在许多语言中，赋值语句的左侧具有受限语法。在具有引用值的 C++ 中，限制可以被认为是语义的，我相信它通常通过语义检查来实现，但在许多 C 派生中 lvalue 可以在语法上定义。这样的定义是明确的，但它们通常不适合用自上而下的语法进行解析，即使对于自下而上的语法，它们也会造成复杂性。进行检查 post-parse 始终是一个简单的解决方案。

如果你真的想区分赋值语句和表达式语句，那么你确实运行进入预测失败的问题（不是歧义）如果你使用top -向下解析技术，例如递归下降。由于语法没有歧义，一个简单的解决方案是使用 LALR(1) 解析器生成器，例如 bison/yacc，它可以毫无问题地解析这样的语法，因为它不需要及早决定哪种语句正在解析。总的来说，使用 LALR(1) 甚至 GLR 解析器生成器可以简化解析器的实现，因为它允许您以易于阅读且与句法分析相对应的形式指定语法。（例如，LALR(1) 解析器可以自然地处理左关联运算符，而 LL(1) 文法只能产生右关联解析，因此需要对语法树进行某种重构。）

递归下降解析器是一个计算机程序，而不是语法，因此它的表达能力不受 LL(1) 语法的形式约束的限制。这既是优点也是缺点：优点是您可以找到不受 LL(1) 文法限制的解决方案；弱点是提取关于语言精确语法的清晰陈述要复杂得多（有时甚至是不可能的）。例如，这种能力允许递归下降文法以或多或少自然的方式处理左结合性，尽管有上述限制。

如果你想走这条路，那么解决办法就很简单了。您将拥有某种功能：

/* This function parses and returns a single expression */
Node expr() {
  Node left = value();
  while (true) {
    switch (lookahead) {
      /* handle each possible operator token. I left out
       * the detail of handling operator precedence since it's
       * not relevant here
       */
      case OP_PLUS: {
        accept(lookahead);
        left = MakeNode(OP_PLUS, left, value());
        break;
      }
      /* If no operator found, return the current expression */
      default:
        return left;
    }
  }
}

这很容易被修改为能够解析表达式和语句。首先，重构函数，以便在给定第一个运算符的情况下解析表达式的 "rest"。（唯一的变化是一个新的原型和删除正文中的第一行。）

/* This function parses and returns a single expression
 * after the first value has been parsed. The value must be
 * passed as an argument.
 */
Node expr_rest(Node left) {
  while (true) {
    switch (lookahead) {
      /* handle each possible operator token. I left out
       * the detail of handling operator precedence since it's
       * not relevant here
       */
      case OP_PLUS: {
        accept(lookahead);
        left = MakeNode(OP_PLUS, left, value());
        break;
      }
      /* If no operator found, return the current expression */
      default:
        return left;
    }
  }
}

有了它，就可以直接实现 expr 和 stmt:

Node expr() {
  return expr_rest(value());
}

Node stmt() {
  /* Check lookahead for statements which start with
   * a keyword. Omitted for simplicity.
   */

  /* either first value in an expr or target of assignment */
  Node left = value();

  switch (lookahead) {
    case OP_ASSIGN: 
      accept(lookahead);
      return MakeAssignment(left, expr())
    }
    /* Handle += and other mutating assignments if desired */
    default: {
      /* Not an assignment, just an expression */
      return MakeExpressionStatement(expr_rest(left));
    }
  }
}

如何修改解析语法以允许赋值和非赋值语句？

How to modify parsing grammar to allow assignment and non-assignment statements?

grammar

context-free-grammar