言語処理系（７）金子敬一５基本的な構文解析技法５．１５．２５．３５．４５．５構文解析系移動還元構文解析演算子順位構文解析下降型構文解析予測的構文解析系５．４下降型構文解析系 • 下降型構文解析の例 S → c A d A → a b | a c a d S c A d ５．４下降型構文解析系 • 下降型構文解析の例 S → c A d A → a b | a c a d S A d c a b ５．４下降型構文解析系 • 下降型構文解析の例 S → c A d A → a b | a c a d S A d c a b ５．４下降型構文解析系 • 下降型構文解析の例 S → c A d A → a b | a c a d S A d c a b ５．４下降型構文解析系 • 下降型構文解析の例 S → c A d A → a b | a c a d S c A d a ５．４下降型構文解析系 • 下降型構文解析の例以下の問題点がある： −左再起性を持つ文法では，無限ループに陥る可能性 −後戻りが必要なため，大きなオーバヘッドの可能性 −代替の試行順序によって受理される言語が異なる可能性５．４下降型構文解析系 • 左再帰性の消去 G：文法，A ⇒ +Aaのとき，G：左再帰的１）すべてのA生成規則をまとめる A → A a1 | ... | A am | b1 | ... | bn ２）この規則を，以下の生成規則に置換 A → b1 A’ | ... | bn A’ A’ → a1 A’ | ... | am A’ | e ５．４下降型構文解析系 • 左再帰性の消去１）すべてのA生成規則をまとめる A → A a1 | ... | A am | b1 | ... | bn ２）この規則を，以下の生成規則に置換 A → b1 A’ | ... | bn A’ A’ → a1 A’ | ... | am A’ | e → T E’ E E → E + T | T E’ → + T E’ | e ５．４下降型構文解析系 • 左再帰性の消去 E → E + T | T T → E + T | T F → ( E ) | id E → T E’ → + T → F T’ → * F → ( E’ T E’ | e T’ F T’ | e E ) | id ５．４下降型構文解析系 • 1. 2. 3. 4. 5. 6. 7. 左再帰性の消去 Gの非終端記号をA1, A2, ..., Anとする A1の直接左再帰性を除去 A2にA1を代入 A2の直接左再帰性を除去 A3にA1, A2を代入 A3の直接左再帰性を除去 … ５．４下降型構文解析系 • 左再帰性の消去 S → A a | b A → A c | S d | e 1. Sに直接左再帰はない． 2. A → A c | A a d | b d | e 3. Aの左再帰性を除去して S → A a | b A → b d’ A’ | e A’ A’ → c A’ | a d A’ | e ５．４下降型構文解析系 • 再帰下降型構文解析再帰的，後戻りなし A → a1 | a2 | ... | an なるA規則で，入力記号aの代替が常に 1つに決まるならば，後戻りの必要なし５．４下降型構文解析系 • 左括り出し文 → if 条件 then 文 else 文 | while 条件 do 文 | begin 文の並び end 適文 → if 条件 then 文 else 文 | if 条件 then 文５．４下降型構文解析系 • 左括り出し文 → if 条件 then 文 else 文 | if 条件 then 文文 → if 条件 then 文文’ 文’ → else 文 | e 適５．４下降型構文解析系 • 遷移図 E → T E’ E’ → + T E’ | e T → F T’ T’ → * F T’ | e F → ( E ) | id E: E’: T: T’: F: T E’ + T F T’ * F ( E E’ e T’ )e id ５．４下降型構文解析系 • 遷移図 E:E: E’: T:T: T’: F:F: T + + E’ e F * * T’ e ( E T F E’ e T’ )e id ５．４下降型構文解析系 • 遷移図 E: T + e T: F * e ( E F: ) id ちょっと休憩（雑談）たほいや • 1. 2. 3. だんぼらぼ水中に大きな物を投げ入れた時の音。香川県で段々畑の意。なでしこに似た花をつける植物。春から夏にかけて海沿いの暖かい斜面に群生する。 4. ソラユリ科高山植物のひとつ。 5. だらしない人。たほいや • おっぱ 1. 小さな木の葉。転じて身分の軽い者のこと。 2. 東北地方で冬に肩に掛ける上衣。 3. 物事の最後。結末。 4. おおざっぱにまとめること。 5. 南米に生息するカミキリムシ。たほいや • 1. 2. 3. 4. 5. ねぎどのねぎを育てるための肥沃な土壌。田んぼにいる虫のこと。キリギリス・イナゴの異称。死者をねぎらうための部屋。ねぎどころ。米沢藩主上杉鷹山の愛称。たほいや • 1. 2. 3. 4. 5. したひ鍋などを熱するときの種火。死体。鎧のひどうしの下につける衣服。下火になることの古称人気が落ちる。赤く色づくこと。たほいや • 1. 2. 3. 4. 5. ぬじ色鮮やかな様子。左官屋の壁を塗る下地のこと。しったかぶり。「にじ」の古形。のじ。所有者のいる土地。たほいや • にこぽん 1. 天から授かる幸い。天運。 2. にこにこして相手の肩をぽんと叩き、親しそうにうちとけて人を懐柔する態度。 3. ニコチンとヒロポンの融合語。 4. 調子のよい人。にこりと笑って肩をたたくことから。 5. 物事が新鮮なさま。休憩おわり５．５予測的構文解析系 • 概要 a + b $ 入力 −入力 X Y −スタック Z −構文解析表 $ −出力スタックプログラム構文 M[X,a] 解析表出力次の動作を決定５．５予測的構文解析系 • 概要 $ $ プログラム構文 M[$,$] 解析表スタック入力出力受理５．５予測的構文解析系 • 概要 a + b $ a Y Z $ スタックプログラム構文 M[a,a] 解析表入力出力５．５予測的構文解析系 • 概要 U V X W Y Z $ スタック a + b $ プログラム構文 M[X,a] 解析表入力出力 X → U V W ５．５予測的構文解析系 • 動作 id E E’ T T’ E→T E’ F F →id + E → T E’ → + T → F T’ → * F → ( E’ T E’ | e T’ F T’ | e E ) | id * ( ) $ E’→e E’→e T’→e T’→e E→T E’ E’→+ T E’ T→F T’ T→F T’ T’→e T’→* F T’ F →(E) ５．５予測的構文解析系 • 動作 $ E T’ E’ + T id F id E E’ T T’ E→T E’ F F →id + id + id * id $ * ( ) $ E’→e E’→e T’→e T’→e E→T E’ E’→+ T E’ T→F T’ T→F T’ T’→e T’→* F T’ F →(E) ５．５予測的構文解析系 • 動作 $ E’ T’ id F * id E E’ T T’ E→T E’ F F →id + id * id $ * ( ) $ E’→e E’→e T’→e T’→e E→T E’ E’→+ T E’ T→F T’ T→F T’ T’→e T’→* F T’ F →(E) ５．５予測的構文解析系 •FIRSTとFOLLOW −任意の文法記号列a, FIRST(a): a から導出可能な文字列の先頭の終端記号の集合 −任意の文法記号列A, FOLLOW(A): 文形式においてAのすぐ右に出現しうる終端記号の集合（含む$）５．５予測的構文解析系 •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) ５．５予測的構文解析系 •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) ５．５予測的構文解析系 •構文解析表の構成１）各生成規則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を記入５．５予測的構文解析系 • LL(1)文法構文解析表のどの欄も多重定義されていない文法５．５予測的構文解析系 • LL(1)文法の必要十分条件 A → a | bに対して， −任意の終端記号a, aとbのうち高々一方がaで始まる文字列を導出 −aとbのうち高々一方が空列を導出 −b⇒*eならばaはFOLLOW(A)に含まれる終端記号で始まる文字列を導出しない