Presentation is loading. Please wait.

Presentation is loading. Please wait.

言語処理系(6) 金子敬一.

Similar presentations


Presentation on theme: "言語処理系(6) 金子敬一."— Presentation transcript:

1 言語処理系(6) 金子敬一

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

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

4 練習問題 4.1 b)(((a, a), Λ, (a)), a)に対する解析木を書け ( L’ ) L , L’ L ( L’ ) L ,
練習問題 4.1 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 5 基本的な構文解析技法 5.1 構文解析系 5.2 移動還元構文解析 5.3 演算子順位構文解析 5.4 下降型構文解析
5 基本的な構文解析技法 5.1 構文解析系 5.2 移動還元構文解析 5.3 演算子順位構文解析 5.4 下降型構文解析 5.5 予測的構文解析系

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

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

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

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

10 5.1 構文解析系 左文形式と右文形式 最左導出: wAγ ⇒ wδγ lm 左文形式 S ⇒*α lm

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

12 5.1 構文解析系 解析木と導出 (1) S → if C then S (2) S → if C then S else S
5.1 構文解析系 解析木と導出 (1) S → if C then S (2) S → if C then S else S (3) S → a (4) C → b

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

14 5.1 構文解析系 解析木と導出 S if C S then S ⇒ if C then S

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

16 5.1 構文解析系 S S if C then b if C then S else S 解析木と導出
5.1 構文解析系 解析木と導出 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 5.1 構文解析系 S S if C then b if C then S else S b 解析木と導出
5.1 構文解析系 解析木と導出 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 5.1 構文解析系 S if C S then b if C then S else S b a 解析木と導出
5.1 構文解析系 解析木と導出 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 5.1 構文解析系 S if C S then b if C then S else S b a a 解析木と導出
5.1 構文解析系 解析木と導出 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 5.2 移動還元構文解析 移動と還元 S → a A c B e A → A b | b B → d a b b c d e 文法 文字列

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

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

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

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

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

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

27 5.2 移動還元構文解析 a b b c d e ⇒ a A b c d e ⇒ a A c d e ⇒ a A c B e ⇒ S
5.2 移動還元構文解析 最右導出 移動と還元 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 5.2 移動還元構文解析 a b b c d e ⇒ a A b c d e ⇒ a A c d e ⇒ a A c B e ⇒ S 把手
5.2 移動還元構文解析 把手 a b b c d e ⇒ a A b c d e ⇒ a A c d e ⇒ a A c B e ⇒ S 文法が曖昧でないならば,その 文法のすべての右文形式は, ちょうど1つの把手をもつ

29 5.2 移動還元構文解析 E ⇒ E + E ⇒ E + E * E ⇒ E + E * id ⇒ E + id * id
5.2 移動還元構文解析 把手 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 5.2 移動還元構文解析 把手の刈取り 把手を対応する左辺で置換する操作 右文形式 把手 還元用生成規則 id + id * id id
5.2 移動還元構文解析 把手の刈取り 把手を対応する左辺で置換する操作 右文形式 把手 還元用生成規則 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 還元 移動 移動 還元 移動 5.2 移動還元構文解析 移動還元構文解析のスタックによる実現 id + id + * $ E E スタック
5.2 移動還元構文解析 移動還元構文解析のスタックによる実現 スタック id + 入力バッファ id + * $ 還元 移動 移動 還元 移動 E E

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

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

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

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

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

37 ちょっと休憩 (雑談)

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

39 休憩おわり

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

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

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

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

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

45 5.3 演算子順位構文解析 結合性と順位からの演算子順位関係 1)優先度q1>q2:q1 ≳ q2 ,q2 ≲ q1
5.3 演算子順位構文解析 結合性と順位からの演算子順位関係 1)優先度q1>q2:q1 ≳ q2 ,q2 ≲ q1 2)優先度q1=q2かつ右結合:q2 ≲ q1 ,q1 ≲ q2   優先度q1=q2かつ左結合:q1 ≳ q2 ,q2 ≳ q1 3)q ≲ id, id ≳ q, q ≲ (, ( ≲ q, ) ≳ q, q ≳ ), $ ≳ q, q ≳ $とする.( ≅ ), $ ≲ (, $ ≲ id, ( ≲ (, id ≳ $, ) ≳ $, ( ≲ id, id ≳ ), ) ≳ )とする

46 3 3 3 2 1 1 2 1 5.3 演算子順位構文解析 1 2 結合性と順位からの演算子順位関係 ^ 右結合的 * / 左結合的
5.3 演算子順位構文解析 結合性と順位からの演算子順位関係 + - * / ^ id ( ) $ > < = ^ 右結合的 * / 左結合的 + - 左結合的

47 5.3 演算子順位構文解析 単項演算子の扱い 2項演算子にないもの:例えば¬に対しては,すべての演算子qに対して,q ≲ ¬とし, ¬の優先順位がqより高ければ,¬ ≳ qとし,低ければ¬ ≲ qとする. 2項演算子にもある単項演算子は,字句解析系で2項のものと区別する必要

48 5.3 演算子順位構文解析 演算子順位文法 G: 生成規則の右辺がeでない演算子文法
5.3 演算子順位構文解析 演算子順位文法 G: 生成規則の右辺がeでない演算子文法 1)aabbgなる右辺,bはeか1つの非終端記号:a ≅ b 2)非終端記号A, aaAbなる右辺,A⇒+gbd, gがeか1つの非終端記号:a ≲ b 3)非終端記号A, aAbbなる右辺, A⇒+gad, dがeか1つの非終端記号:a ≳ b

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

50 5.3 演算子順位構文解析 演算子順位文法 E → E + E | E * E | ( E ) | id
5.3 演算子順位構文解析 演算子順位文法 E → E + E | E * E | ( E ) | id 2)非終端記号A, aaAbなる右辺,A⇒+gbd, gがeか1つの非終端記号:a ≲ b E + Eなる右辺,E⇒+E * E:+ ≲ * 3)非終端記号A, aAbbなる右辺, A⇒+gad, dがeか1つの非終端記号:a ≳ b E + Eなる右辺,E⇒+E * E:+ ≳ *

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

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

53 5.3 演算子順位構文解析 演算子順位構文解析アルゴリズム repeat forever begin
5.3 演算子順位構文解析 演算子順位構文解析アルゴリズム 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 5.3 演算子順位構文解析 演算子順位構文解析アルゴリズム $ id + id $

55 5.3 演算子順位構文解析 演算子順位構文解析アルゴリズム $ id E + id $

56 5.3 演算子順位構文解析 演算子順位構文解析アルゴリズム $ E + id $

57 5.3 演算子順位構文解析 演算子順位構文解析アルゴリズム $ E + id E $

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


Download ppt "言語処理系(6) 金子敬一."

Similar presentations


Ads by Google