鉴于上下文无关文法，找到模棱两可的语句

我有一个家庭作业任务，其中我应该检测语句中的歧义，给定语句定义的语法。鉴于上下文无关文法，找到模棱两可的语句

实施例：

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

因为有两个分析树是可能的上面的语句是不明确的。

我心里有以下歧义截至目前：

1) Operator precedence (example above) 
2) If-else dangling case 
3) Infinite loop (example above is left recursive) 
4) Associativity

你能告诉我了这将是可行的？

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

来源

2012-04-18 Khushman Patel

您可能会考虑在新的计算机科学堆栈交换站点上提出这些问题：http://cs.stackexchange.com/ – Patrick87 2012-04-19 20:35:08

@ Patrick87：感谢您的提示！ – 2012-04-24 11:46:28

@ Patrick87恕我直言，它更适合于[CSTheory]（http://cstheory.stackexchange.com/）:) – 2012-07-16 19:01:20

好吧，如果你的lex和bison在你的命令下，你可以简单地将语法送入野牛，它会告诉你它是否含糊不清。否则，您将必须构造整个LALR1解析器生成器算法，以确定是否存在导致语法不明确的冲突。这些冲突在解析器构建阶段很晚才被检测到（我的解析器生成器在表生成步骤中发现它们）。也许你可以从我的代码如何做到这一点，它是发现在https://github.com/Dervall/Piglet

当你试图填充一部分的动作表中已经填充了与您试图放入它的标记具有相同优先级的条目。

如果你在谈论LL解析器，无限循环并不是一个模棱两可的语法的例子 - 语法可以被重构为非模糊的。

而声明本身不会影响语法是否含糊不清。无论给出什么输入，它都是模棱两可的。

来源

2012-04-18 14:01:30 Dervall

因此，我应该在语法输入时尽可能多地检测语法中的歧义性？因为即使是在一个模棱两可的语法中，也可以写出一个明确的陈述，所以我只需要提到输入的陈述中的含糊不清。在上面的例子中，'id * id'不会有歧义，但是'id * id + id'将会是。 – 2012-04-18 14:12:54

为了解决这个问题，您将需要跟踪解析器将在哪些状态下进行模糊转换。从本质上讲，您将制作一个LR解析器，而不是报告冲突将标记冲突出现为错误单元格的单元格。在这种情况下，只会在解析器进入其中一个单元格时报告错误。 – Dervall 2012-04-18 14:16:44

冲突并不意味着语法是模棱两可的，只是它不是LALR（1）。在非模糊语法中很容易发生冲突。 – 2012-04-18 17:34:04

一般来说，你不能 - 语法歧义是undecidable。

也就是说，有很多语法模式可以识别出明显含糊的语法模式。

任何（非无用的）非左终端和右递归的终端都是不明确的（涵盖了除上述之外的其他所有情况）。
任何（非无用的）具有两个右递归规则的非终端，其中一个是另一个的前缀是不明确的（涵盖dangling-else）。

来源

2012-04-18 17:48:01

鉴于上下文无关文法，找到模棱两可的语句

回答

相关问题