smalltalk - 如何在 PetitParser 中定义 Pascal 变量

Question

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

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

我所做的是将所有这些产生式(除了 identifier )添加为我的子类 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 使用 Parsing Expression Grammars (PEGs)无法处理左递归。 PEG 解析器始终采用左选项，直到找到匹配项。在这种情况下，由于左递归，它不会找到匹配项。要使其工作，您需要首先消除左递归。消除所有左递归可能会更棘手，因为您还将通过 field 得到一个消除第一个之后。例如，您可以编写如下语法，使左递归更明显:

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

如果你有一个左递归，比如:

A  -> A a |  b

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

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

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