如何在PetitParser中定义Pascal变量

Question

这是我试图在PetitParser中实现的(简化的)EBNF部分:

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

我所做的是将所有这些产品(除外identifier)添加为我的子类的ivars,PPCompositeParser并定义相应的方法如下:

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使用无法处理左递归的解析表达式语法(PEG).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.这将成为一个无限消耗执行而不消耗任何输入的循环,并且是堆栈溢出的原因(实际上是左递归).

解决这种情况的技巧是通过添加中间步骤来重写解析器以避免左递归.基本思想是重写版本将在每个周期中消耗至少一个字符.让我们首先简化一下解析器重构'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'实际上是指一些与消耗的标识,我们可以放心地从左侧移动recusion indexed并field在正确的variable':

variable'
    component', variable' / nil asParser

component'
    ^indexed' / field'

indexed'
    ^subscript

field'
    ^fieldName

我写的这个答案没有实际测试代码,但应该是好的.解析器可以进一步简化,我把它留作练习;).

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