Day 94：Earley解析器
18年11月20日 · 史二美—北京理工大学 5160 人阅读
Earley解析器
我实现了一个算法，它直接关系到正式语法解析器的实现。并且我已经实现了解析器本身。
由于Earley解析器的有趣特性，所以今天我们将要学习有关他的算法。
最重要的是，Earley解析器能够同时处理左递归和右递归语法，甚至可以处理不明确的语法。事实上，不管您有什么上下文无关的语法，解析器都会正常工作。
 |
Earley解析器模拟非确定性有限自动机！它使用生产规则内的点符号来模拟当前位置。在此之前，解析器通过一次模拟所有可能的位置来创建DFSA电源集，这就是您通常如何实现NDFSA的方式。
解析器中使用了三种机制。
（1）预测器—基于与点符号相关的可能的非终端产品的自动机状态的构造。
（2）Completer—类似于lr解析器中的约简操作；处理在末尾带有点符号的规则的约简。
（3）扫描器—类似于lr解析器中的移位操作；在规则中的终端上推进点符号。
大家已经猜到了Earley解析器的问题所在，以及为什么它被LR解析器所取代-NDFSA的模拟非常慢，内存消耗也很大。然而，如果您有一个复杂的语法，您可以运行几个算法来删除递归、歧义或外观…。或者您可以运行Earley解析器，它为您处理语法。
算法实现
语法：算术表达式
测试一
测试二
测试三（语法：括号）
Python3Turtle
