2

我有一个家庭作业，在给定语句定义的语法的情况下，我应该在其中检测语句中的歧义。

例子：

Grammar: S -> S + S | S * S | id
Statement: id * id + id

上面的陈述是模棱两可的，因为两个解析树是可能的。

到目前为止，我有以下歧义：

1) 运算符优先级（上例）
2) if-else 悬空案例
3）无限循环（上面的例子是左递归的）
4) 关联性

你能告诉我更多可行的方法吗？

我必须使用 lex 和 bison (yacc) 设计这个解析器，并在 2 天内提交它，所以任何指针都会对语法和语句中的歧义有所帮助。

4

2 回答 2

1

好吧，如果你有 lex 和 bison 在你的命令中，你可以简单地将语法输入 bison，它会告诉你它是否模棱两可。

否则，您必须构建整个 LALR1 解析器生成器算法，以确定是否存在使语法模棱两可的冲突。这些冲突在解析器构建阶段很晚才被检测到（我的解析器生成器在表生成步骤中找到它们）。也许您可以从我的代码中获取一些指示，它位于https://github.com/Dervall/Piglet

当您尝试填充操作表的一部分时，会发生自底向上解析器中移位/归约和归约/归约的经典案例，该部分已经填充了与您尝试放置的令牌具有相同优先级的条目在里面。

如果您在谈论 LL 解析器，那么无限循环并不是真正的模棱两可的语法 - 语法可以重构为非模棱两可的。

并且语句本身不会以任何方式影响语法是否模棱两可。无论给出什么输入，它都是模棱两可的。

于 2012-04-18T14:01:30.140 回答
1

一般来说，你不能——语法歧义是不可判定的。

也就是说，您可以识别出许多明显模棱两可的语法模式。

  • 左递归和右递归的任何（非无用）非终结符都是模棱两可的（涵盖您上面提到的所有情况，除了悬空其他情况）。
  • 任何具有两个右递归规则的（非无用的）非终结符，其中一个是另一个的前缀是模棱两可的（包括 dangling-else）。
于 2012-04-18T17:48:01.753 回答