我正在研究 PEG（解析表达式语法）解析器，我正在研究的主题之一是与其他解析技术的等效性。
我在From Regular Expressions to Parsing Expression Grammars找到了一篇关于将正则表达式转换为等效 PEG 的好论文。
我希望为LL(*)解析器找到类似的处理方法，但仍然空手而归。在我看来，1中描述的许多技术也将适用于LL(*)转换问题，但是我对形式主义的了解还不够，无法对自己的分析充满信心。
非常感谢您的集体帮助！
问问题
210 次
1 回答
1
我认为关于 PEG 的维基百科文章说明了一切。PEG 通过使用子句排序来消除歧义，进行递归下降。理论上，可以递归下降解析的语言家族是LL家族，但是，由于PEG具有无限前瞻且没有歧义，该家族应该是一个更大的家族，可能是完整的CFG。
每个 LL(k) 语法都可以由具有 k 前瞻的递归下降解析器实现，因此每个 LL(k) 语法都可以通过对规则进行排序来转换为 PEG 语法，以便首先列出需要最长前瞻的那些。
这是一个 LL(k) 文法：
params = expr
params = expr ',' params
要使其成为同一语言的 PEG 语法，必须重新排序规则：
params = expr ',' params
params = expr
于 2012-11-17T14:43:27.347 回答