The SmallCompiler processor

Small Compiler Program 1

The SmallCompiler processor

(Preliminary Version)

節 頁 はじめに . . . 1 2 字句解析プログラム . . . 6 4 字句解析入力基本操作. . . 9 6 字句解析関数 . . . 14 7 数値トークン処理 . . . 28 12 識別子処理 . . . 32 13 構文解析プログラム . . . 42 16 文と制御構造 . . . 52 19 式と論理式 . . . 65 23 意味解析処理 . . . 73 26 識別子表とその操作 . . . 77 27 実行機械モデル . . . 86 29 意味解析処理の実装 . . . 104 33 文の意味解析処理 . . . 118 36 式の意味解析処理 . . . 142 40 誤り処理 . . . 157 43 プログラム全体の構成. . . 193 46 おわりに . . . 196 47 索  引 . . . 197 48

2 はじめに Small Compiler Program §1 1. はじめに. このプログラムは、コンパイラを構成する字句解析処理や構文解析処理及び意味解析処理の 概要を説明するためのものである。そのアルゴリズムは極めて基本に忠実なものを採用している。字句解析処 理は手作りコンパイラの標準的な技法を使っている。構文解析処理は再帰下降型手法を使っている。意味解析 処理も逆ポーランド命令を生成する標準的なものである。

これらのアルゴリズムは実際のコンパイラとのそれとほとんど同じであるが、実用的に重要な点は簡略化さ れている。たとえば、原プログラムに誤りがある場合などの処理は適切ではない。このプログラムは、誤りを 見つければメッセージを出力してコンパイルを中止する。実用コンパイラでは、誤りを訂正するように試みた り、原プログラムの残りも続けてコンパイルするようになっている。

したがって、実用的なコンパイラを作成するためには、かなりさまざまな手を加えてプログラムを使いやす いものにしなければならない。エラーメッセージの内容や形式、原プログラムとの対応性、識別子のリストや 相互参照表などの出力にも工夫が必要である。このような気づかいがプログラムの評価に非常に影響を与える ことが多い。

2. 原プログラム言語の構文は次のように定義される。これは、実用的に使われている言語に比べると極めて 単純であるように見える。実際、そのように努力して定義されているからである。しかし、整数処理機能だけ をとってみれば、実用言語と変わらないことは理解できよう。

<program>::=procedure main; <block>.

<block>::= [var<identifier>{,<identifier>}*;]

{procedure <identifier>[(<identifier>{,<identifier>}*)];<block>;}* begin<statement>{;<statement>}* end

<statement>::=<identifier>←<expression>|

if<B-expression>then<statement>{; <statement>}* [else<statement>{;<statement>}*]fi| while<B-expression>do<statement>{;<statement>}*od| call<identifier>[(<expression>{,<expression>}*)]|

read(<identifier>{,<identifier>}*) | write[(<expression>{,<expression>}*)] |

<empty>

<empty>::=

<expression>::=<term>{{+| −}<term>}*

<term>::=<primary>{{× | ÷}<primary>}*

<primary>::=<identifier>|<constant>|(<expression>)

<identifier>::=<letter>{<letter>|<digit>}*

<constant>::= [+| −]<digit>{<digit>}*

<B-expression>::=<expression>{=| >|<| ≥ | ≤ | =}<expression>

3. この構文は拡張Backus Nauer Form (BNF)を使って定義されている。{ と } は構文定義要素のグルー ピングを行う超記号である。[と]は、その中に示されている構文定義要素が選択項目であること、すなわち、

その要素が常に出現しなくてもよいことを示している。*は、その直前の構文要素が0回以上繰り返して出現 することを示している。その他の超記号は通常のBNFと同様である。

§4 Small Compiler Program はじめに 3 4. 以下では、この言語のコンパイラの概要をを具体的にプログラムとして記述することにより説明する。プ ログラムの説明にはKnuthが開発したWEB言語によるが、そのうちの文書部を日本語化したものを利用する。

したがって、具体的な記述言語はPascalということになる。プログラムのアルゴリズムを記述するためには、

一般性を失わないものと思われる。しかし、記述能力を強化するため、WEB言語のPascalは標準Pascal言語 から多少拡張されている。たとえば、関数や手続きの代わりにマクロ定義を利用することができる。次のよう な点でも拡張されている。

5. 以下のプログラムではcase文に省略時選択肢があり、どの選択肢とも適合しない場合に実行されるもの とみなしている。このためには、次のような構文を用いる。

casexof

1: code forx= 1; 3: code forx= 3;

othercasescode forx= 1 andx= 3 endcases

ほとんどのPascalコンパイラは、何らかの手段でこの拡張を行っているように思われるからである。

これらの構文要素は、利用できるコンパイラの依存して、適当に定義を変更すればよい。以下に、このよう な定義の一例を挙げている。

define othercases ≡otherwise { 明示されていない場合に対する省略時選択肢 } define endcases ≡end { 拡張case文で省略時選択肢に続く }

format othercases ≡else format endcases ≡end

4 字句解析プログラム Small Compiler Program §6 6. 字句解析プログラム. 字句解析プログラムは入力原プログラムを分解して、トークン記号列に変換し、出 力する。構文解析プログラムは、この記号列を受け取り、処理する。したがって、字句解析プログラムの入力 は、原プログラムを構成する文字の列である。文字列を構成するデータの形式はasciiなり、ISOなりで定義 されていて、選択の余地がない。Pascal言語では文字データは文字型として既定義である。原プログラムは、

当然Pascal のテキストファイルとして入力されることになる。具体的にデータを入力する部分（ファイルを

参照する部分）と字句解析処理本体は、手続き化やモジュール化などの適当な手段で分離しておいたほうがよ い。ファイルの処理に関しては、機種に依存することが多いからである。字句解析プログラムの出力は、トー クン記号列である。出力される記号は構文解析がおこない易いように適切にコード化して、表現されなければ ならない。Pascal言語の場合には、数え上げ型か記号定数により内部表現をおこなうことが多い。以下では、

これらの点について検討を加え、適当に仮定することにより、字句解析プログラムを作成する。

7. 字句解析プログラムそれ自身は、構文解析プログラムから呼び出されて、トークンを返すサブルーチンと して作成される。これは、コンパイラの基本的構造として、構文解析が中心となって全体の制御をおこない、

字句解析部やコード生成部は構文解析部から呼び出されるようになっていることが多い。これ以外に、これら の部分がそれぞれ別のパスを構成する多パス型のものや、字句解析が構文解析を呼び出し、構文解析がコード 生成を呼び出すようなデータ押込み型構成のものや、コード生成が中心となって、構文解析、字句解析を呼び 出す、データ引出し型の構成も考えられる。実際には、このような例はあまり知られていない。

ここでは、標準型のプログラムを考える。

§8 Small Compiler Program 字句解析プログラム 5 8. 字句解析プログラムが返すトークンそのものは列挙データ型として定義する。この定義は、構文解析プロ グラムでも参照されるため、大域で宣言しなければならない。字句解析を実装している関数はこのデータ型の 値を返す。

大域データ型の宣言 8 ≡

token type = (proc t, {procedureトークンを表示する } var t, {var}

begin t, {begin} end t, {end} if t, {if} then t, {then} else t, {else} fi t, {fi}

while t, {while} do t, {do} od t, {od} call t, {call} read t, {read} write t, {write} id t, {identifier} number t, {number} semicolon t, {;} period t, {.} comma t, {,} leftpar t, {( } rightpar t, {) } equal t, {=} greater t, {>} less t, {<} great equal t, { ≥ } less equal t, { ≤ } not equal t, { =} becomes t, { ← } plus t, {+} minus t, { − } multiply t, { × } divide t); { ÷ }

次の節も見よ— 33と80.

次の節で利用される— 193.

6 字句解析入力基本操作 Small Compiler Program §9 9. 字句解析入力基本操作. 原プログラム入力に必要な基本操作は、入力元から 1文字取り込むための操作 と、取り込み位置を1だけ進める操作である。これ以外にファイルのオープンとクローズ、行末や、ファイル 終端の検出操作が必要である。普通、このような基本操作はモジュールか手続き化することが多い。何かと都 合がよいからである。たとえば、エラーメッセージとともに原プログラムを表示することを考えれば、表示操 作も同じモジュールに簡単に組み込むことができるからである。

しかし、ここでは、これらの操作はPascal のファイル基本操作により実現する。前述のように原プログラ

ムはinput ファイルから読み込まれるものと仮定する。ただし、このプログラムではちょっとした技巧を使い、

別の識別子source を割り当てる。

define source ≡input

10. 入力ファイルから1文字だけ取込み、その値を返す関数をfetch とすると、その定義を例えば次のよう に与えることができる。このような定義は、システムに依存することが多い。

define fetch ≡source↑ { Pascal言語の既定義ファイルと標準演算子で定義される }

11. 読み取り位置を1進める手続き advance も次のように定義できる。この定義もシステムに依存する。

define advance ≡get(source) { これも、Pascal 言語の既定義ファイルと関数で定義する }

12. 行末がどうか検出する関数基本操作 end of line は次のように定義する。さらに、当該行の処理を終了 し、次の行の処理を開始する操作end this line も定義する。

ところで、本コンパイラの場合、行末を検出する代わりに空白文字を返す手法も利用できる。このほうが、

より簡単で望ましいかもしれない。

define end of line ≡eoln(source) define end this line ≡readln(source)

13. 原プログラム終端を検出する操作end of source も次のように定義できる。

原プログラムに誤りがなければ、この操作は必要がない。したがって、ファイル終端検出は、基本操作にす るよりも、外部で例外処理として実現するほうが、コンパイラや字句処理にとっては都合がよいかもしれない。

あるいは、ファイル終端を表わす文字を適当に定義しておいて、それを返す方法も考えられる。

define end of source ≡eof(source)

§14 Small Compiler Program 字句解析関数 7 14. 字句解析関数. 字句解析プログラムそのものは、トークンを表示するデータ型token type の値を返す

関数next token として定義され、引数を取る必要はない。その大略は次のように与えられる。

字句解析プログラム関数 14 ≡ functionnext token: token type;

var字句解析に必要な一時変数 16 begin 空白部分を読み飛ばす 15; 記号を一個分読む 22;

end;

次の節で利用される— 193.

15. 記号と記号の間のスペース、タブ、改行復帰、注釈などは全て空白と見なされるが、これはトークンを 区切るというかなり重要な機能をもっている。あるトークンを表示する文字列が、例えば括弧類のように他の 記号に依存しないで区切られている場合は処理は容易である。しかし、識別子のように空白か次の記号によっ て区切られて初めてそれを表示する文字列が終了する場合、処理に注意が必要である。次のトークンを処理す るときに、以前の区切りになった文字を無視しないようにしなければならないからである。advance の呼び出 しをおこなう場合とおこなわない場合を明確に区別する。

ここでは、タブはPascal入力ライブラリによりスペースに変換されるものとする。

空白を読み飛ばすためには、入力文字が空白文字類であるというループ条件でループを実装すればよい。一 見、非常に簡単なように見えるが、実はそうではない。入力文字をテストするためには、入力文字が確定して いなければならない。そのためには、現在の入力位置が行末やファイル終端であってはならない。すなわち、

一定の条件を確認したのち初めて入力文字データのテストをおこなうことができる。このような条件付きテス トを先頭テスト型ループに実装する場合、論理値型関数としてパッケージする手法がある。しかし、この手法 を追及すると、たいして汎用性のない関数がむやみやたらに増殖することになる。これは決して望ましいこと ではない。また、関数呼び出しオーバヘッドの程度によっては、実行効率もよくない。

ここでは、ループ制御変数を使った実装法を採用する。比較的分かりやすくて、実行効率も悪くないからで ある。

空白部分を読み飛ばす 15 ≡ non space found ←false; repeat if ¬end of source then

begin if end of line then end this line else 非空白文字を検出する 17; end

else 誤り処理（字句検出中ファイル異常終了）後中止 157; until non space found

次の節で利用される— 14.

16. 前述のように、制御用変数non space found が必要である。ファイルの終端が出現した場合なども組み 込まなくてはならない。原プログラムの誤りに対処するためには、このような処理もきちんとすることが望ま しい。本処理系では、入力原プログラムの終端は、原プログラムの誤りとみなしている。本来正しいプログラ ムについては、ファイル終端に出会うことがないからである。

字句解析に必要な一時変数 16 ≡ non space found: boolean;

次の節も見よ— 19, 30, 36及び39.

次の節で利用される— 14.

8 字句解析関数 Small Compiler Program §17 17. このプログラムで読み飛ばさなければならない空白部分は、スペースと注釈である。スペースを検出す ることは容易である。注釈の処理はそう容易でない。本処理系の場合、できるだけ容易に注釈を検出できるよ うに設計する。本処理系では、一対の中括弧で注釈を取り囲むものとする。したがって、入力文字列中の左中 括弧を見つければ、注釈を検出できる。実際の処理系、たとえばC言語のように、´/*´と ´*/´で注釈を区 切る場合には、もう少し複雑な処理が必要である。これらの処理をまとめると、次のようになる。

非空白文字を検出する 17 ≡ casefetch of

´´: advance;

´{´: 注釈を読み飛ばす 18;

othercasesnon space found ←true; endcases

次の節で利用される— 15.

18. 一見、注釈の処理は簡単なように見える。右中括弧が現われるまで、入力文字列を読み飛ばせばよい。

すなわち、入力文字が´}´でないという条件でループを実装し、ループ中で入力文字を無視すればよい。しか し、処理中に改行復帰やファイル終端を検出した場合、注意が必要になる。前記と同じように、ループ条件で 文字をテストする場合、行末やファイル終端でないことを保証しておかなければならない。そうでないと入力 データが不定になるからである。

ここでも、ループ制御変数を使って実装する。

注釈を読み飛ばす 18 ≡

beginadvance; comment end found ←false; repeat 注釈終端を検出する 20;

until comment end found;

advance; { 注釈終端文字そのものを読み飛ばす }

end

次の節で利用される— 17.

19. ループ制御変数は次のように宣言される。

字句解析に必要な一時変数 16+≡ comment end found: boolean;

20. 注釈を読み飛ばすことそのものは非常に容易である。

注釈終端を検出する 20 ≡ if ¬end of source then

begin { ファイルは終端していない } if end of line then end this line else { 行中である }

if fetch =´}´then comment end found ←true elseadvance;

end

else 誤り処理（注釈処理中ファイル異常終了）後中止 158

次の節で利用される— 18.

§21 Small Compiler Program 字句解析関数 9 21. 以上で、入力文字列中の空白部分が読み飛ばされた。さて、いよいよトークン検出の本体について考える。

本処理系で使われているトークンの外部表示の中には、通常のasciiなどのコード系で表示できないものが ある。このような場合、複数の文字を組み合わせて表示するか、適当な文字で置き換えることが多い。ここで は外部表示とその機械可読表示の対応を次のように定義する。

外部表示 入力記号

; ´;´

. ´.´

, ´,´

( ´(´

) ´)´

= ´=´

> ´>´

< ´<´

≥ ´>=´

≤ ´<=´

= ´<>´

← ´:=´

+ ´+´

− ´−´

× ´*´

÷ ´/´

22. 独立した１文字から構成されるトークンの処理は非常に容易である。２文字から構成されているいくつ かのトークンの最初の文字が他のトークンと共通であるものがある。このような共通の文字を含むものの処理 は注意が要求される。プログラムを誤ると、２番目の文字を読み飛ばしてしまうことがあるからである。

記号を一個分読む 22 ≡ casefetch of

容易な記号を処理する 23; 複雑な記号を処理する 24; 数値を含む記号を処理する 28; 識別子を含む記号を処理する 34;

othercases 誤り処理（未知の入力記号）後中止 159; endcases

次の節で利用される— 14.

10 字句解析関数 Small Compiler Program §23 23. トークンが一個の文字のみからなる場合の処理は簡単である。

容易な記号を処理する 23 ≡

´;´: beginnext token ←semicolon t; advance end;

´.´: beginnext token ←period t; advance end;

´,´: beginnext token ←comma t; advance end;

´(´: beginnext token ←leftpar t; advance end;

´)´: beginnext token ←rightpar t; advance end;

´=´: beginnext token ←equal t; advance end;

´+´: beginnext token ←plus t; advance end;

´−´: beginnext token ←minus t; advance end;

´*´: beginnext token ←multiply t; advance end;

´/´: beginnext token ←divide t; advance end

次の節で利用される— 22.

24. 前述のようにトークンが複数の文字からなる場合や、単一文字の場合でもそれが複数の文字からなるも のと重複する場合は、処理が複雑になる。

複雑な記号を処理する 24 ≡

´<´: ´<´記号の場合 25;

´>´: ´>´記号の場合 26;

´:´: コロンの場合 27

次の節で利用される— 22.

25. ´<´記号について、´<´、´<=´、または´<>´の三つの場合が考えられる。後続する文字を調べない限 り、これらを区別できないが、後が行末である場合も考えなければならない。後続した文字を調べたあとで、

その文字が現在のトークンと無関係の場合、その文字は次のトークンになる可能性もあるため、読み飛ばして しまわないように注意しなければならない。

´<´記号の場合 25 ≡ beginadvance; if end of line then

beginnext token←less t; end this line;

end

else casefetch of

´=´: beginnext token←less equal t; advance end;

´>´: beginnext token←not equal t; advance end;

othercasesnext token ←less t; endcases;

end

次の節で利用される— 24.

§26 Small Compiler Program 字句解析関数 11 26. ´>´記号については、´>´と ´>=´の場合が考えられる。上記に比べれば、処理はすこし簡単になる。

´>´記号の場合 26 ≡ beginadvance; if end of line then

beginnext token←greater t; end this line; end

else if fetch =´=´then next token ←greater t else beginnext token ←great equal t; advance;

end end

次の節で利用される— 24.

27. コロンに対しては、後続する文字が´=´でないかぎり、原プログラムの誤りである。

コロンの場合 27 ≡ beginadvance;

if end of line then 誤り処理（未知の入力記号）後中止 159 else if fetch =´=´then

beginnext token←becomes t; advance; end

else 誤り処理（未知の入力記号）後中止 159; end

次の節で利用される— 24.

12 数値トークン処理 Small Compiler Program §28 28. 数値トークン処理. トークンが数値を表わしている場合、その文字列を何らかの手段で数値化し、次 の処理のために用意をしなければならない。このような場合、数値の値そのものは大域変数を通して引き渡す ことが普通である。この大域変数を num value とする。字句解析関数は、数値トークンであることを返せば すむ。

入力された数字文字を数値に変換するために次の関数を定義するが、これは数字文字列が一定の順に並んで いることを仮定している。機種によっては必ずこのようになっているとは限らない。

define tonum(#)≡(ord(#)−ord(´0´)) 数値を含む記号を処理する 28 ≡

´0´,´1´,´2´,´3´,´4´,´5´,´6´,´7´,´8´,´9´: begin { 数字文字は数値化する } num value ←tonum(fetch); advance;

数字文字列が終了するまで続ける 29; next token←number t;

end

次の節で利用される— 22.

29. 数字文字列の処理には、やはりループが必要である。このループは、数字文字が続いている間実行され、

数字文字が途切れるか行末で終了する。したがって、このように複雑な終了条件をもっている場合、終了条件 を論理値型関数にパッケージすることが考えられるが、下手をすると、あまり汎用性のない関数が限りなく増 殖する可能性がある。また、関数呼び出しオーバヘッドによっては、実行効率も低下する。ここでも、比較的 分かりやすくて、効率もよいループ制御変数を使って実装する。

また、このプログラムでは数字文字の検出にcase文を使っている。これは集合に帰属するかどうかを調べ ているもので、本来なら、たとえばfetch ∈[´0´,´1´, . . .,´9´]のように帰属演算を使って調べればよいはずで ある。多分case文のほうがすこし実行効率がよいように思われる。

数字文字列が終了するまで続ける 29 ≡ num end found ←false;

repeat if end of line then

beginend this line; num end found ←true; end

else

casefetch of

´0´,´1´,´2´,´3´,´4´,´5´,´6´,´7´,´8´,´9´: begin { 引き続き数字文字を数値化する } num value ←10∗num value +tonum(fetch); advance;

end;

othercasesnum end found ←true;

endcases;

until num end found

次の節で利用される— 28.

30. ループ制御変数num end found は次のように宣言される。注釈処理とこの処理が同時に実行されるこ とはないため、注釈処理に使った変数をここで使っても問題は起こらない。しかし、処理ごとに異なった変数 を用意するほうが、不注意に誤りを犯す可能性を少なくする。

字句解析に必要な一時変数 16+≡ num end found: boolean;

31. 大域変数num value の宣言は次のようになる。

大域変数の宣言 31 ≡ num value: integer;

次の節も見よ— 37, 40, 81, 91, 97, 101, 113, 137, 191及び195.

次の節で利用される— 193.

§32 Small Compiler Program 識別子処理 13 32. 識別子処理. さて、識別子や予約語について処理をおこなう部分を考える。ここの基本的なアルゴリズ ムは、そう難しいものではない。入力文字列が英数字である間、それを記憶しておき、次に予約語かどうか調 べて、予約語ならそのトークン値を、そうでなければ識別子トークンとして値を返せばよい。これには、文字 列を記憶する配列、予約語表(配列)などが必要である。また、識別子の場合、その名前が識別子表などを構成 する場合に必要なため、名前文字列配列も大域変数としておかなければならない。文字列配列の大きさについ ても適当な仮定をして宣言する。

大域記号定数の宣言 32 ≡ max id length = 10;

次の節も見よ— 79.

次の節で利用される— 193.

33. 文字列用配列もデータ型として宣言しておいたほうが、何かと有利である。

大域データ型の宣言 8+≡

id type = packed array[1. .max id length]of char; 34. 以上の準備に基づいて、ここでの処理を実装する。

識別子を含む記号を処理する 34 ≡

´a´,´b´,´c´,´d´,´e´,´f´,´g´,´h´,´i´,´j´,´k´,´l´,´m´,

´n´,´o´,´p´,´q´,´r´,´s´,´t´,´u´,´v´,´w´,´x´,´y´,´z´,

´A´,´B´,´C´,´D´,´E´,´F´,´G´,´H´,´I´,´J´,´K´,´L´,´M´,

´N´,´O´,´P´,´Q´,´R´,´S´,´T´,´U´,´V´,´W´,´X´,´Y´,´Z´: begin { 識別子処理の開始 }

id value ←´´; id length ←1; id value[id length]←fetch; { 最初の文字を格納する } advance;

英数字が続く限り続ける 35; 予約語識別子を判別する 38; end

次の節で利用される— 22.

14 識別子処理 Small Compiler Program §35 35. ここでも、ループを実装しなければならないが、今までの説明とまったく同様にループ制御変数をつかっ たものを考える。

入力文字列が最大文字列を超える場合、余った部分を無視するようにする。コンパイラによっては、先頭の 数文字と最後の数文字を有効にするものもあり、かなり役に立つ実装になっている。本プログラムでも容易に 実装できるが、どのようにすればよいか考察するとよい。

英数字が続く限り続ける 35 ≡ word end found ←false;

repeat if end of line then

beginend this line; word end found ←true; end

else

casefetch of

´a´,´b´,´c´,´d´,´e´,´f´,´g´,´h´,´i´,´j´,´k´,´l´,´m´,

´n´,´o´,´p´,´q´,´r´,´s´,´t´,´u´,´v´,´w´,´x´,´y´,´z´,

´A´,´B´,´C´,´D´,´E´,´F´,´G´,´H´,´I´,´J´,´K´,´L´,´M´,

´N´,´O´,´P´,´Q´,´R´,´S´,´T´,´U´,´V´,´W´,´X´,´Y´,´Z´,

´0´,´1´,´2´,´3´,´4´,´5´,´6´,´7´,´8´,´9´: begin { 引き続き識別子の処理 } id length ←id length + 1;

if id length ≤max id length then id value[id length]←fetch; advance;

end;

othercasesword end found ←true; endcases;

until word end found

次の節で利用される— 34.

36. ループ制御変数word end found は次のように宣言される。

字句解析に必要な一時変数 16+≡ word end found: boolean;

37. 大域変数id value の宣言は次のようになる。

大域変数の宣言 31+≡ id value: id type;

id length: integer;

38. 記憶された文字列が予約語かどうか調べるためには、予約語表をあらかじめ作成しておいて、その表に ついて表引きすればよい。本処理系なら、予約語も少ないため、あまり複雑なアルゴリズムを駆使する必要は ない。単純な線形探索程度で十分である。ここでは、歩哨法をつかってループの構成を簡単にすませる。

予約語識別子を判別する 38 ≡

word table[id t]←id value; { 歩哨の設定 } lookup ←proc t; { 探索用変数の初期化 }

whileword table[lookup]=id value do lookup ←succ(lookup);

next token←lookup

次の節で利用される— 34.

39. 表探索に使われる一時変数lookup は次のように宣言される。

字句解析に必要な一時変数 16+≡ lookup: token type;

§40 Small Compiler Program 識別子処理 15 40. 表探索を簡単にすませるために、表を注意して構成しておかなければならない。予約語表そのものは次 のようになっている。

大域変数の宣言 31+≡

word table: array [proc t . .id t]of id type;

41. この表はプログラム実行開始時に適切に初期化しておかなくてはならない。

大域変数を初期化する 41 ≡

word table[proc t]←´procedure´; word table[var t]←´var´; word table[begin t]←´begin´; word table[end t]←´end´; word table[if t]←´if´; word table[then t]←´then´; word table[else t]←´else´; word table[fi t]←´fi´; word table[while t]←´while´; word table[do t]←´do´; word table[od t]←´od´; word table[call t]←´call´; word table[read t]←´read´; word table[write t]←´write´;

次の節も見よ— 82, 92, 98, 102, 114及び192.

次の節で利用される— 193.

16 構文解析プログラム Small Compiler Program §42 42. 構文解析プログラム. このプログラムでは構文解析技法としていわゆる下降帰納法 (recursive descent

parsing)を採用する。この技法では、構文解析は単一の解析手続きにより行われるようにはなっていない。む

しろ、構文記述の非終端記号に対応した複数の手続きが互いに呼び出しを行い、解析を実現する。したがって、

以下では複数の手続きを定義する。

これらの手続きはすべて構文解析手続きセクションで定義する。

43. 構文解析手続きは、構文が正しい原プログラムを受理することが可能であるが、オブジェクトプログラ ムを生成することはできない。オブジェクトプログラムを生成するためには、構文解析手続きのさまざまな場 所にいわゆる意味解析ルーチン(semantics analysis routine)を付け加えなくてはならない。以下の定義では、

これらのルーチンのある場所に適当なモジュールを配置することにより、それを示すだけにする。これらのモ ジュールは、後で適切に定義される。

44. いくつかの構文解析手続きの中で開始記号に対応する手続きpars program が最初に呼び出される。こ こでは、この手続きの定義からプログラムを実装する。ただし構文解析を開始する前に、大域変数cur token に最初のトークンが格納されているものと仮定する。このプログラムには、無数の誤り処理ルーチンや意味処 理ルーチンが含まれることが観察できよう。

Pascal 言語の規則によると、pars program に対応する構文規則(構文図)に含まれる非終端記号(に対応す

る手続き)に関して、その定義が後置される場合、forward 宣言を行わなければならないことに注意する。

define advance token ≡cur token ←next token { トークンを進めるマクロの定義 } define main name ≡´main´ { 主手続き名のマクロ定義 }

構文解析手続き 44 ≡

非終端記号に対応する手続きのforward 宣言 45 procedurepars program;

begin if cur token =proc t then advance token

else 誤り処理（構文解析中procedureがない）後中止 160; if cur token=id t then { 主手続き名に対する特殊処理 }

begin if id value =main name then 誤り処理（構文解析中主手続き名が不正）後中止 162; 主手続き識別子の意味解析処理 105;

advance token; end

else 誤り処理（構文解析中主手続き識別子がない）後中止 161; if cur token=semicolon t then advance token

else 誤り処理（構文解析中‘;’ がない）後中止 163; 主手続き開始意味解析処理 106;

pars block;

if cur token=period t then 主手続き終了意味解析処理 107 else 誤り処理（構文解析中‘.’ がない）後中止 164;

end;

次の節も見よ— 46, 53, 62, 65, 67, 69, 71及び72.

次の節で利用される— 193.

45. 非終端記号に対応する手続きのforward 宣言 45 ≡

procedurepars block; { 非終端記号に対応する手続きを forward 宣言する } forward;

次の節も見よ— 51, 55, 57, 61, 66, 68及び70.

次の節で利用される— 44.

§46 Small Compiler Program 構文解析プログラム 17 46. 次に定義する手続きはブロック本体を解析するものである。ここは原プログラムの骨格を処理する部分 であり、プログラムの入れ子構造に対する処理などもここに関係している。

構文解析手続き 44+≡

procedurepars block; ブロック意味解析処理に必要な一時変数の宣言 117 begin ブロック開始意味解析処理 108;

if cur token=var t then { 変数宣言が出現した } 変数宣言の構文解析 47;

whilecur token =proc t do { 手続き宣言が出現した } 手続き宣言の構文解析 48;

if cur token=begin t then { beginが出現した } ブロック本体の構文解析 50

else 誤り処理（構文解析中ブロック本体がない）後中止 165; end;

47. 変数宣言に対して出現する識別子を認識して識別子表に登録しなければならない。しかし、これらの処 理は、どちらかといえば意味解析の範ちゅうに属している。ここでは単に意味処理の表示だけにとどめている。

変数宣言の構文解析 47 ≡

begin repeatadvance token; { 次のトークンへ進める } if cur token =id t then

begin 変数識別子の意味解析処理 109; advance token;

end

else 誤り処理（構文解析中変数識別子がない）後中止 166; until cur token =comma t;

if cur token=semicolon t then advance token else 誤り処理（構文解析中‘;’ がない）後中止 163; end

次の節で利用される— 46.

48. 手続き宣言に対しては、手続き識別子の登録と入れ子処理が必要であるが、これらは意味解析処理で実 現されることが多い。ここでも表示だけにとどめる。

手続き宣言の構文解析 48 ≡ beginadvance token;

if cur token=id t then { 手続き識別子を検出した } begin 手続き識別子の意味解析処理 110;

advance token; end

else 誤り処理（構文解析中手続き識別子がない）後中止 167; 手続き開始意味解析処理 111;

if cur token=leftpar t then 仮引数宣言の構文解析 49; if cur token=semicolon t then advance token

else 誤り処理（構文解析中‘;’ がない）後中止 163; pars block;

if cur token=semicolon t then { 手続きがやっと終わった } begin 手続き終了意味解析処理 115;

advance token; end

else 誤り処理（構文解析中‘;’ がない）後中止 163; end

次の節で利用される— 46.