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

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;（无分配，只计算，丢弃;后跟分号）

第二种情况的目的是建立m矿石在未来的变化。我正在考虑一元增量和减量运算符，还有函数调用;这两者都不需要赋值是有意义的。

我看过其他语法（即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中，衍生词可以用语法来定义。这样的定义是明确的，但它们通常不适合用自顶向下的语法进行解析，即使对于自下而上的语法，它们也会产生复杂性。做检查后分析总是一个简单的解决方案。

如果你真的想从表达式语句区分赋值语句，然后你，如果你使用自上而下的分析技术，如递归下降这样的确碰上预测失败（不歧义）的问题。由于语法不是模棱两可的，因此一个简单的解决方案是使用LALR（1）解析器生成器，如bison/yacc，解析这样的语法没有问题，因为它不需要及早决定哪种类型的语句解析。总的来说，使用LALR（1）甚至GLR解析器生成器可以简化语法分析器的实现，它允许您指定一个容易阅读并对应于语法分析的形式的语法。 （例如，LALR（1）解析器可以自然处理左联合算子，而LL（1）语法只能生成右联合解析，因此需要对语法树进行某种重构。）

A递归下降解析器是一种计算机程序，而不是语法，因此它的表达性不受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)); 
    } 
    } 
}