如何在PetitParser中定义Pascal变量

Question

下面是我试图在PetitParser中实现的(简化的) EBNF部分：

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

我所做的是将所有这些结果(identifier除外)添加为PPCompositeParser子类的ivars，并定义相应的方法如下：

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

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

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

Answer 1

问题是语法是递归的。PetitParser使用自上而下的贪婪算法来解析输入字符串.如果您遵循这些步骤，您将看到它从start到variable -> component -> indexed -> variable。这变成了一个循环，可以在不消耗任何输入的情况下无限地执行，这也是堆栈溢出的原因(实际上是左递归)。

解决这种情况的诀窍是通过添加中间步骤来重写解析器，以避免左递归。其基本思想是重写后的版本在每个周期中至少要消耗一个字符。让我们先简化一下解析器，重构“indexed”和“字段”的非递归部分，然后将它们移到底部。

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'实际上是指使用了标识符的东西，我们可以安全地将回溯从indexed和field的左边移到variable'中的右边。

variable'
    component', variable' / nil asParser

component'
    ^indexed' / field'

indexed'
    ^subscript

field'
    ^fieldName

我写了这个答案，实际上并没有测试代码，但应该是okish。解析器可以进一步简化，我将其保留为摘录;)。

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

Answer 2

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

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

如果有左递归，如下所示：

A  -> A a |  b

您可以像(e是一个空解析器)一样消除它。

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

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