我正在阅读这本书：编程语言的形式语法和语义。我不明白这个练习：
考虑以下两个语法，每个语法都会生成正确平衡的括号和括号字符串。确定其中一个或两个是否模棱两可。希腊字母ε代表一个空字符串。
<string> ::= <string> <string> | ( <string> ) |[ <string> ] | ε<string> ::= ( <string> ) <string> | [ <string> ] <string> | ε
问问题
186 次
1 回答
1
第一个是模棱两可的，第二个不是。这是一个关于如何将上下文无关文法 (CFG) 转化为解析树的问题。在第一个 CFG 中，第一个产生式是歧义的根源。如果我写字符串“（）（）（）”，则不清楚该字符串的哪个部分可以匹配左侧非终结符，哪个部分可以匹配右侧非终结符。
该字符串的一个有效解析树是前两个字符“()”匹配第一个非终结符，然后匹配第二个产生式，字符串的其余部分“()()”匹配正确的非终结符，这再次匹配第一个生产。
另一个有效的解析树是前四个字符“()()”匹配左侧非终结符，其余的“()”匹配右侧非终结符。两者都同样有效，因此存在歧义。像 LR 解析器这样的解析器工具称之为移位/归约冲突。
如果您只想查看字符串是否属于一种语言，这绝对没有问题。如果任何解析工作，你很好。但是，如果您尝试创建解析树以用作例如编程语言的抽象语法树，那么这确实会产生问题。
要说明为什么这是解析语言的问题，请查看此示例。
<expression> ::= <expression> <expression> | <expression> + <expression> | <expression> * <expression>
你如何解析“1+2*3”？是“(1+2)*3”还是“1+(2*3)”？我给出的语法有移位/减少冲突，所以没有指定。大多数 LR 解析工具会自动为您解决这个冲突。这很危险，因为如果我正在编写一种编程语言，应该对程序员将获得的内容有一个明确的理解。由于这是一个典型的算术表达式，我们可能应该遵循数学约定并得到“1+(2*3)”的答案。
解决方案是重写语法，使其明确，或者许多解析器工具也只允许我们明确指定词汇符号的关联性和优先级，这对于保持语法的美观和可读性非常方便。
于 2014-03-29T04:44:15.957 回答