４．３ LL解析（１）LL解析とは ■本質的には再帰下降解析と同じだが、再帰呼出しの代わりにスタックを用いる。【意味】 ①左から右へ（ Left to right ） ②最左導出（Leftmost Derivation）（２）LL解析の手順 ■文法 G = (T,N,P,S) 入力：記号列 W 出力：もし W∈L(G)ならば W の最左導出。でなければ、エラー表示。初期状態：入力記号列は W$、スタックには $ S (S は出発記号) ■文法 G = (T,N,P,S) 入力：記号列 W 出力：もし W∈L(G)ならば W の最左導出。でなければ、エラー表示。初期状態：入力記号列は W$、スタックには $ S (S は出発記号) LL解析の手順（２） For(;;){ Xをスタックのトップ,A を現在の記号とする。 If( X ∈ T || X == $) if(X==A) { if(X==$)break; Xをポップする；次の入力記号を取り出す；} else エラー表示; else /* X ∈N */ if(M[X,A]==X→Y1Y2…YN ）｛ Xをポップ; Y1Y2…YNをプッシュ； /* Y1がトップになる */ X→Y1Y2…YNを出力;} else エラー表示; /*M[X,A]が定義されていないエラー*/ } （３）解析例【文法】 E ::= TE’ E’::= + TE’| ε T ::= FT’ T’::= * FT’| ε F ::= (E) | i 【解析表】 E E’ T T’ F i E→TE’ 入力記号 + * A ( E→TE’ E’→ +TE T→FT’ $ E’→ ε E’→ ε T’→ ε T’→ ε T→FT’ T’→ ε F→i ) T’→*FT’ F→(E) 【文法】 ① E ::= TE’ ② E’::= + TE’| ε ④ T’::= * FT’| ε ⑤ F ::= (E) | i 1 2 3 4 5 6 7 8 9 10 11 12 13 14 i*(i+i)$ i*(i+i)$ i*(i+i)$ i*(i+i)$ *(i+i)$ *(i+i)$ (i+i)$ (i+i)$ i+i)$ i+i)$ i+i)$ i+i)$ +i)$ +i)$ E$ TE’$ FT’E’$ iT’E’$ T’E’$ *FT’E’$ FT’E’$ (E)T’E’$ E)T’E’$ TE’)T’E’$ FT’E’)T’E’$ iT’E’)T’E’$ T’E’)T’E’$ E’)T’E’$ ③ T ::= FT’ 解析実行例（１～１３） ①適用 ③適用 ⑤適用ポップアップと次入力 ④適用ポップアップと次入力 ⑤適用ポップアップと次入力 ①適用 ③適用 ⑤適用ポップアップと次入力 ④適用（ε）【文法】 ① E ::= TE’ ② E’::= + TE’| ε ④ T’::= * FT’| ε ⑤ F ::= (E) | i 15 16 17 18 19 20 21 22 23 24 +i)$ i)$ i)$ i)$ )$ )$ )$ $ $ $ +TE’)T’E’$ TE’)T’E’$ FT’E’)T’E’$ iT’E’)T’E’$ T’E’)T’E’$ E’)T’E’$ )T’E’$ T’E’$ E’$ $ ③ T ::= FT’ 解析実行例（１５～２４） ②適用ポップアップと次入力 ③適用 ⑤適用ポップアップと次入力 ④適用（ε）とポップアップ ②適用（ε）とポップアップ ④適用（ε）とポップアップ ②適用（ε）とポップアップ終り文法G = (T,N,P,S)のとき語 s∈ (T ∪ N)*に対して FIRST(s)={a∈T|s⇒a･･･｝ A∈Nに対して FOLLOW(A)= {a∈T|s⇒uAav｝なお、S⇒uA のときもFOLLOW(A)に加える。（４）解析表の作成以下のように単純に考えてもよい E E’ T T’ F ::= ::= ::= ::= ::= TE’ + TE’| ε FT’ * FT’| ε (E) | i それぞれの最初の文字 FIRST(E) = FIRST(T) = FIRST(F) = { i, ( } FIRST(E’) = { +, ε｝ FIRST(T’) = { *, ε｝それぞれの後に続く文字 FOLLOW（E) = FOLLOW(E’) = { ), $ } FOLLOW(T) = FOLLOW(T’) = { +, ), $ } FOLLOW(F) = { +, *, ), $} 解析表の各項目が高々1つの規則しか含まないとき、文法Gは「LL(1)である」という。数字の１は「１記号先読み」の意味。解析表の作成手順文法G = (T,N,P,S)のとき各生成規則 A→s に対して以下を行う。 ① 各 a ∈FIRST(s)に対して、A→s をM[A, a]に加える。 ② もしε∈FIRST(s)のとき、各 b ∈FOLLOW(A)に対して A→s を M[A, b]に加える。【演習】前の解析表が、以上の作成手順で得られることを示せ。 FIRST(E) = FIRST(T) = FIRST(F) = { i, ( } FIRST(E’) = { +, ε｝ FIRST(T’) = { *, ε｝ FOLLOW（E) = FOLLOW(E’) = { ), $ } FOLLOW(T) = FOLLOW(T’) = { +, ), $ } FOLLOW(F) = { +, *, ), $} E E’ T T’ F ::= ::= ::= ::= ::= TE’ + TE’| ε FT’ * FT’| ε (E) | i 【ヒント】 Eの行の i と（の桁に E→TE’を入れる。 εがある場合は、FOLLOWのところの記号を見る