第 1 回: 授業の概要, 言語理論とコンパイラの応用分野, コンパイラ全体の仕組み

授業の内容

フロンとエンド:

理論: 言語理論, オートマトン
コンパイラ: 字句解析, 構文解析
他の応用: 正規表現, XML

バックエンド:

コンパイラ: 最適化, コード生成

入力の難しさ

構造化されてない (ただのバイト列, 文字列)
何でもあり
入力が正しいかどうかの判断が計算のモデル

コンパイラの役割

ソフトからハードへの橋渡し
入力: 人間がわかるプログラム (高級プログラム言語, ソース (プログラム), 原始プログラム)
出力: 機械がわかるプログラム (目的プログラム, 実行プログラム)

コンパイラの仕事の一例

入力のプログラムの一部:

sum += price * 25;

出力:

LOAD R1, price  ; R1 (レジスタ 1) に price というアドレスからロード
LOAD R2, 25     ; R2 (レジスタ 2) に 25 の定数をロード
MUL R1, R1, R2  ; R1 に R1 と R2 のかけ算の結果を入れる
LOAD R2, sum    ; R2 に sum というアドレスからロード
ADD R2, R1, R2  ; R2 に R1 と R2 の合計を入れる
STORE sum, R2   ; sum というアドレスに R2 を入れる

コンパイラの論理的構造

プリプロセッサ (preprocessor)
字句解析 (lexical analysis)
構文解析 (parsing; syntax analysis)
意味解析 (semantic analysis)
最適化 (optimization)
コード生成 (code generation)
アセンブラ (assembler)
リンカ (linker), ローダ (loader)

コンパイラの種類と関連物

ワンパス•コンパイラ (one pass compiler)
x-パス•コンパイラ (x は 2 から 70 (PL/1))
動的コンパイラ (dynamic / just-in-time (JIT) compiler)
クロスコンパイラ (cross-compiler)
プリプロセッサ (preprocessor)
インタプリタ (通訳系, interpreter)

字句解析の一例

入力のプログラムの一分 (文字の列):

sum += price * 25;\n

出力 (記号の例):

id("sum"),plusequal,id("price"),asterisk,int(25),semicolon
1. 一つの記号 (符, token) が複数の文字からなる.
2. 記号に属性が付いていることがある.
3. 空白は解析に使われるが出力しない

構文解析の一例

入力 (記号の列):

id("sum"),plusequal,id("price"),asterisk,int(25),semicolon

出力 (構文木, syntax tree):

statement (+=(sum,*(price,25)))

オートマトンの一例

自動販売機:

入力: 50 円玉
出力: ジュース (150 円)

状態遷移図 (state transition diagram)

言語と文法

1. 文法は言語の構成規則である
2. 簡単な文の例 (命令文): eat bread, read books, play music
3. 文法的には read bread とか play books も正しい (疑問ある)

形式言語の文法の一例

1. S, A: 非終端記号 (nonterminal symbols, 大文字)
2. a, o, y: 終端記号 (terminal symbols, 小文字)
3. 書き換え規則 (rewriting rules)

    S -> a S o
    S -> A
    A -> y a
4. S: 初期記号 (initial symbols, start symbol)

文法から文の導出 (derivation) の一例:

S -> a S o -> a a S o o -> a a A o o -> a a y a o o
S -> a a y a o o