如何修改解析语法以允许分配和非分配语句

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