第 11 講 言語処理系

林 恒俊

言語処理系

言語処理系はプログラミング言語を処理する応用プログラム

(application program)

(compiler)

原プログラムは普通テキストデータとして用意される。この表現形式は 人間にとって理解可能であり、機械でデータとして処理することも可能 である。しかし、不幸なことには、この形式のプログラムは、計算機が直 接解釈実行することができない。計算機は主記憶中に記憶された

2

2

コンパイラは人間にとって理解可能な形式のプログラムを処理して、計 算機が直接実行可能な形式に変換するプログラムであり、書物の異言語 間翻訳に類似した機能をもっている。

source

program compiler machine

code semantic

interpreter equivalent run input

output equivalent output

コンパイラが果たさなければならない機能は原プログラムをそれと同等 な能力の機械語に変換することである。すなわち原プログラムに入力を 与えて解釈実行して得られる出力と、コンパイルされた機械語プログラ ムが同等な入力に対して実行した結果が同等でなければならない。これ を検証することは容易ではない。

⃝c 2015-2017 Tsunetoshi Hayashi.

1

言語処理系の構成要素

言語処理系の主要な構成要素は字句解析、構文解析、コード生成である けれども、加えてコード改善、実行時環境等あらかじめ計画しておかな ければならない課題が多数存在する。むしろ現在では上記の

3

•

(lexical analysis)

(token)

lex

•

(syntax parsing)

で、入力トークン列を文法に基づいた木構造すなわち解析木

(parse

tree)

昇法とルートから下向きに構築する下降法の二通りの手法が利用さ れる。言語が構文図で定義されている場合は構文図から直接解析プ ログラムを作成することも可能である。文法から

yacc

(parser generartor)

•

(code generation)

(abstract program)

プログラム木全体にマッチングできればそれから命令語列を生成で きる。コード生成は機械語に依存しているためこの部分を言語処理 系のバックエンドと呼ぶことがある。

•

(intermediate

language)

れる中間言語はインタプリタ

(interpreter)

(reverse Polish notation, RPN)

•

(runtime environment)

•

(code improvement)

コード改善は機械語の冗長な部分を取除くことから、繰返しをベク トル演算化すること、命令順を再スケジュールすることまで実現し ている。しかし、計算機種によってはこの程度までコード改善をし ないと実行速度が不充分になることもある。

字句処理

字句処理はテキスト形式の原プログラムを切分けて予約語、識別子、定 数、演算子、区切り記号等のプログラム構成要素を抽出する過程である。

このような構成要素をトークン

(token)

•

構文解析処理から呼出されて最新の要素の種類を返すような関数か 手続きとして作成される。

source

program lexical analyzer

syntax parser

identifier table

識別子の名前や定数の値は関連した表やデータベースに格納する。

•

println("Hello World!");

をトークンに分解すれば

println ( "Hello World!" ) ;

となる。

•

(regular language)

(regular expression)

(sequence)

(selection)

(repetition)

規表現に適合するかどうか調べるためには有限状態機械

(finite state

automaton)

したがって字句処理プログラムは

◦

◦

◦

で作成可能である。

Unix

lex

lex

•

Fortran

ない変数は暗黙に宣言されているものとみなされる。そこで、次の

2

文 トークン列 備考

DO 1 I=1,2 DO 1 I = 1 , 2 DO

DO 1 I=1.2 DO 1 I = 1.2

字句定義と構文定義が互いに依存していて、独立していないことが 原因である。最近の言語はこのようにならないように設計される。

構文解析の原理

通常プログラミング言語の構文は

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

a

T

×

P

P

a a

このような木を解析木

(parse tree)

析木を構築する方法と葉から構築する方法が考えられる。それぞれ 下降型解析法

(top-down parsing)

(bottom-up parsing)

•

• • • • • • • • • input symbols start symbol

reconstruction

上昇法は入力記号列から部分木構築可能な列を検出して、できるだ け早期に部分木を構築することにより、解析木を再構成する手法で ある。

• • • • • • • • • input symbols start symbol

reconstruction

いずれの手法でも最終的に得られる解析木は同一である。

再帰下降法

主としてプログラミング言語の構文が構文図で定義されている場合、構 文図から解析プログラムを直接導きだすことも可能である。手作りの言

語処理系では好んで採用されることが多い。

•

E T

T +

T P

P ×

P

( E )

a

以下のようにプログラムを作成する。

◦

◦

◦

◦

◦

•

symbol

next

1

error

recursive descent parser procedure E;

begin T ;

while symbol = “+” do next;

T

od end;

procedure T ; begin P ;

while symbol = “ × ” do next ;

P od end;

procedure P ; begin

if symbol = “a” then next else

if symbol = “(” then next ;

E;

if symbol = “)” then next else error

fi else error fi

fi end;

式と文のコード生成

原プログラムについて構文解析を行った結果、構文が正しい場合には次 の処理を進められるように適切な形式で解析結果を出力する。出力は解 析木、逆ポーランド記法、

4

(quadruple)

3

(triple)

4

ポーランド記法がよく採用される。

•

(abstract program)

a

a +

a

×

•

(postfix notation)

(infix notation)

(polish notation)

(prefix notation)

記  法 式 の 例 中間記法

(a + b) × c

× (+(a, b), c)

((a, b)+, c) ×

これらの記法のうち、逆ポーランド記法では括弧を取り除いても演 算順序が変わらないように評価法を与えることができる。すなわち 演算子の優先順に無関係に演算順をユニークに規定することが可能 である。コンパイラは逆ポーランド記法に基づく演算子とオペラン ドの列として構文解析結果を出力する。逆ポーランド記法で出力す るためには次のようにプログラム木を走査すればよい。

◦

◦

◦

◦

走査は再帰的に行われる。

•

◦

◦

(push)

◦

(pop)

(push)。

◦

次に入力記号列

1 2 3 × +

スタック 入力記号列

下位

←→

←→

<empty> 1 2 3 × +

(

)

1 2 3 × +

1 2 3 × +

1 2 3 × + ×

1 6 + +

7

Pascal

SmallTalk

Java

UCSD

P-System

Pascal

ポーランド記法で動いていた。

機械語コード生成

字句解析や構文解析と異なり、コード生成には理論的な基礎となるもの がない。とくに、意味が厳密に数学的対象に基づいて定義されているよ うな場合、機械語プログラムに完全に反映することはできない。例えば、

機械データ形式の整数では最大値や精度は有限であり、数学の整数の定 義とは明らかに異なっている。

•

•

(

)

プログラム木を入力として構文解析

(パターンマッチング)

(

)

◦

◦

◦

◦

◦

制御構造のコード生成

制御構造のコードは中間言語でも機械語でも実質は同じである。論理値 の評価コードが生成できれば、条件分岐とラベルを割当てるだけでよい。

•

if B then S fi if B then S

else S

fi

code of B

branch on false to label-1;

code of S label-1:

code of B

branch on false to label-1;

code of S

branch to label-2;

label-1:

code of S

label-2:

•

while B do S od repeat S until B

label-1:

code of B

branch on false to label-2;

code of S branch to label-1;

label-2:

label-1:

code of S

code of B

branch on false to label-1;

コード改善

•

◦

◦

(common subexpression)

◦

(copy propagation)

◦

(dead code elimination)

◦

(constant folding)

◦

(ループ不変式の移動、ループ変数の削除、演算

)

◦

(peephole optimization)

•

(

)

◦

◦

◦

STORE

LOAD

実行時環境

現在の多くのプログラミング言語はブロック構造と静的有効範囲規則に 基づく実行モデルを採用している。このモデルでは局所変数を動的に確 保する。これはハードウェアが備えている環境とは適合しない。適合さ せるメカニズムを実行時ライブラリが用意しなければならない。

•

◦

(recursive call)

◦

(procedure nesting)

◦

◦

•

before call after call

return local variables

stack

fp sp

return local variables arguments

return local variables

stack

fp sp

•

1.

CPU

2.

3.

4.

という手順を実行する。手続きを終了する時には、

1.

2.

3.

という手順が実行される。一般に復帰の方が作業量が少ない。