東京工科大学 コンピュータサイエンス学部 亀田 弘之

Presentation on theme: "東京工科大学 コンピュータサイエンス学部 亀田 弘之"— Presentation transcript:

1 東京工科大学 コンピュータサイエンス学部 亀田 弘之
山場だよ！ 言語プロセッサ ー第6回目ー 構文解析（続き） 東京工科大学 コンピュータサイエンス学部 亀田　弘之

2 今日の内容 構文解析 LL(1)文法（復習） First集合（復習） Follow集合（復習） 構文解析表による構文解析法
予測的構文解析のモデル 構文解析表の作り方 動作　など 今日でマスターしてしまおう！ 今日は気合が必要だよ 言語プロセッサ2015 (東京工科大学CS学部)

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

4 (参考)迷路の例 一歩先を見れば，後戻りしないで済むといいのだが，… 言語プロセッサ2015 (東京工科大学CS学部)
（出典） （出典） 一歩先を見れば，後戻りしないで済むといいのだが，… 言語プロセッサ2015 (東京工科大学CS学部)

5 形式文法（復習) 文法 G=( N, V, S, P ), ただし、 N: 非終端記号の集合（構文構造記述用語集）
確認事項(常識) 文法 G=( N, V, S, P ), ただし、 N: 非終端記号の集合（構文構造記述用語集） V: 終端記号の集合（語彙) S: 開始記号 P: 書換え規則の集合 言語プロセッサ2015 (東京工科大学CS学部)

6 LL（１）文法の条件 文法における制限 構文解析方法
再確認事項 文法における制限 左再帰性の除去 （左再帰の書き換え規則を変形により削除する。 無限ループの回避を目的としている。） 括りだし(factoring) （バックトラックの回避を目的としている。） 構文解析方法 Top down 再帰呼び出し １文字先読み 言語プロセッサ2015 (東京工科大学CS学部)

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

8 （参考情報）　LL(1)の位置づけ 言語プロセッサ2015 (東京工科大学CS学部)

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

10 例 構文規則 Firstを求める様子 S → if ( E ) S else S | while ( E ) S | { S }
S → if ( ．．． より、 if ∈ First(S) S → while ( E ．．． より、 　　　　　　　while ∈ First(S) S → { S }　より、 　　　　　　　　　{ ∈ First(S) 言語プロセッサ2015 (東京工科大学CS学部)

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

12 練習問題 First(abcd) First(bα) 言語プロセッサ2015 (東京工科大学CS学部)

13 練習問題 ① S → S S + | S S * | a ② S → 0 S 1 | 0 1 First集合(First(S))を求めよ。
言語プロセッサ2015 (東京工科大学CS学部)

14 Follow集合 【意味】 Xの直後に現れる終端記号の集合 【定義】
最終確認事項 【定義】 Follow(X) = { a | a ∈ Vt , S =*=> …Xa… } 【意味】 Xの直後に現れる終端記号の集合 言語プロセッサ2015 (東京工科大学CS学部)

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

16 First集合とFollow集合 【定義】 1. First(α)={a | a ∈ Vt, α =*=> a… }
再確認事項 【定義】 1. First(α)={a | a ∈ Vt, α =*=> a… } ただし、 α =*=> ε ならば、 ε ∈ First(α) 2. Follow(X)={a | a ∈ Vt, S =*=> …Xa… } 言語プロセッサ2015 (東京工科大学CS学部)

17 First集合とFollow集合を求めてみよう！
演習（Let’s challenge!） First集合とFollow集合を求めてみよう！ ここが 正念場！ 言語プロセッサ2015 (東京工科大学CS学部)

18 確認問題 文法G1について答えよ。 G1: S → aBd B → bC C → c|ε 終端記号はどれか？ 非終端記号はどれか？
開始記号はどれか？ First集合を求めよ。 Follow集合を求めよ。 構文解析表を求めよ。 G1はLL(1)か？ G1: S → aBd B → bC C → c|ε 言語プロセッサ2015 (東京工科大学CS学部)

19 本番演習（Let’s challenge!）
次の文法を考える。FirstとFollowを求めよ． E → E + T | T T → T * F | F F → ( E ) | id First集合とFollow集合を求めてみよう！ ここが 正念場！ 言語プロセッサ2015 (東京工科大学CS学部)

20 まず、何をしますか？ 左再帰性がないかどうかを確認する。 ・どうやって確認する？ 左再帰性があれば、それを除去する。 ・どうやって除去する？
左再帰性がないかどうかを確認する。 　・どうやって確認する？ 左再帰性があれば、それを除去する。 　　　・どうやって除去する？ 言語プロセッサ2015 (東京工科大学CS学部)

21 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) | id } 教科書p.86より 言語プロセッサ2015 (東京工科大学CS学部)

22 First(E) = First(T) = First(F) = { (, id } First(E’) = { +, ε}
確認事項 First(E) = First(T) = First(F) = { (, id } First(E’) = { +, ε} First(T’) = { *, ε} Follow(E) = Follow(E’) = { ), $} Follow(T) = Follow(T’) = { +, ), $} Follow(F) = { +, *, ), $} 皆さんこうなりましか？ 言語プロセッサ2015 (東京工科大学CS学部)

23 これをもとに 構文解析へと進みましょう 話題 構文解析表 予測的構文解析法 実際のトレース など
実際のトレース　など 言語プロセッサ2015 (東京工科大学CS学部)

24 構文解析表による構文解析法 予測的構文解析のモデル 構文解析表の作り方 構文解析のアルゴリズム
言語プロセッサ2015 (東京工科大学CS学部)

25 予測的構文解析のモデル a + b $ X Y Z $ 入力 プログラム 出力 構文解析表 スタック
言語プロセッサ2015 (東京工科大学CS学部)

26 構文解析表の作り方 入力：　文法G 出力：　構文解析表M 手順：　（次のページ参照） 言語プロセッサ2015 (東京工科大学CS学部)

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

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

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

30 First　＆　Follow （もう一度自力でやってみよう） ここが 正念場！ 言語プロセッサ2015 (東京工科大学CS学部)

31 First(E) = First(T) = First(F) = { (, id } First(E’) = { +, ε}
再掲 First(E) = First(T) = First(F) = { (, id } First(E’) = { +, ε} First(T’) = { *, ε} Follow(E) = Follow(E’) = { ), $} Follow(T) = Follow(T’) = { +, ), $} Follow(F) = { +, *, ), $} こうでしたよね！ 言語プロセッサ2015 (東京工科大学CS学部)

32 構文解析表を作成する （各自で作成できるようになろう！） 言語プロセッサ2015 (東京工科大学CS学部)

33 構文解析表 id + * ( ) $ E E’ T T’ F 言語プロセッサ2015 (東京工科大学CS学部)

34 構文解析表の作り方 再掲 入力：　文法G 出力：　構文解析表M 手順：　（次のページ参照） 言語プロセッサ2015 (東京工科大学CS学部)

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

36 構文解析表 id + * ( ) $ E E → T E’ E → T E’ E’ E’ → + T E’ E’ →ε T T → F T’
F → id F → ( E ) 言語プロセッサ2015 (東京工科大学CS学部)

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

38 スタックから記号を１つポップする。それをXとする。また現在の入力記号の先頭をaとする。
X=a≠$ ならば、スタックからXをポップし、入力ポインタを１つ進める。 Xが非終端記号ならば、M[Ｘ,a]を調べる。 言語プロセッサ2015 (東京工科大学CS学部)

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

40 動作のトレース 入力： id + id * id 落ち着いてトレースしよう！ 言語プロセッサ2015 (東京工科大学CS学部)

41 動作のトレース スタック 入力 出力 $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’→ε　 （以下省略） 言語プロセッサ2015 (東京工科大学CS学部)

42 以上で構文解析の話しの 概要はほぼ終わりです．
引き続き練習を積み重ねてください． 用語の存在を知ること 用語の意味を知り，自分で説明できるように． なぜそのような用語が定義されているのかを考えて，自分の言葉で理解する． 左再帰削除ができるように Factoringができるように First集合やFollow集合を自分で求められるように 構文解析表が作れるように 構文解析処理をトレースできるように 言語プロセッサ2015 (東京工科大学CS学部)

43 参考情報 構文解析まで終われば、後は少し楽に なります。 構文解析は解析の中でも難関部分で、 今日でも多くの研究がなされてます。
構文解析の次は意味解析 （解析の最終段階）。 それ以後は合成の段階になります。 来週はここまでの総合演習をやります。 言語プロセッサ2015 (東京工科大学CS学部)

44 Let’s call it a day! 今日はここまで！
寒くなったので健康には十分注意しましょう． 言語プロセッサ2015 (東京工科大学CS学部)

45 復習（確認）問題 言語プロセッサ2015 (東京工科大学CS学部)

46 文法 左再帰性を除去しなさい． E → E + T | T T → T * F | F F → ( E ) | id
言語プロセッサ2015 (東京工科大学CS学部)

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

48 新たな文法規則 E → T E’ E’ → + T E’ | ε T → F T’ T’ → * F T’ | ε
F → ( E ) | id 言語プロセッサ2015 (東京工科大学CS学部)

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

50 確認問題（自宅で復習してみよう） G1: S → aBd B → bC C → c|ε 文法G1について答えよ。 終端記号はどれか？
非終端記号はどれか？ 開始記号はどれか？ First集合を求めよ。 Follow集合を求めよ。 構文解析表を求めよ G1はLL(1)か？ 入力 abd の構文解析動作を書き下しなさい。 G1: S → aBd B → bC C → c|ε 次回，授業中にみんなで確認しましょう！ 言語プロセッサ2015 (東京工科大学CS学部)

51 予告 次回から，簡単な言語処理系を作成します。 その後，意味解析，最適化の話をします。 言語プロセッサ2015 (東京工科大学CS学部)