如何在 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

语法有一个左递归：variable -> component -> indexed -> variable。 PetitParser 使用无法处理左递归的 Parsing Expression Grammars (PEGs)。 PEG 解析器总是选择左边的选项，直到它找到一个匹配项。在这种情况下，由于左递归，它将找不到匹配项。要使其工作，您需要首先消除左递归。消除所有左递归可能更棘手，因为在消除第一个递归后，您还将通过 field 获得一个。比如可以这样写语法，让左递归更明显：

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

如果你有一个像这样的左递归：

A  -> A a |  b

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

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

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

Answer 2

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

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

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 的左侧移动到 [=16] 的右侧=]:

variable'
    component', variable' / nil asParser

component'
    ^indexed' / field'

indexed'
    ^subscript

field'
    ^fieldName

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

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

如何在 PetitParser 中定义 Pascal 变量

How to define Pascal variables in PetitParser

smalltalk

petitparser