LL法
最初のLは、left to right
二文字目のLは、
最左導出(
leftmost derivation)
()の中身は先読みするTokenの数
ex. LL(1)
LL(1)を使うことで、先読みできるので、処理のやり直しをしない
速い
hsll = sequence [char 'a', char 'b' <|> char 'c']
main = do
parseTest ll "ab"
parseTest ll "ac"
こうすると、とりあえず"a"まではパースして、次に左辺を試し、失敗したら"c"を見る。
つまり、"a"を再びパースしなくて済む
手戻りが少なくて済む
LL(1)文法の条件
形式的な定義
任意のA\in Nと、Aを左辺とする全ての生成規則をまとめたA\rightarrow \alpha_1|\alpha_2|\cdots|\alpha_nに対して、i\ne jなら\mathrm{DIRECTOR}(A,\alpha_i)\cap\mathrm{DIRECTOR}(A,\alpha_j)=\phiがなりたつときLL(1)文法という
要するに、任意の非終端記号について全ての生成規則のDIRECTOR集合の積集合が空集合ならLL(1)文法
以下のような規則があったときを考えると、
まずはAに対して
\mathrm{DIRECTOR}(A,\alpha_1), \mathrm{DIRECTOR}(A,\alpha_2),..を求めて、これらの集合にかぶりがなければいい
次にBに対して、、、というのを全部やって全部満たしていればいい
bnfA → α_1
A → α_2
..
B → β_1
..
LL(1)文法の定義
任意のA\in V_NとAを左辺に持つ規則A\rightarrow\alpha_1|\alpha_2|\cdots|\alpha_n
参考