言語プロセッサ ー第７回目ー 構文解析（続き）.

Presentation on theme: "言語プロセッサ ー第７回目ー 構文解析（続き）."— Presentation transcript:

1 言語プロセッサ ー第７回目ー 構文解析（続き）

2 今日の内容 構文解析 LL(1)文法（復習） First集合（復習） Follow集合（復習） 構文解析表による構文解析法
予測的構文解析のモデル 構文解析表の作り方 動作　など 言語プロセッサ2011

3 LL（１）文法 LL(1)文法のイメージ： A → α｜β
確認事項 LL(1)文法のイメージ： A → α｜β という規則で、αかβのどちらの書換えを選ぶかを決めるとき、入力の先頭記号１個を見ることにより、バックトラックが起きないような選択が可能な文法。 つまり、適応するべき文法規則を、１文字先読みすれば決定できるということ。 高速処理には大切な性質です。 言語プロセッサ2011

4 形式文法（復習) 文法 G=( V, N, P, S ), ただし、 V: 終端記号の集合（語彙)
確認事項 文法 G=( V, N, P, S ), ただし、 V: 終端記号の集合（語彙) N: 非終端記号の集合（構文構造記述用語集） P: 書換え規則の集合 S: 開始記号 言語プロセッサ2011

5 LL（１）文法の条件 文法への制限 構文解析方法 左再帰性の除去 括りだし(factoring) Top down 再帰呼び出し
確認事項 文法への制限 左再帰性の除去 括りだし(factoring) 構文解析方法 Top down 再帰呼び出し １文字先読み 言語プロセッサ2011

6 １文字先読み十分性の条件は？ First集合とFollow集合を用いて作成される 構文解析表において，表内のどのセルにも動作が多重に定義されていないこと． (詳細は後述します。) 確認事項 言語プロセッサ2011

7 First集合 【意味】 文字列αから導出される文字列の先頭(最左端)に現れる終端記号の集合。 【定義】
確認事項 【定義】 First(α)={a | a ∈ V=(Vn∪Vt)*, α=*=>a… } ただし、α=*=>εならば、ε∈First(α) 【意味】 　　文字列αから導出される文字列の先頭(最左端)に現れる終端記号の集合。 言語プロセッサ2011

8 First集合 【First集合を求めるアルゴリズム】 以下を、どのFirst集合にも新たに追加するものがなくなるまで繰り返す。
確認事項 【First集合を求めるアルゴリズム】 以下を、どのFirst集合にも新たに追加するものがなくなるまで繰り返す。 First(ε)={ε} First(aα)={a} if a∈V　 （Vは終端記号の集合） if( First(Y) /∋ ε) 　 Yは空文字列にならない。 First(Yα)= First(Y) else First(Yα)= (First(Y) ー {ε})∪ First(α) 4. if(X→α) First(X)= First(X) ∪First(α) 言語プロセッサ2011

9 Follow集合 【意味】 Xの直後に現れる可能性のある終端記号の集合 【定義】
確認事項 【定義】 Follow(X)={a | a ∈ V, S=*=>…Xa… } 【意味】 Xの直後に現れる可能性のある終端記号の集合 言語プロセッサ2011

10 Follow集合 【Follow集合を求めるアルゴリズム】 以下を、どのFollow集合にも新たに追加するものがなくなるまで繰り返す。
確認事項 【Follow集合を求めるアルゴリズム】 以下を、どのFollow集合にも新たに追加するものがなくなるまで繰り返す。 Follow(S)に$を加える。 規則 A → αBβ (B∈N) に対して、 （ア）First(β)をFollow(B)に加える。 ただし、ε∈First(β) のときはεは加えない。 （イ）ε∈First(β)またはβ=εならば、 Follow(A)をFollow(B)に加える。 言語プロセッサ2011

11 First集合とFollow集合 【定義】 1. First(α)={a | a ∈ V, α=*=>a… }
確認事項 【定義】 1. First(α)={a | a ∈ V, α=*=>a… } ただし、α=*=>εならば、ε∈First(α) 2. Follow(X)={a | a ∈V, S =*=> …Xa… } 言語プロセッサ2011

12 First集合とFollow集合 【例】 文法G=(V,N,E,P) P={ E→TE’, E’ →+TE’ | ε T→FT’
確認事項 First集合とFollow集合 【例】 文法G=(V,N,E,P) P={ E→TE’, E’ →+TE’ | ε T→FT’ T’ →*FT’ | ε F→(E) | i } 教科書p.86より 言語プロセッサ2011

13 First(E) = First(T) = First(F) = { (, i } First(E’) = { +, ε}
確認事項 First(E) = First(T) = First(F) = { (, i } First(E’) = { +, ε} First(T’) = { *, ε} Follow(E) = Follow(E’) = { ), $} Follow(T) = Follow(T’) = { +, ), $} Follow(F) = { +, *, ), $} 言語プロセッサ2011

14 構文解析表による構文解析法 予測的構文解析のモデル 構文解析表の作り方 構文解析のアルゴリズム 言語プロセッサ2011

15 予測的構文解析のモデル 入力 a + b $ X Y Z $ プログラム 出力 構文解析表 スタック 言語プロセッサ2011

16 構文解析表の作り方 入力：　文法G 出力：　構文解析表M 手順：　（次のページ参照） 言語プロセッサ2011

17 構文解析表作成手順 文法の各規則A→αに対して、ステップ２と３を行う。
各終端記号a∈First(α)に対して、M[A, a]にA→αを記入する。 ε∈First(α)ならば、各終端記号b∈Follow(A)に対して、M[A, b]にA→αを記入する。 ε∈First(α)かつ$∈Follow(A)ならば、 M[A, $]にA→αを記入する。 Mの未記入欄にerrorを記入する。 言語プロセッサ2011

18 上記のアルゴリズムは任意の文法に対しても適用できるが、文法によってはMの欄に対して複数の規則が書き込まれることがある。
【例】 P = {S →i C t S S’ | a, S’→e S | ε, C→b } ( M[S’, ε] を求めてみよ。) LL(1)文法はこのようなことが起きない文法。 言語プロセッサ2011

19 構文解析のアルゴリズム X = a = $ ならば、”構文解析成功” を出力し停止。
X = a =!= $ ならば、スタックからXをpopし、入力ポインタを１つ進める。 a∈Vならば、M[X, a]を調べる。M[X,a]={X→ABC}ならば、C,B,Aの順にスタックにpushし、 X→ABCを実行する。M[X,a]=errorならば、停止。 言語プロセッサ2011

20 復習問題 言語プロセッサ2011

21 文法 E → E + T | T T → T * F | F F → ( E ) | id 左再帰性を除去しなさい． 言語プロセッサ2011

22 （直接）左再帰性除去法 参　考 Aに関する左再帰性を取り除くためにまず， A → Aα1 |Aα2|・・・|Aαm|β1|β2|・・・|βn のようにまとめる． 上記の形を基に以下のように変形する． A → β1A’|β2A’|・・・|βnA’ A’ → α1 A’|α2A’|・・・|αmA’|ε パターンを覚えよう！ 言語プロセッサ2011

23 新たな文法規則 E → T E’ E’ → + T E’ | ε T → F T’ T’ → * F T’ | ε
F → ( E ) | id 言語プロセッサ2011

24 FirstとFollowを求めよ． E → T E’ E’ → + T E’ | ε T → F T’ T’ → * F T’ | ε
F → ( E ) | id 言語プロセッサ2011

25 First　＆　Follow （各自でやってみよう） ここが 正念場！ 言語プロセッサ2011

26 構文解析表を作成する （各自で作成してみよう） 言語プロセッサ2011

27 構文解析表 id + * ( ) $ E E → T E’ E → T E’ E’ E’ → + T E’ E’ →ε T T → F T’
F → id F → ( E ) 言語プロセッサ2011

28 動作手順 予測的構文解析系は、入力、スタック、構文解析表および出力からなる。
入力には構文解析対象の文字列があり、末尾に記号＄が添えられている。 スタックには底を示す記号＄が入っている。初期状態では開始記号が入っている。 構文解析表は配列 M[A,a] と書け、Aは非終端記号、aは終端記号か＄である。 言語プロセッサ2011

29 スタックから記号を１つポップする。それをXとする。また現在の入力記号の先頭をaとする。
X=a≠$ ならば、スタックからXをポップし、入力ポインタを１つ進める。 Xが非終端記号ならば、M[A,a]を調べる。 言語プロセッサ2011

30 M[A,a] = { X → UVW } ならば、スタックのXをWVU(Uが最上位)に書き換える。出力としてこの書き換え規則を印字する。
M[A,a]=error ならば回復ルーチンを起動する。 言語プロセッサ2011

31 動作のトレース 入力： id + id * id 落ち着いてトレースしよう！ 言語プロセッサ2011

32 動作のトレース スタック 入力 出力 $E id+id*id $E’T id+id*id E→TE’
スタック 入力 出力 $E id+id*id $E’T id+id*id E→TE’ $E’T’F id+id*id T→FT’ $E’T’id id+id*id F→id $E’T’ +id*id $E’ id*id T’→ε　 （以下省略） 言語プロセッサ2011

33 以上で構文解析の話は ほぼ終わりです． 引き続き練習を積み重ねてください． 用語を知ること 用語の意味を知り，自分で説明できるように．
なぜそのような用語が定義されているのかを考え理解する． 左再帰削除ができるように Factoringができるように Firstやfollowを自分で求められるように 構文解析表が作れるように 構文解析処理をトレースできるように 言語プロセッサ2011

34 参考情報 構文解析まで終われば、後は少し楽になります。 構文解析は解析の中でも難関部分で、 今日でも多くの研究がなされてます。
構文解析の次は意味解析（解析の最終段階）。 それ以後は合成の段階になります。 言語プロセッサ2011

35 Let’s call it a day! 今日はここまで！
寒くなったので健康には十分注意しましょう． 言語プロセッサ2011