PICA解析：将PackRAT解析重新定义为动态编程算法

下载PDF摘要：递归下降解析器是由一组相互递归的函数构建的，其中每个函数直接实现语法的一个非终结符。PackRAT解析器使用记忆来降低递归下降解析的时间复杂度，从输入长度的指数下降到线性。递归下降解析器非常容易编写，但存在两个重要问题：(I)左递归语法导致解析器陷入无限递归；(Ii)出现语法错误后，很难或不可能以最佳方式恢复解析状态并继续解析。pika解析器解决了这两个问题，pika解析器是包解析的一种新的动态编程算法，它需要反向解析输入：自下而上和右向左，而不是自上而下和从左到右。这种反向解析顺序使得pika解析器能够处理使用直接或间接左递归来实现左关联的语法，简化语法编写，并且还允许从语法错误中进行最佳恢复，这是IDE和编译器的重要属性。PICA解析保持了PackRAT解析的线性时间性能特征，它是输入长度的函数。Pika解析器是根据广泛使用的Parboiled2和ANTLR4解析库进行基准测试的。对于表达式语法，PICA解析器的性能明显好于其他解析器，尽管对于实现Java语言规范的复杂语法，每个输入字符都会产生很大的持续性能影响。因此，如果性能很重要，最好将pika解析应用于简单的中等大小的语法，或者应用于非常大的输入，如果其他解析替代方案不能线性扩展输入的长度。给出了对逆性、结合性和左递归的几点新见解。