第11講 言語処理系

第 11 講 言語処理系
林 恒俊
言語処理系
言語処理系はプログラミング言語を処理する応用プログラム (application
program) である。コンパイラ (compiler) と呼ばれることもある。
原プログラムは普通テキストデータとして用意される。この表現形式は
人間にとって理解可能であり、機械でデータとして処理することも可能
である。しかし、不幸なことには、この形式のプログラムは、計算機が直
接解釈実行することができない。計算機は主記憶中に記憶された 2 進形
式の機械語プログラムのみが直接実行可能だからである。なんらかの手
段でテキストデータを実行可能な 2 進機械語に変換する必要がある。言
語処理系はこの矛盾を解決するための手段として着想され開発された。
コンパイラは人間にとって理解可能な形式のプログラムを処理して、計
算機が直接実行可能な形式に変換するプログラムであり、書物の異言語
間翻訳に類似した機能をもっている。
output
equivalent
output
semantic
interpret
equivalent
input
run
source
program
compiler
machine
code
コンパイラが果たさなければならない機能は原プログラムをそれと同等
な能力の機械語に変換することである。すなわち原プログラムに入力を
与えて解釈実行して得られる出力と、コンパイルされた機械語プログラ
ムが同等な入力に対して実行した結果が同等でなければならない。これ
を検証することは容易ではない。
c 2016 Tsunetoshi Hayashi.
⃝
1
情報科学 (2016)
2
言語処理系の構成要素
言語処理系の主要な構成要素は語彙解析、構文解析、コード生成である
けれども、加えてコード改善、実行時環境等あらかじめ計画しておかな
ければならない課題が多数存在する。むしろ現在では上記の三要素は適
切な自動化ツールを利用すれば比較的容易に構築可能である。
• 語彙解析 (lexical analysis) は字句定義に対応した処理を行う過程
である。実際の処理は原プログラムの文字列を切出して構成要素
(token) に分割する。lex のような正規表現処理生成系を利用しても
よいが、実は手作りでもそれほど手間はかからない。
• 構文解析 (syntax parsing) は構文定義に対応した処理を行う過程
で、入力要素列を文法に基づいた木構造すなわち解析木 (parse tree)
に変換する。構文解析は解析木を上方向に向かって構築する上昇法
とルートから下向きに構築する下降法の二通りの手法が利用される。
言語が構文図で定義されている場合は構文図から直接解析プログラ
ムを作成することも可能である。文法から yacc のような構文解析
自動生成系 (parser generartor) を利用して解析プログラムを生成す
ることも可能である。語彙解析と構文解析は言語に依存しているた
めこの部分を言語処理系のフロントエンドと呼ぶことがある。
• コード生成 (code generation) のため解析木から処理内容を反映
したプログラム木あるいは抽象プログラム (abstract program) を構
築し、それに対して命令語の動作を表現する部分木を適合させる。
プログラム木全体にマッチングできればそれから命令語列を生成で
きる。コード生成は機械語に依存しているためこの部分を言語処理
系のバックエンドと呼ぶことがある。
• 機械語を生成するかわりに、機械に依存しない中間言語 (intermediate language) コードを生成する処理系もある。バイトコードとも呼
ばれる中間言語はインタプリタ (interpreter) プログラムでこれを
直接解釈実行することが可能である。そしてインタプリタは既存の
言語を利用して移植できるため、言語を新規オペレーティング・シス
テムに移動するような場合に容易に作業を進めることができる。中
間言語はよく逆ポーランド記法 (reverse Polish notation, RPN)
の命令体系を利用することが多い。
第 11 講 言語処理系
3
• 再帰呼出しが可能なブロック型言語は実行時に局所変数や復帰情報
をスタック上に確保する。このようなスタックやそれを管理する仕
組みを実行時環境 (runtime environment) という。言語の設計に
は動作するオペレーティング・システム上で実行時環境をどのよう
に実装するかあらかじめ考慮しなければならない。
• コード改善 (code improvement) は生成された機械語を調整して
アセンブリ言語で書かれたプログラムに匹敵するくらいの実行速度
を与えることが目的である。初期のコンパイラから実現されていた
が、かけた手間の割に効果的とはいえないのが実情である。アルゴ
リズムを改善するほうがコード改善よりもはるかに効果があること
が少なくない。
機械語の冗長な部分を取除くことから、繰返しをベクトル化するこ
と、命令順を再スケジュールすることまで実現している。しかし、
計算機種によればここまでコード改善をしなければ実行速度が不充
分とということである。
字句処理
字句処理はテキスト形式の原プログラムを切分けて予約語、識別子、定
数、演算子、区切り記号等のプログラム構成要素を抽出する過程である。
• 一般的な設計では字句処理は独立した過程のプログラムではなく、
構文解析処理から呼出されて最新の要素の種類を返すような関数か
手続きとして作成される。
source
program
lexical
analyzer
syntax
parser
identifier table
識別子の名前や定数の値は関連した表やデータベースに格納する。
• 構成要素への切分けは概ね次のようになっている。例えば
println("Hello World!");
情報科学 (2016)
4
を構成要素に分解すれば
println
(
"Hello World!"
)
;
となる。
• これらの構成要素は形式言語学では正規表現 (regular expression) で
与えられる正規言語 (regular language) に属している。正規表現は
一般に広範な文字パターンを検索するためによく利用されていて、
文字の列 (sequence) と選択 (selection) と繰返し (repetition) により
定義される。文字列を解析して正規表現に適合するかどうか調べる
ためには有限状態機械 (finite state automaton) という抽象機械を
利用すればよいことが知られている。したがって字句処理プログラ
ムは
◦ 構成要素を正規表現で定義する
◦ 正規表現を判定する有限状態機械を合成する
◦ その有限状態機械をプログラムで実現する
で作成可能である。Unix には lex という字句処理生成プログラム
が付属している。実際に lex で作成した字句処理は大きくて遅いこ
とが多いので利用は多くない。字句処理プログラムは比較的容易に
手作りで作成が容易である。
• 古い Fortran では、基本的にステートメント中の空白文字は無視さ
れ、宣言されていない変数は暗黙に宣言されているものとみなされ
る。そこで、次の二つの文を比較すると、文の末尾に近いコンマと
ピリオドが違うだけで、構成要素に分解する区切り方も、構文も全
く異なったものになっている。
文
構成要素
DO 1 I=1,2
DO 1
DO 1 I=1.2
DO 1 I
I
=
=
1 ,
1.2
備考
2
DO 文
代入文
第 11 講 言語処理系
5
字句定義と構文定義が互いに依存していて、独立していないことが
原因である。最近の言語ではこのようにならないように設計される
ことが多い。
構文解析の原理
通常プログラミング言語の構文は BNF のような形式的体系に基づいて定
義される。ここでは記述を簡単化するため形式的文法を説明に利用する。
• この文法記述では置換え可能な記号 (非終端記号) を他の記号列で置
換えることを繰返し、最終的に置換え不可能な記号 (終端記号) のみ
からなる記号列を生成する。生成された記号列が正しい文である。
非終端記号の一つを選んで開始記号 (start symbol) として常にこの
記号から置換えを開始する。例えば非終端記号は {E, T, P }、開始
記号は E 、終端記号は {+, ×, (, ), a} で、次のような置換えをすると
仮定する。
E → E + T, E → T, T → T × P, T → P, P → (E), P → a
次のように置換えを繰返すと
E ⇒E+T ⇒T +T ⇒P +T ⇒a+T ⇒
a+T ×P ⇒a+P ×P ⇒a+a×P ⇒a+a×a
というように a と + と × と () からなる数式風の記号列を生成する。
• この生成過程は次のような木として図示することができる。
E
E
T
T
P
T
P
P
a
+
a
×
a
情報科学 (2016)
6
このような木を解析木 (parse tree) という。構文解析とは与えら
れた文から解析木を構築することである。入力文に対して根から解
析木を構築する方法と葉から構築する方法が考えられる。それぞれ
下降型解析法 (top-down parsing) 及び上昇型解析法 (bottom-up
parsing) という。
• 入力記号列は一般に先頭から後尾に向かって走査される。下降法は
入力文を生成した過程を再現することにより解析木を再構成する手
法である。開始記号から入力記号と適合するように生成規則にした
がって文を生成する。
start symbol
reconstruction
•
•
•
•
•
•
•
•
• input symbols
上昇法は入力記号列から部分木構築可能な列を検出して、できるだ
け早期に部分木を構築することにより、解析木を再構成する手法で
ある。
start symbol
•
•
reconstruction
• • • • •
•
• input symbols
いずれの手法でも最終的に得られる解析木は同一である。
第 11 講 言語処理系
7
再帰下降法
主としてプログラミング言語の構文が構文図で定義されている場合、構
文図から解析プログラムを直接導きだすことも可能である。手作りの言
語処理系では好んで採用されることが多い。
• 次の構文図の例について
E
T
T
+
P
×
T
P
(
E
)
P
a
以下のようにプログラムを作成する。
◦ 構文図のそれぞれの非終端記号に対して手続きを用意する。
◦ 手続きの内部で構文図のパスをコーディングする。
◦ 終端記号を通過する時、その記号が入力されているか検査する。
◦ 非終端記号を通過する時、対応する手続きを呼出す。
◦ パスが分岐する時、各パスの先で入力される記号の有無で分岐
を選択する。
• 結果得られるプログラムは次のようになる。なお symbol は最後に
入力した構成要素が格納される変数名、next は入力を 1 構成要素分
前進する手続き、error は構文誤りを報告する手続きである。
情報科学 (2016)
8
procedure E;
begin T ;
while symbol = “+” do begin
next;
T
end
end;
procedure T ;
begin P ;
while symbol = “×” do begin
next;
P
end
end;
procedure P ;
begin
if symbol = “a” then next
else if symbol = “(” then begin
next;
E;
if symbol = “)” then next
else error
end
else error
end;
式と文のコード生成
原プログラムについて構文解析を行った結果、構文が正しい場合には次
の処理を進められるように適切な形式で解析結果を出力する。出力は解
析木、逆ポーランド記法、4 つ組 (quadruple)、3 つ組 (triple) 等が代表的
である。それぞれ、一長一短があり、言語の複雑さやコンパイラの規模
などに依存して適切なものが選択される。さらに、形式は異なっていて
も表現されている内容はほとんど変わらないため、互いに形式を変換す
第 11 講 言語処理系
9
ることが可能である。通常、最適化や直接機械語生成を目指す場合には
解析木や 4 つ組、中間言語を経由してインタプリタ実行する場合には逆
ポーランド記法がよく採用される。
• 解析木をさらに変形して、プログラムの論理的構造を木構造で表
現したプログラム木、あるいは抽象プログラム (abstract program)
を利用する。コード生成はこれらの木構造を適当に走査することに
よって実現される。次にプログラム木の例を示している。
+
×
a
a
a
• 逆ポーランド記法 (reverse polish notation, postfix notation)
は数式などの表現法の一種で、オペランドを演算子の前に置くもので
ある。これに対して、通常の数式表現を中間記法 (infix notation)、
演算子をオペランドの前に置くものをポーランド記法 (polish notation, prefix notation) と呼ぶことがある。
記 法
中間記法
ポーランド記法
逆ポーランド記法
式 の 例
(a + b) × c
×(+(a, b), c)
((a, b)+, c)×
これらの記法のうち、逆ポーランド記法では括弧を取り除いても演
算順序が変わらないように評価法を与えることができる。すなわち
演算子の優先順に無関係に演算順をユニークに規定することが可能
である。コンパイラは逆ポーランド記法に基づく演算子とオペラン
ドの列として構文解析結果を出力する。逆ポーランド記法で出力す
るためには次のようにプログラム木を走査すればよい。
◦ 木の左枝の葉が変数や定数の終端ならそれを出力する。そうで
なければその葉を根として走査を再開する。
◦ 次に右枝の葉が変数や定数の終端ならそれを出力する。そうで
なければその葉を根として走査を再開する。
情報科学 (2016)
10
◦ 根の演算子を出力して、上位の枝に戻る。
◦ 木全体を走査すると終了する。
走査は再帰的に行われる。
• 逆ポーランド記法で表現された式はスタックを使って評価すること
ができる。中間言語インタプリタ方式のコンパイラではこの評価ア
ルゴリズムが大変重要な役割を果たしている。
◦ 最初にスタックを空にし、ポーランド記法式を先頭から順に走
査する。
◦ 式中の変数や数値を走査した場合、その値をスタックにプッ
シュする。
◦ 演算子が走査された場合、スタックからその演算に必要な数の
オペランドを取り出し、該当する演算を行い、結果として得ら
れた値をスタックにプッシュする。
◦ ポーランド記法式が走査されてしまえば、式の値がスタックに
残される。
次に式 1 2 3 × + を実際に評価した結果を示している。
スタック
(上位 ←→ 下位)
1
21
321
61
7
入力記号列
(先頭 ←→ 後尾)
123×+
23×+
3×+
×+
+
注 釈
初期状態
シフト
シフト
× 演算
+ 演算
評価終了
Pascal や SmallTalk や Java のコンパイラは逆ポーランド記法を出
力するように設計されている。パーソナル・コンピュータの UCSD
P-System は Pascal で書かれ、オペレーティング・システムまで逆
ポーランド記法で動いていた。
第 11 講 言語処理系
11
機械語コード生成
字句解析や構文解析と異なり、コード生成には理論的な基礎となるもの
がない。とくに、意味が厳密に数学的対象に基づいて定義されているよ
うな場合、機械語プログラムに完全に反映することはできない。例えば、
機械データ形式の整数では最大値や精度は有限であり、数学の整数の定
義とは明らかに異なっている。
• 現在のところ、意味定義と機械語命令の体系をにらみ合わせて、コー
ド生成のアルゴリズムを設計するしかない。この作業はかなり恣意
的である。逆にいえばコンパイラ設計の経験と腕前が発揮される所
でもある。
• 命令語を選択し機械語プログラムを出力するためには、構文解析と
よく似た手法を利用することができる。この手法では、計算機に実
装されている命令を生成規則の一種 (演算パターン) として記述し、
プログラム木を入力として構文解析 (パターンマッチング) を行なっ
て、その結果得られる導出列 (解析木) から機械語プログラムを生成
する。
◦ 命令語のオペランドやレジスタなどの演算に関係する要素を非
終端記号で代表する。
◦ 各命令について、演算とオペランドの組合わせを右辺、実行結
果を含む要素を左辺とするような生成規則を構成し、その命令
の動作を記述する。
◦ この生成規則の右辺を再解釈すると、演算子とオペランドか
ら構成される木構造とみなされ、プログラム木の部分木と対応
する。
◦ プログラム木を入力として、生成規則とのマッチングすなわち
構文解析をおこない、解析木を構成する。
◦ 解析木を適切に巡回することで機械語命令列を得る。
情報科学 (2016)
12
制御構造のコード生成
制御構造のコードは中間言語でも機械語でも実質は同じである。論理値
の評価コードが生成できれば、条件分岐とラベルを割当てるだけでよい。
• 条件文は次のようにコードを生成すればよい。
if B then S
code of B
branch on false to label-1;
code of S
label-1;
if B then S1 else S2
code of B
branch on false to label-1;
code of S1
branch to label-2;
label-1;
code of S2
label-2;
• 繰返し文は次のようにコードを生成すればよい。
while B do S
label-1;
code of B
repeat S until B
label-1;
code of S
branch on false to label-2;
code of B
code of S
branch on false to label-1;
branch to label-1;
label-2;
第 11 講 言語処理系
13
コード改善
• プログラム単位、式、文、制御構造程度の範囲を限ってコードを改
善する技法をいう。
◦ レジスタの最適配置
◦ 共通部分式 (common subexpression) の削除
◦ 複写伝搬 (copy propagation) の削除
◦ 無用コードの削除 (dead code elimination)
◦ 定数式のコンパイル時計算 (constant folding)
◦ ループ最適化 (ループ不変式の移動、ループ変数の削除、演算
の弱化)
◦ ピープホール最適化 (peephole optimization)
等のいくつか実現可能な改善法が挙げられる。
• ピープホール (覗き穴) 改善は、上記の諸技法と異なり、コード生成
が完了した後、機械語命令列について改善を施すように試みるもの
である。例えば、次のような場合に実施することができる。
◦ 無条件分岐先がまた無条件分岐命令である
◦ 無条件分岐命令の後にラベルの付いていない命令列がある
◦ 同じ番地に対する STORE 命令と LOAD 命令が引き続いている
このような命令列は、コード生成でかなり工夫をしても発生する。
実行時環境
現在の多くのプログラミング言語はブロック構造と静的有効範囲規則に
基づく実行モデルを採用している。このモデルでは局所変数を動的に確
保する。これはハードウェアが備えている環境とは適合しない。適合さ
せるメカニズムを実行時ライブラリが用意しなければならない。
情報科学 (2016)
14
• 実行時環境を決定する要因はプログラミング言語が用意している次
のような機能に依存する。
◦ 再帰呼出し (recursive call) の有無
◦ 手続きの入れ子 (procedure nesting) 構造の有無
◦ 動的に局所変数の大きさが可変
◦ 手続き引数の有無
• これらの機能を実現するためには実行プログラムの作業領域や局所
変数を静的に確保せずに、実行時スタックを用意してその上に動的
に確保するようにすればほぼ解決する。
stack
sp
local
variables
return
fp
arguments
local
variables
return
• 手続きの呼出しと復帰の機構は、基本的な部分はハードウェアの支
援が必要であるが、言語の機能によっては、実行時にかなりの処理
を行なわなければならない。通常、手続きを呼出す時には
1. 手続きの入り口でプログラムカウンタやレジスタ類などの CPU
状態を復帰情報として保存し、
2. フレームポインタを設定し、
3. 局所変数や一時変数などの作業領域を確保したのち、
第 11 講 言語処理系
4. 手続きを開始する。
という手順を実行する。手続きを終了する時には、
1. 作業領域を解放し、
2. 復帰情報を回復し、
3. 呼出し元に分岐する。
という手順が実行される。一般に復帰の方が作業量が少ない。
15