parsing - 解析左递归语法

Question

我想为一种已经离开递归但我不知道该怎么做的语言制作一个解析器。我唯一的解析经验是 ll(1)。

例如具有以下 bnf 定义

cqlQuery    ::=     prefixAssignment cqlQuery
| scopedClause
prefixAssignment    ::=     '>' prefix '=' uri
| '>' uri
scopedClause    ::=     scopedClause booleanGroup searchClause
| searchClause
booleanGroup    ::=     boolean [modifierList]
boolean     ::=     'and' | 'or' | 'not' | 'prox'
searchClause    ::=     '(' cqlQuery ')'
| index relation searchTerm
| searchTerm
relation    ::=     comparitor [modifierList]
comparitor  ::=     comparitorSymbol | namedComparitor
comparitorSymbol    ::=     '=' | '>' | '<' | '>=' | '<=' | '<>' | '=='
namedComparitor     ::=     identifier
modifierList    ::=     modifierList modifier | modifier
modifier    ::=     '/' modifierName [comparitorSymbol modifierValue]
prefix, uri, modifierName, modifierValue, searchTerm, index     ::=     term
term    ::=     identifier | 'and' | 'or' | 'not' | 'prox' | 'sortby'
identifier  ::=     charString1 | charString2

我是否必须转换左递归或做其他事情来避免它？

请不要给我翻译者的链接，因为我想手动进行而不是使用程序进行解析。

Answer 1

如果您看一下，modifierList它本质上至少需要一个修饰符。我们不需要做太多就可以摆脱左递归。

modifierList ::= modifier [ modifierList ] 

现在scopedClause有点棘手，但如果我们进行第二次制作，它就会成功。它总是需要至少一个searchClause并且可以有很多booleanGroup searchClause。

scopedClauseTail ::= booleanGroup searchClause [ scopedClauseTail ] 
scopedClause ::= searchClause [ scopedClauseTail ]