では、字句解析の解説からはじめます。
(2ページ)
トークンというのが字句なわけですが、このトークンというのは何かというと、文法の最小単位が終端記号なわけですが、構文解析にとっての終端記号というのがある意味トークンというわけです。
具体的にはどのようなものがトークンかというと、たとえばキーワードとか、ようするにif とか while とかっていうのは、文字列としてみればiとかhとかの文字なわけですが、構文解析でみるとこれらはひと固まりのもので、つまりこれがトークン。
それから、区切り記号、括弧とか演算子、というような文法にとっての最小単位がトークンです。

それで、さっきちょっとでてきましたけど、identifierとか定数は、終端記号なわけですが、そうすると元のソースコードの3とか4とか15とかいった情報が消えてしまうので、これはどうするのかというと、保持するわけですね。
こういった くっついた値を字句値といいます。

では、トークン解析の実践ということで書いたものがつぎのlex.
どういうことが難しいのかというと、べつに難しいことはなくって、

[萩谷先生1] どういうものが識別子としてゆるされるのかっていうのは、普通は正則表現で簡潔にかけます。
例えば、英文字で始まる英数字列とかは、Emacs風の書き方をすると
このように書けます。
だから、正則表現を認識できれば、字句解析はいいわけです。
トークンとしてはその他にキーワードとかありますけど、若干これはきたなくって、まず最初に識別子を認識してからそのあとで特殊な識別子をキーワードとしてピックアップするという若干変則的な処理になります。
その他のトークンとしては、区切り記号とか演算子とかがあります。
それから空白文字はトークンではありません。ようするに適当にトークンとトークンを区切る記号なわけですね。だからトークンとしては意味がないわけです。
それから空白文字がたくさんあってもそれは意味がない。
通常はトークンの間には複数個のトークンを挿入することができて、となりあう識別子キーワード整数の間には、1つ以上の空白文字をいれなければならないわけです。
昔、FORTRANという変な言語があったんですが、FORTRANだと空白がいみがなくて、今のFORTRANは良く知らないのですが、昔のFORTRANだと空白を全くいれなくても 解析できるというすさまじいものだったわけです。
あ、あとキーワードも認識の仕方もへんで、Cだとifという変数名をつかえないんですけどFORTRANだとifという変数でもつかえるんですね。
FORTRANは、なんか非常にかわった言語なんです。

字句解析は難しいことをいうとですね、なぜ正則言語という話がでてきたかというと、字句解析をやるためには、正則言語を認識する必要がある、ということでそうすると オートマトンを作らなければならないとかそういう話になってきてしまうわけです。
もちろんそうやってオートマトンをつくってやることもできますが、普通はそこまでやる必要はあまりなくて、プログラムで書いても非常に簡単にかくことができます。
キーワードをどう認識するかとか演算子のかたまりをどう認識するかとかが重要なんだと おもいます。

レジュメの2ページに字句解析の実践ということで、えーこれはですね大変恐縮ですが Emacs-Lispで書いてあって、雰囲気だけあじわってもらえばいいとおもいますが、以降にLL構文解析のプログラムがかいてあってそれと完結するようになっています。
字句解析とLL構文解析2つ組になって、x+y*x1+y2 というような式をちゃんと認識できるようになっているということです。

それで、字句解析はどうやるかというとむずかしいことはなくって、あ、キーワードのテーブルとか演算子のテーブルとかはもちろん必要になります。
keyword-alist token-alist という変数が用意してあって、ここにキーワードとか演算子のテーブルがかいてあります。
ここには next-token という関数が用意してあります。これはこの関数を引数なしでよびだすと、Emacsのカーソルの次のトークンを読んでトークンを返して、カーソルは次のトークンにすすむというものです。
だからこの next-token という関数を繰り返しよびだしていくと、次々とトークン値が 返ってきて、カーソルはすすんでいくというようになります。
どんなかんじかというと、まず最初に、空白文字を読み飛ばします。Emacs-Lisp だと簡単で skip-chars-forward と呼び出すと空白スペース改行をよみとばします。
そして読み飛ばしたあと、先頭の文字が何かをしらべて英文字ならどうする、数字ならどうする、それ以外ならどうする、ということをやるわけです。
次の文字が英字ならば、英数字を読み飛ばして、というか先にすすんで、そこまでに読んだ英数字を切り出してきて、キーワードの連想リストをしらべます。
ようするに、英文字だったら identifier ですから、英数字の列がキーワードか調べます。
連想リストにあればキーワードですから、キーワードに対応するトークンを返します。連想リストになければ identifier ですから、この場合 identifier だというトークンとそれに付随してそれの文字列を返すわけです。
例えば、
[lexex1]
英字の場合は今の処理ですが、数字の場合の同じようですね。
numというトークンを返す。
そうじゃなければ、特殊記号がならんでいる場合ですから、特殊記号のならびを抜き出してきて、まあ1文字しかない場合もありますが、それをtoken-alistというところを調べて、対応するトークンを返します。
[lexex2]
たとえば、左括弧はlparとしてtoken-alistの中で登録されていますので、トークンとしては左括弧に対してはlparと返します。
で、次にxというのを読むとidというトークンで、その付随した情報としてxという情報がつきます。

以上まあ簡単な処理ですが。

トークン解析を難しいことをいうと、正則表現とかいう話になりますが、まあこれ正則表現ですが、べつにオートマトンの知識がなくてもいいです。
ちなみにahoの教科書にはもう少し詳しく書いてあって、正則表現をどうやって解析したらいいかという話も書いてあります。

字句解析の話はこれくらいでおわってしまうのですが、次に構文解析の話をやっていきます。
4学期にやったことをどのくらい覚えているか気になりますが(当時、形式言語理論の担当は萩谷先生でした)、えーと さきほどからいっているように、字句解析が返したトークン列を文脈自由文法にしたがって構文解析をします。

それで、いろんな構文解析の手法があるのですが、まず最初にLL予測型構文解析の話をします。
[文法]
これはかけ算と足し算しかない例ですが、こういう1こ1この規則を生成規則といいます。
左端は書き換え可能なわけですが、これは非終端記号です。変数という言葉は誤解を招くので使いません。非終端記号は生成規則で書き換えることができます。
あと開始記号というものがあります。Eが開始記号と宣言してもかまいません。
ようするに非終端記号のどれか一つが開始記号として宣言されます。
この例では非終端記号はEとT。終端記号は(、)、それからid。これiとdという二つの 文字でなくて、ひとつの記号です。
[最左]
こうやって繰り返し書き換えをおこなって、Eからはじめて終端記号だけからなるものになる過程を
[最左2]
というように書きます。

あと、あとで出てきますが、最左導出とか最右導出とかいうはなしがあって、この場合下線を引いた部分が書き変わるわけですが、この書き変わる部分が常に一番左の非終端である場合を最左導出といいます。

最後に文法が生成する言語について。
[生成する言語]
この例の場合はTから導出できるwという終端記号列の集まり全体を、生成する言語といいます。
このへんは、まあならったことがあると思いますが。

あと、いろいろな種類の記号についてまとめておきます。

[記号の種類]

おしまい


Prev

 

〔トップページへ〕 〔言語処理系論の仮想講義のindexページへ〕
<vu@is.s.u-tokyo.ac.jp>

Last updated on 7 May, 1999