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

Question

所以问题是关于下面的语法。我正在研究一种小型解释语言（我们在课堂上学习了一些编译器设计，所以我想将其提升到一个新的水平并自己尝试一些东西）。我一直在尝试制作非终结符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到以下两种情况：

1. x = 789;（常规赋值，后跟分号）
2. x+2;（没有赋值，只是计算，丢弃；后面跟一个分号）

第二个案例的目的是为未来更多的改变奠定基础。我正在考虑一元递增和递减运算符，以及函数调用；两者都不要求分配有意义。

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

感谢所有帮助。

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

Answer 1

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

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

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

有两个相对容易实现的小复杂问题：

1. 从逻辑上讲，与大多数运算符不同，赋值与右侧关联，因此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其中需要括号，即使赋值的优先级低于三元运算符。

   不过，这些选项在语法中实现起来并不困难。

2. 在许多语言中，赋值的左侧具有受限制的语法。在具有参考价值的C++中，这种限制可以被认为是语义上的，并且我相信它通常是通过语义检查来实现的，但在许多C衍生物中lvalue可以通过语法来定义。这样的定义是明确的，但它们通常不适合用自上而下的语法进行解析，并且即使对于自下而上的语法来说它们也会造成复杂性。进行解析后检查始终是一个简单的解决方案。

如果你真的想区分赋值语句和表达式语句，那么如果你使用自上而下的解析技术（例如递归下降），你确实会遇到预测失败（而不是歧义）的问题。由于语法是明确的，一个简单的解决方案是使用 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;
    }
  }
}

可以轻松修改以能够解析表达式和语句。首先，重构该函数，以便在给定第一个运算符的情况下解析表达式的“其余部分”。（唯一的变化是新的原型和正文第一行的删除。）

/* 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));
    }
  }
}