解析左遞歸語法

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 ]