PEG语法和解析器生成器的局限性？

Question

我很享受YARD的使用:

我能够构建全功能计算器.我正在评估YARD做PHP解析器.请关注PEG语法和解析器生成器的局限性.非常感谢你!

Answer 1

我认为PEG的一个重大问题是它们不符合语法的正常分类,因为它们以一种根本不同的方式运作.正常语法是"向后"的,因为它们描述了可以生成的所有可能的句子(程序).PEG描述了如何解析 - 他们从另一端解决问题.

在我看来,这是一种更自然的思考问题的方法,当然对于任何手写(递归 - 下降)解析器我都不会做任何其他事情.

PEG的真正价值,btw,是设计自己的语言; 使用PEG确保语言是明确可解析的,而不是传统的语言设计方法,无论是不关心解析(并提出可疑的语法,如C和C++),或设计语法然后打败它直到它最终成为你的工具(传统上yacc)可以实际解析的东西.通过使基本操作解析(而不是句子生成),PEG使语言设计的这一方面更容易. (15认同)
如果解析的含义由其他信息确定,则排序规则没有帮助.臭名昭着的C++允许"x*y;" 作为一种陈述,有两种解释:声明或算术运算.没有规则排序可以帮助您确定这是什么.您需要上下文信息.C和C++解析器经常通过构建符号表来解决这个问题.知道x是一种类型可以解决问题.但是如果x或y的定义在*语句之后出现*,那么即使这个hack也行不通.安全的赌注是GLR解析器,它只是选择两个解析以便稍后解决. (9认同)
大多数解析器无法正确处理上下文敏感的语法而没有某种类型的hacks(例如,对于解析C,您使解析器反馈到词法分析器,以便它为类型名称分配正确的符号类型,以便它们不会得到被视为常规标识符).PEG很有意思,因为它们可以直接表达C和C++使用的消歧规则(我不知道Python).具体来说,"如果它看起来像一个声明,那就是".他们可以通过命令他们的规则来执行此操作,以便在语句规则之前尝试声明规则. (3认同)

Answer 2

PEG语法的主要限制是它们根本不处理歧义.

可以肯定的是,这也是他们的优势,因为处理含糊不清是使用CFG(无上下文语法)工具中最令人沮丧的部分之一.

使用PEG,您可以通过在另一个模糊匹配但不需要的规则之前对要匹配的规则进行排序来明确处理歧义.

问题是你甚至不知道语言或语法中的某些甚至任何歧义和PEG生成器,至少我试过的那些,不会分析语法歧义以帮助你找到他们然后设计和订购你的规则,以正确的方式处理它们.

像yacc和bison这样的CFG解析器生成器会分析你的语法并报告所有的歧义.不幸的是,他们经常以一种非常神秘的方式报道它们,这很难理解.当然,通常很难修复语法来处理它们.但至少你会意识到它们存在.

使用PEG语法,你可以幸福地忽略概念语法中的歧义,因为一旦你把它变成PEG就不再有歧义了,它只是有匹配的规则,也许是默默无法达到的规则,如果它们有更高的值也会匹配优先.这些可能不会出现在您的测试中,但可能会在发布后显示出来.

使用CFG语法,您不得不在开发过程中处理歧义,但这并不容易.

如果我没有说清楚,这是Joshua Haberman关于Lambda终极编程语言博客的六年讨论:PEGs和Packrat Parsing不是答案.