- 追加された行はこの色です。
- 削除された行はこの色です。
[[Cコンパイラ設計(yacc・lexの応用)/第1章]]
[[FrontPage]]
2008/05/13からのアクセス回数 &counter;
#contents
* 単語の認識 [#xe37077e]
** 目的 [#q3973f9d]
前章でも見てきたように、言語は文の集合体であり、さらに文は終端記号の集合体である。プログラミング言語における終端記号は三種類存在している。特殊な(短い)文字列で表現される演算子、あらかじめ決められた文字列で表現される予約語、そして特殊な文法の規定に従う定数や識別子などのユーザが定義する終端記号である。もちろんブランク文字やタプコードや改行文字のような空白文字も存在する。これらは、最近のプログラミング言語では、ただ単に終端記号を分割するものか、あるいはまったく意味がないものである。また、コメントもそれぞれのプログラミング言語の文法によって異なるが、空白文字と同様に、意味がないものとして扱われる。
本章では、コンパイラに与えられた無秩序な入力文字列から終端記号を取り出す作業、すなわち編集段階である字句解析を取り扱う。字句解析では通常、空白文字やコメントは無視される。また、演算子や予約語が認識され、内部表現一通常は小さな値をとる整定数一に置き換えられる。ユーザの定義した定数や識別子は適当なテーブルに保存され、IdentifierやConstantという一般的な表現と、その内容が保存されたテーブル上の位置とが次段に渡される。字句解析の問題は、次のような形式を持った実際の言語定義を用いて、模擬的に解決することができる。
#pre{{
statement
: 'I' 'F' condition 'T' 'H' 'E' 'N' statement
}}
しかしながら、結果としての文法は矛盾を含まざるをえず、技術的には非常に非効率的である。
字句解析は、コンパイラの作業の中でも大部分を占めるものとなる。他のコンパイラの処理とはほとんど独立したものである字句解析を扱うことで、もっと適切な手法を用いることが可能となり、また同時に,我々が日常的に利用する文字セットを使用したプログラミング言語の記述についての情報を、1つのモジュール内に隠すことが可能となる。
** 定義手段 [#xc875e1d]
我々はいかに文字列から終端記号を構成していくのであろうか?字句解析は有限状態オートマトンの理論のための伝統的なアプリケーションである。プログラミング言語の語彙表現の仕様から遷移図を作り出すのは簡単であり、漠然と遷移図に基づいて10時間前後の時間を費やせば、どのような仕様にも対処できるであろう。文字列、コメント、そして(浮動小数点)定数を大方その順番に処理しようとすると、通常汚らしいものになる。まず、図によって、遷移図として表現されたCスタイルのコメントを考えてみる。
#ref(fig_2.2_1.jpg);
遷移図では状態は番号の付いたノードとして表わされ、遷移は状態間の枝で表わされる。そしてこの枝にはその遷移をもたらす文字が付記されている。特徴的なことは、終端記号を検出しての遷移からの脱出は偶然のものであり、ある場合には次に続く文字を先読みしているし、ある場合にはそうではない。
遷移図は完全にきっちりと文法グラフに一致している。遷移図の枝は状態遷移を表わしているが、文法グラフのノードは状態変化を起こすための記号を含んでいる。両者の違いは、文法グラフが通常互いに別の文法グラフを呼び出すのに対し、遷移図ではそのようなことは仮定されないことである。
#ref(fig_2.2_2.jpg);
両者の比較を通じて、なぜ遷移図が字句解析のための方法として選ばれるかがわかるであろう。しかし、この方法そのものは間違いやすく、結果を修正しにくい。
もっと良い字句解析の問題の解決方法は、次のようなセオリーから直接引き出される。言語仕様を満足する有限状態オートマトンを表現する便利な方法が必要であり、また、その表現から適当なテーブルを作り出すコンパイラが必要であり、そしてこのテーブルによって有限状態オートマトンをシミュレートするインタプリタが必要となる。
このような目的に対して、lex[Les78bコと呼ばれるコンパイラが実際に作られている。lexはエディタのパターン
(([Ker78a]のed(1)参照。))
に似たパターンからなるテーブルを受け取り、パターンを満足する入力文字列を解析することのできるテーブル駆動型のCプログラムを作り出す.エディタの代用コマンドが示すように、バターンはある特定の文字列を認識するために非常に便利なものである。
パターンは有限状態オートマトンを実際に構築するための非常に便利な定義用言語である。それぞれのパターンに対して、入力内にそのパターンを満足する文字列が見つかった際に実行されるC言語の命令が作られる。簡単な翻訳用のアプリケーションでは、通常C言語の文は変更した文字列のコピーを標準出力に書き込むが、コンパイラでは、文字列に対して適当な符号化を行なったものを、字句解析関数を呼び出した関数に返さなくてはならない。
これから見ていくように、leXは本来非常に強力なツールであり、言語の認識に対して便利に使うことができる。しかし、私見ではあるが、1eXはユーザに対する親和性がきわめて悪い。エラー・メッセージは短く、しかも不明確である。また、leXに対してのコメント的な入力は、どう見ても煩わしいものである。さらに、leXを上手に使用しないと、巨大なプログラムを作成してしまう。しかし、それでもleXは字句解析のためには利用すべきツールである。というのも、もう一つの選択肢である字句解析関数の自力での作成は、非常に手間がかかってしまうからである。
本章の残りの部分では、大部分のコンパイラ・アプリケーションに対処するのに十分なleXの特徴について、詳細を示す。まずはじめに、もっとも頻繁に利用されるパターンのためのオペレーションについて、leXではパターンがどのように記述されるかについて、および識別子、文字列、コメントなどの標準的な言語の構成要素がどのようにパターンとして表現されるがについて、示す。ここでは大部分の可能性を示すのであり、その詳細を示すことはしない。
2.5節ではlexをプログラム生成ツールとして紹介し、2、3の、小さいものではあるが、ファイルの挿入、分割、単語の数え上げの完全なlexのプログラムを示す。我々のsampleCの実装については、sampleCのための完全な字句解析機構が示される2.7節でさらに紹介する。
** パターン [#lfaefea2]
edやそれに似たテキスト・エディタのユーザは、次のようなパターンの構成に十分慣れ親しんでいる。
- その文字自身を表現している英文字、数字、その他の特殊文字
- 改行を除く任意の文字を表現するピリオド(.)
- キャラクタ・クラスと呼ばれる一連の文字列を囲むブラケット、[および]、このクラスは、その構成要素の中の任意の一つを表現している,あるいは文字列が^で始まっている場合には、その文字列中に存在しない任意の1文字を表現している。文字列中の二つの文字の間の一は、その範囲を含むことを表現している。
以上に示したパターンのある一つの構成要素に続く・は、同じ要素の入力が任意の回数繰り返される、またはまったく存在しないことを示している。
- パターンの先頭の^は入力行の先頭を示している。
- パターンの最後の$は入力行の最後を示している(ただし改行文字そのものではない)。
特殊文字や空白に対しての適当なエスケープの規定とを合わせると、プログラミング言語の大部分の終端記号に対してのパターンが表現できる。1eXでは二つのエスケープの規定がある。
- ＼は次に続く特殊文字の特殊な意味を失わせる。特に二つ続いた＼文字は一つの＼を表わしている。＼がbやnやtの英文字に先行することがあるが、これらの組合せは、C言語と同じように、それぞれ後退文字、改行文字、タプ文字を表わしている。
- もっと良い方法は、一つ以上の文字を引用符(double-quote)で囲むことであり、これは特に文字列に対して有効である。引用符で囲まれた文字は、その文字が本来持っている特殊な意味を失う。
大部分の特殊文字は、1eXにおいては特殊な意味を持っている。もし特殊文字がその文字自身を表現しているのであれば、それは特殊な意味を失っているということである。特殊文字はキャラクタ・クラス内においては特殊な意味は持たない。空白は常になんらかの方法によって特殊な意味を失わせることを明確にするか、＼によるエスケープ・シーケンスによって表現されなくてはならない。引用符内の引用符は、C言語と同様に＼"で表わされる。
以下、例を挙げてsampleCのいくつかの終端記号に対するパターンを示す。演算子は単純に引用符で囲まれている。ここではバックスラッシュのコンベンションよりも引用符を使う。したがって演算子は
** 長所としての曖昧さ [#j5a1be74]
** “lex”のプログラム [#z9f0647f]
** 字句解析部のテスト [#h6129800]
** 例 [#vbaa58e2]
** 問題 [#ta4c041d]
** コメント [#qc6a0b02]
この記事は、
#vote(おもしろかった,そうでもない,わかりずらい)
皆様のご意見、ご希望をお待ちしております。
#comment
![[PukiWiki]](image/pukiwiki.png "[PukiWiki]")
