代码之家 › 专栏 › 技术社区 › Leandro Caniglia Charlie

如何定义PetitParser中的Pascal变量

petitparser smalltalk

5

Leandro Caniglia Charlie · 技术社区 · 6 年前

下面是我试图在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]' .

问题: 我得到一个栈溢出。

2 回复 | 直到 6 年前

1

5

melkyades 6 年前

问题是你的语法是 左递归 .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'

现在 变量 实际上是指使用标识符的东西,我们可以安全地从 indexed 和 field 向右 变量 :

variable'
    component', variable' / nil asParser

component'
    ^indexed' / field'

indexed'
    ^subscript

field'
    ^fieldName

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

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

2

6

Andrei Chis 6 年前

语法有左递归: variable -> component -> indexed -> variable . 珀蒂帕瑟的用途 Parsing Expression Grammars (PEGs) 无法处理左递归。Peg解析器总是采用左选项,直到找到匹配项为止。在这种情况下,由于左递归,它将找不到匹配项。要使其工作,首先需要消除左递归。消除所有左递归可能会更复杂,因为您还将通过 field 在排除第一个之后。例如,您可以按如下方式编写语法,以使左递归更加明显:

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

如果有左递归,比如:

A  -> A a |  b

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

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

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