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

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

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

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

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

4 練習問題 ４．１ 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’

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

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

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

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

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

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

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

12 ５．１ 構文解析系 解析木と導出 （１） 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

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

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

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

16 ５．１ 構文解析系 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

17 ５．１ 構文解析系 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

18 ５．１ 構文解析系 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

19 ５．１ 構文解析系 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

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

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

22 ５．２ 移動還元構文解析 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 文字列

23 ５．２ 移動還元構文解析 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 文字列

24 ５．２ 移動還元構文解析 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 文字列

25 ５．２ 移動還元構文解析 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 文字列

26 ５．２ 移動還元構文解析 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 文字列

27 ５．２ 移動還元構文解析 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

28 ５．２ 移動還元構文解析 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 文法が曖昧でないならば，その 文法のすべての右文形式は， ちょうど１つの把手をもつ

29 ５．２ 移動還元構文解析 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

30 ５．２ 移動還元構文解析 把手の刈取り 把手を対応する左辺で置換する操作 右文形式 把手 還元用生成規則 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

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

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

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

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

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

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

37 ちょっと休憩 （雑談）

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

39 休憩おわり

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

41 ５．３ 演算子順位構文解析 演算子文法の例 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

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

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

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

45 ５．３ 演算子順位構文解析 結合性と順位からの演算子順位関係 １）優先度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 ≳ ), ) ≳ )とする

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

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

48 ５．３ 演算子順位構文解析 演算子順位文法 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

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

50 ５．３ 演算子順位構文解析 演算子順位文法 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：+ ≳ *

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

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

53 ５．３ 演算子順位構文解析 演算子順位構文解析アルゴリズム 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

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

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

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

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

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