2

再帰を残した言語のパーサーを作りたいのですが、どうすればよいかわかりません。解析に関して私が持っている唯一の経験は 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

左再帰を変換するか、それを回避するために何か他のことをする必要がありますか?

解析にプログラムを使用せず、手動で行いたいので、翻訳者へのリンクを提供しないでください。

4

1 に答える 1

2

見てみると、modifierList本質的に少なくとも1つの修飾子が必要です。左再帰を取り除くために多くのことをする必要はありません。

modifierList ::= modifier [ modifierList ]

今scopedClauseは少しトリッキーですが、2 番目のプロダクションをブレイクアウトすればうまくいきます。常に少なくとも 1 つ必要であり、searchClause多くのbooleanGroup searchClause. 

scopedClauseTail ::= booleanGroup searchClause [ scopedClauseTail ] 
scopedClause ::= searchClause [ scopedClauseTail ]
于 2012-08-31T09:14:14.810 に答える