言語処理系（６） 金子敬一

練習問題 ４．１ リスト構造は以下のように定義される． Λは，空リスト aは，リスト構造 練習問題　４．１ リスト構造は以下のように定義される． Λは，空リスト aは，リスト構造 l1, l2, ..., lk (k>0)がリスト構造ならば (l1, l2, ..., lk)もリスト構造 a) リスト構造に対する文脈自由文法を作れ b) (((a, a), Λ, (a)), a)に対する解析木を書け

練習問題 ４．１ リスト構造は以下のように定義される． Λは，空リスト aは，リスト構造 練習問題　４．１ リスト構造は以下のように定義される． Λは，空リスト aは，リスト構造 l1, l2, ..., lk (k>0)がリスト構造ならば (l1, l2, ..., lk)もリスト構造 a) リスト構造に対する文脈自由文法を作れ L = Λ | a | ( L’ ) L’ = L | L, L’

練習問題 ４．１ b)(((a, a), Λ, (a)), a)に対する解析木を書け ( L’ ) L , L’ L ( L’ ) L , 練習問題　４．１ b)(((a, a), Λ, (a)), a)に対する解析木を書け ( L’ ) L , L’ L ( L’ ) L , L’ Λ L L , L’ a L ( L’ ) ( L’ ) L a L L , L’ a a ( L’ ) L , L’

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

５．１　構文解析系 構文解析系 文脈自由文法G，文字列wに対して wがGの文ならば解析木を返す さもなくば，誤りメッセージを生成する

５．１ 構文解析系 上昇型構文解析 解析木を葉から根に向かって構成 例．移動還元構文解析 入力記号を移動しつつ，スタックへ積む ５．１　構文解析系 上昇型構文解析 解析木を葉から根に向かって構成 例．移動還元構文解析 入力記号を移動しつつ，スタックへ積む スタックの上位が生成規則の右辺に対応すると，左辺に置換（還元操作）

５．１　構文解析系 下降型構文解析 解析木を根から葉に向かって構成 例．再帰下降型構文解析 予測的構文解析系 LL構文解析系

５．１　構文解析系 解析木の表現 直接表現：リスト構造による表現など 間接表現：導出に用いる生成規則列など

５．１　構文解析系 左文形式と右文形式 最左導出： wAγ　⇒　wδγ lm 左文形式 S ⇒*α lm

５．１　構文解析系 解析木と導出 文wに対する解析木において，最左の非終端記号に対応するノードの子コードのラベルによる置換を繰り返す．

５．１ 構文解析系 解析木と導出 （１） S → if C then S （２） S → if C then S else S ５．１　構文解析系 解析木と導出 （１） S → if C then S （２） S → if C then S else S （３） S → a （４） C → b

５．１　構文解析系 解析木と導出 S if C S then b if C then S else S b a a

５．１　構文解析系 解析木と導出 S if C S then S ⇒ if C then S

５．１　構文解析系 解析木と導出 S S if C then b if C then S ⇒ if b then S

５．１ 構文解析系 S S if C then b if C then S else S 解析木と導出 ５．１　構文解析系 解析木と導出 S S if C then b if C then S else S if b then S ⇒ if b then if C then S else S

５．１ 構文解析系 S S if C then b if C then S else S b 解析木と導出 ５．１　構文解析系 解析木と導出 S S if C then b if C then S else S b if b then if C then S else S　　　⇒ if b then if b then S else S

５．１ 構文解析系 S if C S then b if C then S else S b a 解析木と導出 ５．１　構文解析系 解析木と導出 S if C S then b if C then S else S b a if b then if b then S else S　　　⇒ if b then if b then a else S

５．１ 構文解析系 S if C S then b if C then S else S b a a 解析木と導出 ５．１　構文解析系 解析木と導出 S if C S then b if C then S else S b a a if b then if b then a else S　　　⇒ if b then if b then a else a

５．２　移動還元構文解析 移動と還元 S → a A c B e A →　A b | b B → d a b b c d e 文法 文字列

５．２　移動還元構文解析 移動と還元 S → a A c B e A →　A b | b B → d a b b c d e 文法 文字列

５．２ 移動還元構文解析 S → a A c B e A → A b | b B → d a b b c d e 移動と還元 文法 A ５．２　移動還元構文解析 移動と還元 S → a A c B e A →　A b | b B → d a b b c d e 文法 A 文字列

５．２ 移動還元構文解析 S → a A c B e A → A b | b B → d a b b c d e 移動と還元 文法 A ５．２　移動還元構文解析 移動と還元 S → a A c B e A →　A b | b B → d a b b c d e 文法 A 文字列

５．２ 移動還元構文解析 S → a A c B e A → A b | b B → d a b b c d e 移動と還元 文法 A ５．２　移動還元構文解析 移動と還元 S → a A c B e A →　A b | b B → d a b b c d e 文法 A 文字列

５．２ 移動還元構文解析 S → a A c B e A → A b | b B → d a b b c d e 移動と還元 文法 A B ５．２　移動還元構文解析 移動と還元 S → a A c B e A →　A b | b B → d a b b c d e 文法 A B 文字列

５．２ 移動還元構文解析 S → a A c B e A → A b | b B → d a b b c d e 移動と還元 文法 S A ５．２　移動還元構文解析 移動と還元 S → a A c B e A →　A b | b B → d a b b c d e 文法 S A B 文字列

５．２ 移動還元構文解析 a b b c d e ⇒ a A b c d e ⇒ a A c d e ⇒ a A c B e ⇒ S ５．２　移動還元構文解析 最右導出 移動と還元 a b b c d e ⇒ a A b c d e ⇒ a A c d e ⇒ a A c B e ⇒ S A → b A → A b B → d S → a A b B e

５．２ 移動還元構文解析 a b b c d e ⇒ a A b c d e ⇒ a A c d e ⇒ a A c B e ⇒ S 把手 ５．２　移動還元構文解析 把手 a b b c d e ⇒ a A b c d e ⇒ a A c d e ⇒ a A c B e ⇒ S 文法が曖昧でないならば，その 文法のすべての右文形式は， ちょうど１つの把手をもつ

５．２ 移動還元構文解析 E ⇒ E + E ⇒ E + E * E ⇒ E + E * id ⇒ E + id * id ５．２　移動還元構文解析 把手 E ⇒ E + E 　 ⇒ E + E * E 　 ⇒ E + E * id 　 ⇒ E + id * id 　 ⇒ id + id * id E ⇒ E * E 　 ⇒ E * id (1) E → E + E (2) E → E * E (3) E → ( E ) (4) E → id

５．２ 移動還元構文解析 把手の刈取り 把手を対応する左辺で置換する操作 右文形式 把手 還元用生成規則 id + id * id id ５．２　移動還元構文解析 把手の刈取り 把手を対応する左辺で置換する操作 右文形式 把手 還元用生成規則 id + id * id id E → id E + id * id E + E * id E + E * E E * E E → E * E E + E E → E + E E

還元 移動 移動 還元 移動 ５．２ 移動還元構文解析 移動還元構文解析のスタックによる実現 id + id + * $ E E スタック ５．２　移動還元構文解析 移動還元構文解析のスタックによる実現 スタック id + 入力バッファ id + * $ 還元 移動 移動 還元 移動 E E

還元 移動 還元 ５．２ 移動還元構文解析 移動還元構文解析のスタックによる実現 id * E + id + * $ E スタック ５．２　移動還元構文解析 移動還元構文解析のスタックによる実現 スタック id * E + 入力バッファ id + * $ E 還元 移動 還元

５．２　移動還元構文解析 移動還元構文解析のスタックによる実現 スタック E * + 入力バッファ id + * $ 受理 還元

５．２　移動還元構文解析 解析木の構成 スタック id + 入力バッファ id + * $ E E E id + id E

５．２　移動還元構文解析 解析木の構成 スタック id * E + 入力バッファ id + * $ E E E E id + id * id

５．２　移動還元構文解析 解析木の構成 スタック E * + 入力バッファ id + * $ E E E E E id + id * id

ちょっと休憩 （雑談）

魚偏の漢字 鮪 まぐろ 鰯 いわし 鯵 あじ 鰆 さわら 鰍 かじか 鰈 かれい 鯨 くじら 鯛 たい 鱈 たら 鮫 さめ 鯖 さば 鮪　まぐろ 鰯　いわし 鯵　あじ 鰆　さわら 鰍　かじか 鰈　かれい 鯨　くじら 鯛　たい 鱈　たら 鮫　さめ 鯖　さば 鰊　にしん 鰤　ぶり 鯔　ぼら 鰻　うなぎ 鯰　なまず 鯉　こい 鮒　ふな

休憩おわり

５．３　演算子順位構文解析 演算子文法 隣接する非終端記号を持たない文法 効率的な移動還元構文解析系を生成

５．３ 演算子順位構文解析 演算子文法の例 E → E A E | ( E ) | - E | id ５．３　演算子順位構文解析 演算子文法の例 E → E A E | ( E ) | - E |　id A → + | - | * | / | ^ 演算子文法でない E → E + E | E - E | E * E | E / E | E ^ E | ( E ) | - E |　id

５．３ 演算子順位構文解析 順位関係 終端記号間の３種類の関係：≅, ≲, ≳ 定め方には２通り 演算子の結合性と優先度に基づく ５．３　演算子順位構文解析 順位関係 終端記号間の３種類の関係：≅, ≲, ≳ 定め方には２通り 演算子の結合性と優先度に基づく 曖昧さのない文法から機械的に

５．３ 演算子順位構文解析 把手 ≲ ≅ ≳ 演算子順位関係の使用 右分形式の把手の左端を≲で，右端を≳で区切る ５．３　演算子順位構文解析 演算子順位関係の使用 右分形式の把手の左端を≲で，右端を≳で区切る E + E * E / E + E 把手 ≲ ≅ ≳

５．３ 演算子順位構文解析 演算子順位関係の使用 ０）非終端記号をすべて除去 １）左端から走査して最左の≳を見つける ５．３　演算子順位構文解析 演算子順位関係の使用 ０）非終端記号をすべて除去 １）左端から走査して最左の≳を見つける ２）次に左端へ走査して，≲を見つける 　３）≲と≳で囲まれた部分に，間や両端に高々１個の非終端記号を付加して把手を得る

５．３ 演算子順位構文解析 結合性と順位からの演算子順位関係 １）優先度q1>q2：q1 ≳ q2 ，q2 ≲ q1 ５．３　演算子順位構文解析 結合性と順位からの演算子順位関係 １）優先度q1>q2：q1 ≳ q2 ，q2 ≲ q1 ２）優先度q1=q2かつ右結合：q2 ≲ q1 ，q1 ≲ q2 　 優先度q1=q2かつ左結合：q1 ≳ q2 ，q2 ≳ q1 ３）q ≲ id, id ≳ q, q ≲ (, ( ≲ q, ) ≳ q, q ≳ ), $ ≳ q, q ≳ $とする．( ≅ ), $ ≲ (, $ ≲ id, ( ≲ (, id ≳ $, ) ≳ $, ( ≲ id, id ≳ ), ) ≳ )とする

３ ３ ３ ２ １ １ ２ １ ５．３ 演算子順位構文解析 １ ２ 結合性と順位からの演算子順位関係 ^ 右結合的 * / 左結合的 ５．３　演算子順位構文解析 結合性と順位からの演算子順位関係 + - * / ^ id ( ) $ > < = ^ 右結合的 * / 左結合的 + - 左結合的 ２ １ １ ３ １ ２ １ ２ ３ ３

５．３　演算子順位構文解析 単項演算子の扱い ２項演算子にないもの：例えば￢に対しては，すべての演算子qに対して，q ≲ ￢とし， ￢の優先順位がqより高ければ，￢ ≳ qとし，低ければ￢ ≲ qとする． ２項演算子にもある単項演算子は，字句解析系で２項のものと区別する必要

５．３ 演算子順位構文解析 演算子順位文法 G: 生成規則の右辺がeでない演算子文法 ５．３　演算子順位構文解析 演算子順位文法 G: 生成規則の右辺がeでない演算子文法 １）aabbgなる右辺，bはeか1つの非終端記号：a ≅ b ２）非終端記号A, aaAbなる右辺，A⇒+gbd, gがeか１つの非終端記号：a ≲ b ３）非終端記号A, aAbbなる右辺, A⇒+gad, dがeか１つの非終端記号：a ≳ b

５．３　演算子順位構文解析 演算子順位文法 この規則で生成した順位関係が互いに素である演算子文法

５．３ 演算子順位構文解析 演算子順位文法 E → E + E | E * E | ( E ) | id ５．３　演算子順位構文解析 演算子順位文法 E → E + E | E * E | ( E ) | id ２）非終端記号A, aaAbなる右辺，A⇒+gbd, gがeか１つの非終端記号：a ≲ b E + Eなる右辺，E⇒+E * E：+ ≲ * ３）非終端記号A, aAbbなる右辺, A⇒+gad, dがeか１つの非終端記号：a ≳ b E + Eなる右辺，E⇒+E * E：+ ≳ *

５．３ 演算子順位構文解析 演算子順位文法 E → E + T | T E → T + F | F F → ( E )| id + * ( ５．３　演算子順位構文解析 + * ( ) id $ > < = 演算子順位文法 E → E + T | T E →　T + F | F F → ( E )| id

LEADING()およびTRAILING()については省略 ５．３　演算子順位構文解析 演算子順位構文解析アルゴリズム LEADING()およびTRAILING()については省略

５．３ 演算子順位構文解析 演算子順位構文解析アルゴリズム repeat forever begin ５．３　演算子順位構文解析 演算子順位構文解析アルゴリズム repeat forever begin if スタックが$ and 入力が$ then 受理してbreak; aをスタック最上段の終端記号, b入力記号; if a ≲ b or a ≅ b then bをスタックに else if a ≳ b then /* 還元動作 */ repeat スタックからおろす until (スタックの最上段の終端記号) ≲ (最後にスタックからおろした終端記号) else 誤り訂正ルーチンを呼び出す end

５．３　演算子順位構文解析 演算子順位構文解析アルゴリズム $ id + id $ ≲

５．３　演算子順位構文解析 演算子順位構文解析アルゴリズム $ id E + id $ ≲ ≲ ≳

５．３　演算子順位構文解析 演算子順位構文解析アルゴリズム $ E + id $ ≲ ≳

５．３　演算子順位構文解析 演算子順位構文解析アルゴリズム $ E + id E $ ≳ ≲

５．３　演算子順位構文解析 順位関数 全終端記号間の表を持つのは重い 　順位関数