1

我在编写自上而下的解析器时遇到了这个答案：是否有可用于 8 位嵌入式系统的 flex/bison 替代方案？但我对几点感到困惑。

说我有这个语法：

Expr = Id | Id '(' Expr ')'
Stmt = Id '=' Expr | Expr

我不确定这是否是绝对必要的，但我想我们可以保留语法：

Expr = Id ExprRest
ExprRest = ϵ | '(' Expr ')'
Stmt = Id '=' Expr ';' | Expr ';'

我将如何编写正确解析foo(x);为的代码Stmt？如果我们编写如下Stmt解析代码：

func ParseStmt() {
  if ParseId() {
    return ParseTerminal('=') && ParseExpr() && ParseTerminal(';');
  } else {
    return ParseExpr() && ParseTerminal(';');
  }
}

我们将看到Id foo，假设我们在第一种情况下，然后失败，因为我们找不到=下面的foo。

这个语法不是 LL(1) 吗？

4

2 回答 2

1

该文法不是LL(1)，因为LL(1)文法需要能够在仅给定解析堆栈和前瞻标记的情况下确定要扩展哪个产生式。Stmt如果解析堆栈为空，则在给定Id前瞻标记的情况下，您无法判断要使用两个产生式中的哪一个。您可以保留它，但它会变得烦人。

由 生成的可执行文件bison虽然占用了很多 C 行，但实际上非常紧凑。你的语法，由野牛编译，产生了 1559 行 C，但编译成一个 4K 的目标文件，其中（我相信）只有略多于 1K 对应于实际的代码和数据。（当然，这是没有动作的。）

如果您真的想为表达式语法手动编写解析器，我建议您使用自下而上的“Shunting Yard”算法或自上而下的“Pratt 解析器”（两者都可以通过 Google 轻松搜索） ，它比严格的 LL 语法更好地处理运算符优先级之类的事情。但是您可能会发现野牛生成的语法具有可比的大小和速度，以及更好的可读性和可维护性。（或者你可能不会。口味不同。）

于 2013-09-26T17:01:17.020 回答
0

您的问题是 ID(xxx) 可以出现在语句和表达式上下文中。

正如另一个答案所说，您必须考虑更多因素。这并不难。像这样写你的语法：

Stmt = Id  ( '=' Expr ';' |
             RestOfExpression );

 RestOfExpression = '(' Expr ')' |
                     ϵ );
 Expr =  Id  RestOfExpression;

代码应该很明显。

于 2013-09-26T18:58:12.413 回答