コンパイラとプログラミング言語

コンパイラとプログラミング言語

第7週 構文解析の概要/上向き構文解析

2014年5月21日 金岡 晃

授業計画

第1週 (4/9)

コンパイラの概要 第2週

(4/16)

コンパイラの構成 第3週

(4/23)

プログラミング言語の形式的な 記述

第4週 (4/30)

プログラミング言語の形式的な 記述

第5週 (5/7)

字句解析の概要と非決定性有限 オートマトン、決定性有限オー トマトン・字句解析プログラム 第6週

(5/14)

中間試験

第7週 構文解析の概要/上向き構文解析

第8週 (5/28)

下向き構文解析/構文解析プ ログラム

第9週 (6/4)

中間表現と意味解析 第10週

(6/11)

Java仮想マシンとその機械語 第11週

(6/18)

条件分岐文と繰り返し文の コード生成

第12週 (6/25)

関数呼び出しのコード生成 第13週

(7/2)

休講 第14週

(7/9)

休講

中間試験 解説

コンパイラとプログラミング言語

問1

（１）

ソース プログラム

ソース プログラム

・・

・

（２）

（２）

目的 プログラム

目的 プログラム

（３）

実行時 ライブラリ

実行 プログラム

実行

（４）

下に示す言語処理系のなかで、コンパイラを示すものは（１）～（４）

のどれか答えよ

言語処理系

• コンパイラ、リンケージエディタ、エディタ、デバッガ、実行時ラ イブラリなど、プログラムの開発・翻訳（コンパイル）・実行に関 係するプログラム群の総称

• 処理系とも呼ぶ

エディタ

ソース プログラム

ソース プログラム

・・

・

コンパイラ

コンパイラ

目的 プログラム

目的 プログラム

リンケージ エディタ

実行時 ライブラリ

実行 プログラム

実行 デバッガ

問 2

コンパイラの内部は5つのフェーズから成り立つ。

その5つのフェーズをすべて書き出せ。

ソース

プログラム 目的

プログラム コンパイラ

字句

解析 構文

解析 意味

解析 最適化 コード 生成

中間情報（中間語、名前表）

フェーズ

問 3

＜問 3-1 ＞以下の中置記法で記述された式を後置記法に変換せよ O+P*Q-R

＜問 3-2 ＞以下の中置記法で記述された式を後置記法に変換せよ Y*(A*(M*(E*(T*E))))

＜問 3-3 ＞以下の後置記法で記述された式を中置記法に変換せよ

AB+CDE/-*

中置記法 → 後置記法

• 優先順位の高い演算から変換していく – 同じ優先順位だったら、左から

O+P*Q-R O+PQ*-R O+PQ*-R OPQ*+-R OPQ*+-R OPQ*+R-

Y*(A*(M*(E*(T*E)))) Y*(A*(M*(E*TE*))) Y*(A*(M*ETE**)) Y*(A*METE***) Y*AMETE****

YAMETE*****

優先順位

()

*, / +, -

=

問 3-1 ： OPQ*+R- 問 3-2 ： YAMETE*****

後置記法 → 中置記法

• やりかたはいろいろ

– 優先順位が高い演算から変換 – アタマから変換

• 変換のポイント

– 後置記法は演算される 2 つが先に来て、そして演算子が後に来る

演算子を見つけて、その直前の2文字を変換

AB+CDE/-*

(A+B)CDE/-*

(A+B)C(D/E)-*

(A+B)(C-(D/E))*

(A+B)*(C-(D/E))

外しても演算の順番に関係ない()を 外す

問 3-3: (A+B)*(C-D/E)

問 4

次の規則から生成することができる式はどれか答えよ

〔規則〕

＜式＞ :: ＝＜変数＞｜ ( ＜式＞ + ＜式＞ ) ｜ ( ＜式＞ * ＜式＞ )

＜変数＞ :: ＝ A ｜ B ｜ C ｜ D

（ア） A+(B+C)*D （イ） (A+B)+(C+D)

（ウ） (A+B)*(C+D) （エ） ((A*B)+(C*D))

1 つずつチェックをしていく

（ア） A+(B+C)*D

これが式かどうかを確認する

＜式＞ ::＝＜変数＞｜(＜式＞+＜式＞)｜(＜式＞*＜式＞)

＜変数＞ ::＝A｜B｜C｜D

どれにも当てはまらないので×

（イ） (A+B)+(C+D)

これが式かどうかを確認する

＜式＞ ::＝＜変数＞｜(＜式＞+＜式＞)｜(＜式＞*＜式＞)

＜変数＞ ::＝A｜B｜C｜D

どれにも当てはまらないので×

1 つずつチェックをしていく

（ウ） (A+B)*(C+D)

これが式かどうかを確認する

＜式＞ ::＝＜変数＞｜(＜式＞+＜式＞)｜(＜式＞*＜式＞)

＜変数＞ ::＝A｜B｜C｜D

どれにも当てはまらないので×

1 つずつチェックをしていく

（エ） ((A*B)+(C*D))

これが式かどうかを確認する

＜式＞ ::＝＜変数＞｜(＜式＞+＜式＞)｜(＜式＞*＜式＞)

＜変数＞ ::＝A｜B｜C｜D

この形式の様子。

あとは（A*B)と（C*D）が 式になっているかの確認が必要

（A*B) これが式かどうかを確認する

＜式＞ ::＝＜変数＞｜(＜式＞+＜式＞)｜(＜式＞*＜式＞)

この形式の様子。あとはAとBが

1 つずつチェックをしていく

A これが式かどうかを確認する

＜式＞ ::＝＜変数＞｜(＜式＞+＜式＞)｜＜式＞*＜式＞

＜変数＞ ::＝A｜B｜C｜D

式になっている

※B、C、Dも同様

（A*B)は式である

※ (C*D) も同様

((A*B)+(C*D))は式である

問 4 ：（エ）

問 5

＜問 5-1 ＞ 以下の BNF で表された構文規則を構文図式で表現せよ

< 項 > ::= < 因数 > { ^{< 乗除演算子 >< 因数 >} }

：終端記号

：構成要素 問5－1：

因数

乗除演算子 因数

ループしているが、

ループを通過しても良い

問 5

＜問 5-2 ＞ 以下の構文図式で表現された構文規則を BNF で表現せよ

問 5 － 2 ： while(< 条件式 >)< 文 >

while( 条件式 ) 文

問 6

＜問 6-1 ＞ 正規表現で (a|b)*(c|d)e と表されたものと一致する文字列 を選べ

（ア） abaabde （イ） abababbe

（ウ） cde （エ） ededab

(a|b)*(c|d)e

その後、c か d が1回出現する。

最後にe が出現する。

（ア） abaabde 表現に沿っているので ○

（イ） abababbe 表現に沿っていないので×

（ウ） cde 表現に沿っていないので×

（ウ） ededab 表現に沿っていないので×

問 6 － 1 ：（ア）

問6

＜問6-2＞ 下記の非決定性有限オートマトンを正規表現で表せ

1 4

F

C B 2 0 E

3 A

D

G

一番シンプルなのは、すべての道筋を洗い出して、| でつなぐ。

ABD*F

ACED*F

第 7 週

構文解析の概要 / 上向き構文解析

コンパイラとプログラミング言語

本日の到達目標と概要

• 到達目標

– 構文解析のおおまかな流れの理解 – 上向き構文解析の理解

• 概要

– 構文解析の位置づけ – 構文解析の概要

– 構文木と名前表

– 上向き構文解析と下向き構文解析

– 上向き構文解析の動き

コンパイラの論理的な構成

ソース

プログラム 目的

プログラム コンパイラ

字句 解析

構文 解析

意味

解析 最適化 コード

生成

中間情報（中間語、名前表）

フェーズ

字句解析の概要

• ソースプログラムからトークンを取り出して構文解析に渡す – ソースプログラム：文字列（数字含む）の集まり

– トークン：プログラム上の構成要素

• トークンの取り出しは、文法に従って行う

import java.io.*;

class Sample throws IOException{

public static void main(String[] args){

BufferedReader br = ….

}

} • 人間から見るとプログラム

• コンピュータから見ると文字列

import java

. io * ;

class Sample

throws IOException

public static ・・・

トークン

字句解析の流れ

ソース プログラム

字句解析

構文

文字（列） 解析

読み取り 字句

読み取り トークン

• 人間から見るとプログラム

• コンピュータから見ると文字列 ただの文字列

扱い

意味を持つ 要素に分割

分割されたトークンの集まりが 文法として間違っていないかチェック

（ここでBNFを使って定義された 文法と照らし合わせる）

構文解析

• 字句解析が出力したトークンを読み込みながら、そのトークンの列 がプログラム言語の文法で許されているパターンと合うかを解析す る

ソース

プログラム 字句解析 トークン 構文解析

構文木

名前表

• 許されているパターンであれば、トークンの列は構文規則 に従って構成され、字句を葉とする構文木が生成される。

• 構文解析の結果、ソースプログラムの構造は構文木として 出力され、名前や数字などの情報は名前表に出力される。

構文解析の例

構文規則 <式> ::= <項> | <式>+<項>

<項> ::= <因子>| <項>＊<因子>

<因子> ::= <名前>|(<式>)

<名前> ::= a|b|c

a ＊ ( b + c ) ソースコード

（字句解析の

入力） a＊(b+c)

トークン

（字句解析の 出力）

構文解析の例

トークン

（字句解析の出力）

構文木

（構文解析の出力）

a ＊ ( b + c )

因子 項 式

因子 項 式

因子 項

因子 項

式

構文解析法

上向き構文解析法

（bottom-up parser)

下向き構文解析法

（top-down parser)

入力した記号列が構文規則の 右辺と一致した場合に左辺の 記号に置き換えていく

記号列として次に何が来るの かを仮定しながら構文解析を

進めていく _{a ＊ ( b + c )}

名前 名前

因子 項 式

名前 因子 項 式

因子 項

因子 項

上向き 式

構文 解析法

下向き 構文 解析法

上向き構文解析法の例

因子 項 式

因子 項 式

因子 項

因子 項

式

構文規則

<式> ::= <項> | <式>+<項>

<項> ::= <因子>| <項>＊<因子>

<因子> ::= <名前>|(<式>)

<名前> ::= a|b|c

<因子> ::= <名前>|(式)

<項> ::= <因子>| <項>＊<因子>

<式> ::= <項> | <式>+<項>

<式> ::= <項> | <式>+<項>

<因子> ::= <名前>|(式)

<項> ::= <因子>| <項>＊<因子>

<式> ::= <項> | <式>+<項>

本日の到達目標と概要

• 到達目標

– 構文解析のおおまかな流れの理解 – 上向き構文解析の理解

• 概要

– 構文解析の位置づけ – 構文解析の概要

– 構文木と名前表

– 上向き構文解析と下向き構文解析

– 上向き構文解析の動き