言語処理系（７） 金子敬一.

Presentation on theme: "言語処理系（７） 金子敬一."— Presentation transcript:

1 言語処理系（７） 金子敬一

2 ５ 基本的な構文解析技法 ５．１ 構文解析系 ５．２ 移動還元構文解析 ５．３ 演算子順位構文解析 ５．４ 下降型構文解析
５　基本的な構文解析技法 ５．１　構文解析系 ５．２　移動還元構文解析 ５．３　演算子順位構文解析 ５．４　下降型構文解析 ５．５　予測的構文解析系

3 ５．４　下降型構文解析系 下降型構文解析の例 S → c A d A → a b | a S c a d c A d

4 ５．４　下降型構文解析系 下降型構文解析の例 S → c A d A → a b | a S c a d c A d a b

5 ５．４　下降型構文解析系 下降型構文解析の例 S → c A d A → a b | a S c a d c A d a b

6 ５．４　下降型構文解析系 下降型構文解析の例 S → c A d A → a b | a S c a d c A d a b

7 ５．４　下降型構文解析系 下降型構文解析の例 S → c A d A → a b | a S c a d c A d d a

8 ５．４ 下降型構文解析系 下降型構文解析の例 以下の問題点がある： 左再起性を持つ文法では，無限ループに陥る可能性
５．４　下降型構文解析系 下降型構文解析の例 以下の問題点がある： 左再起性を持つ文法では，無限ループに陥る可能性 後戻りが必要なため，大きなオーバヘッドの可能性 代替の試行順序によって受理される言語が異なる可能性

9 ５．４ 下降型構文解析系 左再帰性の消去 G：文法，A ⇒ +Aaのとき，G：左再帰的 １）すべてのA生成規則をまとめる
５．４　下降型構文解析系 左再帰性の消去 G：文法，A ⇒ +Aaのとき，G：左再帰的 １）すべてのA生成規則をまとめる A → A a1 | ... | A am | b1 | ... | bn ２）この規則を，以下の生成規則に置換 A → b1 A’ | ... | bn A’ A’ → a1 A’ | ... | am A’ | e

10 ５．４ 下降型構文解析系 左再帰性の消去 １）すべてのA生成規則をまとめる
５．４　下降型構文解析系 左再帰性の消去 １）すべてのA生成規則をまとめる A → A a1 | ... | A am | b1 | ... | bn ２）この規則を，以下の生成規則に置換 A → b1 A’ | ... | bn A’ A’ → a1 A’ | ... | am A’ | e E → T E’ E’ → + T E’ | e E → E + T | T

11 ５．４ 下降型構文解析系 左再帰性の消去 E → T E’ E’ → + T E’ | e E → E + T | T T → F T’
５．４　下降型構文解析系 左再帰性の消去 E → T E’ E’ → + T E’ | e T → F T’ T’ → * F T’ | e F → ( E ) | id E → E + T | T T → E + T | T F → ( E ) | id

12 ５．４ 下降型構文解析系 左再帰性の消去 Gの非終端記号をA1, A2, ..., Anとする A1の直接左再帰性を除去 A2にA1を代入
５．４　下降型構文解析系 左再帰性の消去 Gの非終端記号をA1, A2, ..., Anとする A1の直接左再帰性を除去 A2にA1を代入 A2の直接左再帰性を除去 A3にA1, A2を代入 A3の直接左再帰性を除去 …

13 ５．４ 下降型構文解析系 左再帰性の消去 S → A a | b A → A c | S d | e Sに直接左再帰はない．
５．４　下降型構文解析系 左再帰性の消去 S → A a | b A → A c | S d | e Sに直接左再帰はない． A → A c | A a d | b d | e Aの左再帰性を除去して A → b d’ A’ | e A’ A’ → c A’ | a d A’ | e

14 ５．４ 下降型構文解析系 再帰下降型構文解析 再帰的，後戻りなし A → a1 | a2 | ... | an
５．４　下降型構文解析系 再帰下降型構文解析 再帰的，後戻りなし A → a1 | a2 | ... | an なるA規則で，入力記号aの代替が常に1つに決まるならば，後戻りの必要なし

15 適 ５．４ 下降型構文解析系 左括り出し 文 → if 条件 then 文 else 文 | while 条件 do 文
５．４　下降型構文解析系 左括り出し 文 → if 条件 then 文 else 文 | while 条件 do 文 | begin 文の並び end | if 条件 then 文 適

16 適 ５．４ 下降型構文解析系 左括り出し 文 → if 条件 then 文 else 文 | if 条件 then 文
５．４　下降型構文解析系 左括り出し 文 → if 条件 then 文 else 文 | if 条件 then 文 文 → if 条件 then 文 文’ 文’ → else 文 | e 適

17 ５．４ 下降型構文解析系 遷移図 E: E’: T: T’: F: T + F * ( E’ T’ E ) e id E → T E’
５．４　下降型構文解析系 遷移図 E: E’: T: T’: F: T + F * ( E’ T’ E ) e id E → T E’ E’ → + T E’ | e T → F T’ T’ → * F T’ | e F → ( E ) | id

18 ５．４ 下降型構文解析系 遷移図 E: E’: T: T’: F: T + F * ( E’ T’ E ) e id E: T: F: T
５．４　下降型構文解析系 遷移図 E: E’: T: T’: F: T + F * ( E’ T’ E ) e id E: T: F: T F ( e E ) id + *

19 ５．４　下降型構文解析系 遷移図 T e + E: F e * T: ( E ) id F:

20 ちょっと休憩 （雑談）

21 たほいや だんぼらぼ 水中に大きな物を投げ入れた時の音。 香川県で段々畑の意。
なでしこに似た花をつける植物。春から夏にかけて海沿いの暖かい斜面に群生する。 ソラユリ科　高山植物のひとつ。 だらしない人。

22 たほいや おっぱ 小さな木の葉。転じて身分の軽い者のこと。 東北地方で冬に肩に掛ける上衣。 物事の最後。結末。 おおざっぱにまとめること。
南米に生息するカミキリムシ。

23 たほいや ねぎどの ねぎを育てるための肥沃な土壌。 田んぼにいる虫のこと。 キリギリス・イナゴの異称。
死者をねぎらうための部屋。ねぎどころ。 米沢藩主　上杉鷹山の愛称。

24 たほいや したひ 鍋などを熱するときの種火。 死体。 鎧のひどうしの下につける衣服。 下火になることの古称　人気が落ちる。 赤く色づくこと。

25 たほいや ぬじ 色鮮やかな様子。 左官屋の壁を塗る下地のこと。 しったかぶり。 「にじ」の古形。のじ。 所有者のいる土地。

26 たほいや にこぽん 天から授かる幸い。天運。 にこにこして相手の肩をぽんと叩き、親しそうにうちとけて人を懐柔する態度。
ニコチンとヒロポンの融合語。 調子のよい人。にこりと笑って肩をたたくことから。 物事が新鮮なさま。

27 休憩おわり

28 ５．５ 予測的構文解析系 概要 入力 a + b $ 入力 スタック X 構文解析表 Y プログラム 出力 Z 出力 $ 構 文
５．５　予測的構文解析系 概要 入力 スタック 構文解析表 出力 入力 a + b $ X Y Z $ プログラム 出力 構　文 解析表 M[X,a] スタック 次の動作を決定

29 ５．５　予測的構文解析系 概要 入力 $ $ プログラム 出力 構　文 解析表 受理 M[$,$] スタック

30 ５．５　予測的構文解析系 概要 入力 a + b $ a Y Z $ プログラム 出力 構　文 解析表 M[a,a] スタック

31 ５．５ 予測的構文解析系 U 概要 入力 V a + b $ W X Y プログラム Z 出力 $ 構 文 M[X,a] 解析表 スタック
５．５　予測的構文解析系 U V W 概要 入力 a + b $ X Y Z $ プログラム 出力 構　文 解析表 M[X,a] スタック X → U V W

32 ５．５ 予測的構文解析系 E → T E’ 動作 E’ → + T E’ | e T → F T’ T’ → * F T’ | e
５．５　予測的構文解析系 E → T E’ E’ → + T E’ | e T → F T’ T’ → * F T’ | e F → ( E ) | id 動作 id + * ( ) $ E E→T E’ E’ E’→+ T E’ E’→e T T→F T’ T’ T’→e T’→* F T’ F F →id F →(E)

33 ５．５ 予測的構文解析系 動作 $ E’ T + id * $ E’ T’ F id * $ E’ T’ + id * $ E’ T id
５．５　予測的構文解析系 動作 $ E’ T + id * $ E’ T’ F id * $ E’ T’ + id * $ E’ T id * $ E’ T’ F id + * $ E id + * $ E’ T’ id + * $ E’ T id + * $ E’ + id * id + * ( ) $ E E→T E’ E’ E’→+ T E’ E’→e T T→F T’ T’ T’→e T’→* F T’ F F →id F →(E)

34 ５．５ 予測的構文解析系 動作 $ E’ T’ id $ E’ T’ $ $ E’ T’ F id $ E’ $ E’ T’ * id $
５．５　予測的構文解析系 動作 $ E’ T’ id $ E’ T’ $ $ E’ T’ F id $ E’ $ E’ T’ * id $ E’ T’ id * $ E’ T’ F id * $ E’ T’ F * id id + * ( ) $ E E→T E’ E’ E’→+ T E’ E’→e T T→F T’ T’ T’→e T’→* F T’ F F →id F →(E)

35 ５．５ 予測的構文解析系 FIRSTとFOLLOW 任意の文法記号列a, FIRST(a): aから導出可能な文字列の先頭の終端記号の集合
５．５　予測的構文解析系 FIRSTとFOLLOW 任意の文法記号列a, FIRST(a): aから導出可能な文字列の先頭の終端記号の集合 任意の文法記号列A, FOLLOW(A): 文形式においてAのすぐ右に出現しうる終端記号の集合（含む$）

36 ５．５ 予測的構文解析系 FIRSTの求め方 X：任意の文法記号，FIRST(X)を以下のように求める
５．５　予測的構文解析系 FIRSTの求め方 　X：任意の文法記号，FIRST(X)を以下のように求める １）X：終端記号，FIRST(X)={X} ２）X：非終端，X→a a, a FIRST(X) ３）X→Y1 Y2 ... Yk, Y1 Y2 ... Yi-1⇒+eならばFIRST(Yi)-{e} FIRST(X) Y1 Y2 ... Yk⇒*eならば， e FIRST(X)

37 ５．５ 予測的構文解析系 FOLLOWの求め方 A：任意の非終端記号，FOLLOW(A)を 以下のように求める
５．５　予測的構文解析系 FOLLOWの求め方 　A：任意の非終端記号，FOLLOW(A)を 以下のように求める １）S：出発記号，$ FOLLOW(S) ２）A→a B b, b = e, FIRST(b)-{e} FOLLOW(B) ３）A→a Bまたは， A→a B bかつe FIRST(b), FOLLOW(A) FOLLOW(B)

38 ５．５ 予測的構文解析系 構文解析表の構成 １）各生成規則A→aに対し，２，３を実行
５．５　予測的構文解析系 構文解析表の構成 １）各生成規則A→aに対し，２，３を実行 ２）各終端記号a FIRST(a)に対して， M[A,a]にA→aを記入 ３）e FIRST(a)ならば, 各終端記号b FOLLOW(A)に対して，M[A,b]にA→aを記入．e FIRST(a)かつ$ FOLLOW (A)ならばM[A,b]にA→aを記入 ４）空欄にerrorを記入

39 ５．５　予測的構文解析系 LL(1)文法 構文解析表のどの欄も多重定義されていない文法

40 ５．５ 予測的構文解析系 任意の終端記号a, aとbのうち高々一方がaで始まる文字列を導出 aとbのうち高々一方が空列を導出
５．５　予測的構文解析系 LL(1)文法の必要十分条件 A → a | bに対して， 任意の終端記号a, aとbのうち高々一方がaで始まる文字列を導出 aとbのうち高々一方が空列を導出 b⇒*eならばaはFOLLOW(A)に含まれる終端記号で始まる文字列を導出しない