消除上下文无关语法中的歧义
消除上下文无关语法中的歧义
提问于 2014-08-17 15:45:34
给定一个不明确的语法，为了消除操作符优先的问题，我们将转换语法以遵循运算符优先规则。为了解决算子的结合性问题，我们考虑到与之相关的算子，将文法转化为左递归或右递归。
现在，当计算机必须进行解析时，假设它使用递归下降算法，那么语法首先应该是明确的吗？还是语法应该根据算法有不同的要求？
如果语法是左递归的，递归下降算法不会终止。现在，我如何给出一个明确的语法(结合性问题得到解决)的算法作为输入？
回答 1
Stack Overflow用户
发布于 2014-08-17 15:58:01
语法必须是LL(k)，才能使用没有回溯的标准高效递归下降算法。有一些标准转换对于将一般LR语法(基本上是由基于确定堆栈的算法解析的任何语法)转换为LL(k)形式非常有用。它们包括左递归消去和左因子分解。这些都是我不打算在这里讨论的广泛的话题。但是，它们在大多数好的编译器文本中都有很好的覆盖，在通过搜索获得的在线注释中也相当好。Aho和是这个和大多数其他编译器基础的一个很好的参考。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/25350812
复制相关文章
相似问题
腾讯云开发者
