LL法
最初のLは、left to right
二文字目のLは、最左導出(leftmost derivation) ()の中身は先読みするTokenの数
ex. LL(1)
LL(1)を使うことで、先読みできるので、処理のやり直しをしない
速い
code:hs
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に対して、、、というのを全部やって全部満たしていればいい
code:bnf
A → α_1
A → α_2
..
B → β_1
..
LL(1)文法の定義
任意の$ A\in V_Nと$ Aを左辺に持つ規則$ A\rightarrow\alpha_1|\alpha_2|\cdots|\alpha_n
参考