SPECに記載されているSPARQLの文法がLL(1)か怪しい件
SPARQLのSPECにはEBNFによる文法定義が掲載されており、その下には以下の注釈がある。
The SPARQL grammar is LL(1) when the rules with uppercased names are used as terminals.
しかし、実際のところ、このEBNFを使ってSPARQLパーサを作るとLL(1)では書けない。その理由として、EBNFのルール一覧の上に書かれている以下の一文が挙げられる。
When choosing a rule to match, the longest match is chosen.
私の知る限り、LL(1)文法ならば、そもそも最長一致も何もなく、次の1文字を先読みすればOR（やOneOrNothingなど）で与えられた選択肢のうちどれを選ぶかが決定するはずである。しかし、最長一致を優先するということは、ORで与えられた選択肢を1度全て試し最も長いものを選ぶ、言い換えればバックトラックを行うという意味である。これがLL(1)文法といえるのかどうか、非常に怪しい。
SPARQLの場合、冒頭に引用した文章の通り、1文字単位ではなくトークン単位で見た場合にLL(1)である、というのは好意的に解釈すれば理解可能である。次のトークンを実際に字句解析的に切り出してみて、上手く切り出せるようならそれを選ぶ、という方法だ。例えば次のルールはLL(1)文法的である。
[44]Var::= VAR1 | VAR2
[74]VAR1::= '?' VARNAME[75]VAR2::= '$' VARNAME
VAR1とVAR2は開始文字が違うので、Varにおいて両者のどちらかを選択する場合、VAR1にマッチすればVAR2にマッチすることはないし、VAR2にマッチすればVAR1にマッチすることはない。例えば?xというテキストにVarのルールを適用する場合、VAR1にマッチした時点で、Varの結果が決定し、VAR2についていちいち調べる必要はない。トークン単位のLL(1)としては理解しうるルールである。
しかし、SPARQLのterminalは必ずしもこのような決定的な開始文字を持たないことがある。例えば次の定義だ。
[62]NumericLiteralUnsigned::= INTEGER | DECIMAL | DOUBLE
[77]INTEGER::= [0-9]+[78]DECIMAL::= [0-9]+ '.' [0-9]* | '.' [0-9]+[79]DOUBLE::= [0-9]+ '.' [0-9]* EXPONENT | '.' ([0-9])+ EXPONENT | ([0-9])+ EXPONENT
NumericLiteralUnsignedに例えば1.0をマッチさせる場合、普通に考えて最初の選択肢であるINTEGERが1までマッチして次のトークン切り出しに移るべきである。しかし、SPARQLの言語として正しいのはDECIMALによる1.0全てに対するマッチである。つまり、NumericLiteralUnsignedで与えられた3つの選択肢のうち、INTEGERがマッチするにもかかわらず、DICIMALとDOUBLEも一応確認し、他に最長一致の可能性が無いか確認する必要があるのだ。
この問題はVarの場合と違い、NumericLiteralUnsignedの持つ選択肢の開始部分が重なっていることに起因する。DECIMALの開始部分が完全にINTEGERそのものなのだ。
確かに、terminalの切り出しにおいてこのような最長一致を行うことを前提とするならば、この文法はLL(1)と解釈できるかもしれない。しかし、これは即ちパーサにバックトラックの実装を強要しているわけで、実装におけるLL(1)の優位性を全て無に返してしまっている。
結局のところ、少なくともSPECに記載されているEBNFはLL(1)と呼ぶべき文法ではないか、好意的にLL(1)と解釈した場合本来LL(1)文法が持つ優位性を全く享受できないというわけである。つまり、冒頭の文章には全く意味がなく、ユーザを混乱させる為だけにあると言える。