5

这是我试图在 PetitParser 中实现的（简化的）EBNF 部分：

variable :: component / identifier
component :: indexed / field
indexed :: variable , $[ , blah , $]
field :: variable , $. , identifier

我所做的是将所有这些产品（除了identifier）添加为我的子类的 ivarsPPCompositeParser并定义相应的方法如下：

variable
  ^component / self identifier

component
  ^indexed / field

identifier
  ^(#letter asParser, (#word asParser) star) flatten

indexed
  ^variable , $[ asParser, #digit asParser, $] asParser

field
  ^variable , $. asParser, self identifier

start
  ^variable

最后，我创建了解析器的一个新实例并将 message 发送给它parse: 'a.b[0]'。

问题：我得到一个堆栈溢出。

4

2 回答 2

7

该文法有一个左递归：variable -> component -> indexed -> variable. PetitParser 使用无法处理左递归的解析表达式语法 (PEG) 。PEG 解析器总是采用左选项，直到找到匹配项。在这种情况下，由于左递归，它将找不到匹配项。要使其工作，您需要首先消除左递归。消除所有左递归可能会更加棘手，因为field在消除第一个之后您也将完成一个。例如，您可以将语法编写如下，以使左递归更明显：

variable = (variable , $[ , blah , $]) | (variable , $. , identifier) | identifier

如果您有左递归，例如：

A  -> A a |  b

你可以消除它（e 是一个空的解析器）

A  -> b A'
A' -> a A' | e

您需要应用两次才能摆脱递归。或者，如果您不想解析所有可能的标识符组合，您可以选择简化语法。

于 2019-01-15T23:48:50.907 回答
5

问题是您的语法是递归的。PetitParser 使用自上而下的贪心算法来解析输入字符串。如果你按照这些步骤，你会看到它start从那时开始variable -> component -> indexed -> variable。这变成了一个无限执行而不消耗任何输入的循环，并且是堆栈溢出的原因（即实践中的左递归）。

解决这种情况的技巧是通过添加中间步骤来重写解析器以避免左递归。基本思想是重写后的版本在每个循环中至少会消耗一个字符。让我们首先简化解析器重构“索引”和“字段”的非递归部分，并将它们移到底部。

variable
  ^component, self identifier

component
  ^indexed / field

indexed
  ^variable, subscript

field
  ^variable, fieldName

start
  ^variable


subscript
    ^$[ asParser, #digit asParser, $] asParser

fieldName
    ^$. asParser, self identifier

identifier
  ^(#letter asParser, (#word asParser) star) flatten

现在您可以更容易地看到（通过循环），如果variable要结束递归，则必须在开头找到一个标识符。这是开始的唯一方式，然后是更多的输入（或结束）。让我们称之为第二部分variable'：

variable
    ^self identifier, variable'

现在variable'实际指的是使用标识符的东西，我们可以安全地将recusion从左侧indexed和field右侧移动到variable'：

variable'
    component', variable' / nil asParser

component'
    ^indexed' / field'

indexed'
    ^subscript

field'
    ^fieldName

我在没有实际测试代码的情况下编写了这个答案，但应该没问题。解析器可以进一步简化，我把它作为练习;)。

有关左递归消除的更多信息，您可以查看左递归消除

于 2019-01-16T00:51:33.853 回答