| 言語処理系を作ってみたい！！ | ||||||||||||||||||||||||||||||
| 僕がそんな野望を抱き始めたのは、ちょうど去年の今時分からでした。 その頃我が愛読書Ｃマガジン誌では、大城正典氏の「ＲＡＤユーザのためのプログラミングセオリー入門」 という記事が連載されていました。その記事はＣ＋＋やＪａｖａなどのオブジェクト指向言語のソースコードを使って、 様々な分野に応用できるデータ処理のノウハウを解説するという内容なのですが、 ９８年８月号〜１１月号は、「ダイアログボックスに入力した式の答えを計算するプログラム」を題材にして、 制作過程を解説しながら言語処理の基本となる計算式処理を学習しようというものだったのです。 言語処理系はＣ言語やＨＴＭＬなどのソースコードが書かれている、タネも仕掛けもないテキストファイルを、 非常に派手な動作（派手なホームページや、派手な強制終了） に変換してくれる、どえらいプログラムと思っていましたし、 言語処理系のような複雑怪奇な（に思える）データ処理技法をマスターすれば、 その他の色々な処理にも応用が利くでしょうから、昔から一度 は作ってみたいプログラムでした。 その作り方の一部分を知ることができるとあって、ワクワクして記事に目を通してみたのです。 しかし見慣れない学術用語と言語処理系ならではの方法論が壁となり、なかなか理解が進みませんでした。 字句解析器といってソースコード（ここでは計算式が書かれた文字列）から、 数値や演算子(※）などの単語（トークン）を切り分ける処理までは何となく理解できたものの、 それより後の構文解析器（式の構造を解析する処理）の作成や、 記号表（名前とその意味とを結びつけるためのデータ構造）の管理、 そしてそれぞれの処理の役割分担については真っ白な状態でした。 それでも字句解析器を作り、気を良くした僕は「他の処理についてももっと勉強して、 まずは変数や関数なんかも使える便利な電卓プログラムを作ってみよう！」と意気込んだのでした。 注
| ||||||||||||||||||||||||||||||
| インターネットでお勉強 | ||||||||||||||||||||||||||||||
|
言語処理系の勉強を始めようと思い、
書店へ行ってコンピュータ関係の技術書の棚を眺めてみましたが、
なかなかこれといった本が見つかりませんでした。 プログラミング言語や、オブジェクト指向、Windowsプログラミングなどの メジャーな分野を解説した本でしたら、たくさんの本が棚を争っていて、入門書からかなり専門的な内容のものまで、 自分のレベルや目的に合ったものを選ぶことができます。 しかし、言語処理系となると本の数も少ないですし、大学の講義の教科書向けに 書かれている本がほとんどで、学術用語をかみ砕いて分かりやすく説明しているような本は見当たらず、 最初から独学で勉強するには少々敷居が高い感じを受けました。 何か勉強の道しるべになるような本があるといいと思ったのですが、 この本を一読すればこれだけの事ができるようになる、という実感が持てそうな本を 見つけることができませんでした。 書店ではどんな本を読んだら良いのか解らなかった僕は、インターネットのサーチエンジンを 使って、「構文解析」とか「字句解析」とか、言語処理系を扱う書籍の中で必ず書かれているような キーワードで検索してみました。検索結果は何百件にも昇りましたが、最初から２、３件目にあった、 「Compiler Construction Lecture」というページをおもむろに開いてみました。 するといきなり「コンパイラを書くのは難しくない」という見出しで、 言語処理系の仕組みを解説しているページに出くわしたのです。 そのページは琉球大学工学部情報工学科で教職にあたっておられる、河野真治氏のホームページの一部でした。 彼は大学の講義のレジュメをインターネット上で公開されておられたのです。 その中ではＣ言語をアセンブリ言語に翻訳する、最小限のコンパイラのソースコードや、「再起下降」という 構文解析方法が紹介されていました。 最小限のコンパイラはMicro-Cと呼ばれていて、Ｃ言語で書かれたわずか３０００行ほどのプログラムですが、 ちゃんとＣ言語のソースコードをコンパイルして、アセンブリ言語に変換することができるものです。 Micro-Cの構文解析器でも、再起下降方式が使われていました。 「再起下降」という方法は簡単にいうと、各々の文法規則に対応した処理を行う関数があって、 それらの関数はソースコードを読み進めながら、さらに別の文法規則に対する関数を呼び出すようになっていて、 次々に呼び出し合いながら構文解析を進めて行くというものです。 「文」や「式」といった広い範囲を扱う関数が最初に呼ばれて、「掛け算や割り算」、「数値」といった 狭い範囲を扱う関数は、自分より広い範囲を扱う関数に呼び出される形になります。 例えば、「３×５＋６÷２」という式を再起下降方式で計算する場合を考えてみましょう。 この式を計算するには、まず「３×５」や「６÷２」の答えを計算した後に、それらを足し合う必要 があります。これを関数として書く場合は、「足し算」という文法規則を扱う関数は、加算処理を行う前に、 掛け算や割り算を処理する関数を先に呼び出して、その結果を得ておく必要があります。 具体的には次のような手続きとなります。 「足し算」関数の手続き
さらに「掛け算や割り算」の処理はこうなります。 「掛け算や割り算」関数の手続き
「数値」はご覧の通り。 「数値」関数の手続き
河野氏はこの再起下降構文解析の実現方法を、Ｃ言語のサンプルコードを使って説明しておられました。 この方式は処理の見通しもつけやすく、簡単に作れるのが特徴なのだそうです。 僕が使い慣れたＣ言語で説明されているのもあって、直感的に理解できたことを覚えています。 扱える文法の範囲が狭いという問題があるらしいのですが、 その頃僕が求めていた電卓プログラムの式解析処理には十分対応できるものでした。 この方法を知った僕は、電卓プログラムの作成に取りかかりました。Ｃ言語を使って作って、 四則演算や、括弧の処理もできるようなものにしました。 変数や関数なんかも扱えるようにしたかったのですが、記号表の管理とかもやらなければいけない と思ったのと、関数の構文を解析する方法がよく分らなかったので取合えず保留にしました。 「式を入力して、結果を表示する」関数、「足し算や引き算」関数、「掛け算や割り算」関数、「値構築」関数 をそれぞれ用意しました。「値構築」関数は、上記の「数値」関数の機能に加えて、マイナス記号や、括弧の処理 をするように作りました。 取合えず一通り書いて、実行してみると… ＞１+１[ENTER] ＞１ このバグは文字通り「足し算」を忘れていたために起こった単純なミスですが、その人口無能ぶりは笑えました。 ごく初歩的な電卓プログラムではありますが、「処理系」と名の付くものを作ってしまった僕は、 しばらくの間、既に業界の重鎮たちと肩を並べたような気分に浸っていました。 そして次の目標は「簡単なＢＡＳＩＣ（※）インタープリタを作ること」に定めました。 注
| ||||||||||||||||||||||||||||||
| Ａｈｏのバイブル買ってみた | ||||||||||||||||||||||||||||||
|
最初に書店で本を漁っていたときには見つけられなかったのですが、どうやら言語処理系
の分野を勉強する人々の間で、通称「バイブル」や、「ドラゴンブック」
と呼ばれている定番の教科書があることをインターネットをクルージングしていて発見しました。
言語処理系の構築法を解説している多くのサイトで、この本について言及されていたのです。 それはAlfred V.Ahoという人が中心になって書いた『コンパイラ 原理・技法・ツール』という本で、 邦訳版はサイエンス社が発行元になっています。 I巻とII巻があってそれぞれ5,600円というかなり高価な本なのですが、 「やっぱり定番物だし」というイメージに押されて、買ってみることにしました。 無理をしたのは値段だけではありません。買ってはみたものの、知らない言葉が溢れ返っていて 最初の２、３０ページ読んだだけで、頭がぐるぐる回り始めるような感じになってしまいました。 /(@_@)\←ぐるぐる それでも頭を掻きむしりながら読んでみると、どの言葉もその意味はしっかりと説明されていますし、 様々な例や図形や擬似コード(※)によって繰り返し説明がなされています。 それらの言葉はどれも言語処理系を実際にコーディングする過程で必要となってくる考え方や、使われているデータ構造、 テクニックに即しているものばかりですし、非常に興味深い概念がたくさん解説されていることが分ります。 何度か繰り返し読んで、しっかりと言葉のイメージをつかめば、この本全体の内容も理解できそうな感じはしました。 しかし聞いたこともない言葉は数百語やそこらではありません。 やっと言っている意味を理解しかけたかなと思うと、今度はその言葉を使ってさらに別の概念が説明される といった具合です。ほとんど外国語を一つ勉強するようなものです。 しばらくはページをめくる度に頭が痛くなる日々が続きました。 思えばこの本、最初に書店で敬遠していた「大学の講義の教科書向けの本」の親玉みたいなものです。 章末には練習問題とか参考文献とか載ってますし。 「処理系作りてぇー、動かしてぇー、何でも良いから早く早く！！」という僕ですので、 最初から最後まで丹念に読むことは今後に委ねることにして、 「分らなかったら、索引を引いて読み返す」という立場（？）で、 インタープリタを作るに当たって、自分が知りたいところだけを読んでみることにしました。まず動くところ までは持って行きたいというのが人情というものです。 この本の目次を眺めると、１章はガイダンスになっていて、コンパイラの仕組みや、この本の構成に 関する説明となっています。また、２章では式の順序を入れ替える簡単なコンパイラを作る過程が 紹介されていて、この本で説明される内容の予行演習のような内容が書かれています。 そして３章以降から、本格的なコンパイラを作るに当たって必要となるノウハウが、概念的な説明から、 プログラムを記述する上での具体的なテクニックまでを含めて、詳しく述べられています。 １章２章は今後の勉強のロードマップにするために読んでおいた方が良いと考えました。 ３章は字句解析器についての説明でしたが、 字句解析ルーチン自体、簡単なものなら１００行程度の１つの関数で書けますし、 「正規表現」や、「DFA」、「オートマトン」などといった難しそうな概念を知らなくても、 自分が書きたいと思うような処理は書けると思ったのでパスしました。 ４章は、構文解析器についての解説です。構文解析に使われる処理方法が何種類か書いてあって、 それぞれの構文解析方法に適した文法の性質が説明されています。また構文解析器を 自動的に生成するプログラムに関する説明もありました。 当時僕は構文解析を、再起下降方式を使った手書きのプログラムで行おうと思っていましたから、 それ以外の方式についての説明は、取りあえず飛ばして読むことにしました。 ５章は「構文主導翻訳」というタイトルです。純粋な意味での構文解析は、 決められたパターンに沿ってソースコードを最初から最後まで読むだけで、 それ以外のことは何もしないのですが、５章では構文解析の過程に沿って、決められた値を計算したり、 「構文木」というデータ構造を作るなどといった、 何らかの付加的な動作を規定する方法が説明されています。 この章を読まなかったら、何もしない処理系しか作れないので読みます。 ６章は、型チェックの方法が書かれています。型を一つしか持たない言語なら、型チェックはいらないのですが、 どうせ作るなら型の概念を扱えるインタープリタを作りたかったので、ここも読むことにしました。 ７章は「実行時環境」というタイトルで、実行時のメモリの管理の方法や、関数呼び出しの 実現方法、そして「記号表」に関する詳しい解説がなされています。 プログラムが実際にどうやって動くのか説明している重要な章ですので、この章も読む必要があります。 ８章は、中間コードという実行コードの中間的な表現に関する説明と、 それを生成する方法が書かれています。 多くのインタープリタ形式の処理系では、まずプログラム言語のソースコードを 中間コードに類するデータ形式に変換してから、 そのデータ形式を実行するための関数を呼び出して実行する方法が取られている、 と風の便りに聞いていました。 自作の処理系もその方式に従おうと思っていましたので、この章も読むことにしました。 ９章は中間コードから目的コードを生成する方法が述べられています。この章では目的コードを アセンブリ言語として説明がなされています。レジスタ（※）をうまく使ったコードを生成する方法や、 基本的な「最適化」処理の説明があって、目的のプロセッサの性質を考慮に入れた コードを作り出すテクニックが述べられています。 作ろうとしていたインタープリタは、中間コードを実行するタイプを想定していましたし、 「とにかく動けば良い」と思っていたので、レジスタの使用や最適化までは考えていませんでした。 そんなわけでこの章はパスしました。 １０章は最適化に関するより高度な技法が説明されています。この章もパスしました。 １０章までで、言語処理系の実現に関しての大きなトピックは全て解説されていて、１１章以降は、 コンパイラを開発する際の注意点や、ＣやＰａｓｃａｌなど、実際に稼動している処理系の解説などが 書かれています。別に読まなくても良かったのですが、読み易かったので読みました。 読み捨てようにも重要な事柄ばかりですので、結局は内容の半分程度は読むことにしました。 数ヶ月の間「あうー疲れた。今日は何と１ページも読んだから、 この辺で止めとこう。うーん、残り３６５ページ…」 という日々が続くこととなりました。 またこの本を読むのと並行して、再起下降方式を使った簡易ＢＡＳＩＣインタープリタ を、Ｃ＋＋で書いてみることにしました。(結局、頓挫しましたが。) 当時僕の手元にあった処理系のサンプルは、河野真治氏の講義のページからダウンロードした、 東工大の太田昌孝氏作のＭｉｃｒｏ−Ｃというコンパイラのソースくらいでした。 Ｍｉｃｒｏ−Ｃは非常に短いソースコードで作られていて、ちゃんとＣ言語のコンパイルができてしまう優れものでしたが、 短いだけに変数や関数の名前が簡潔すぎたり、広域変数(※）の値によって処理を変えている関数もあるので、 僕の読解力では一読して、「なるほど！」と思えるような代物ではありませんでした。 僕の場合、概念的な話を長々とされるよりは、実際のソースコードを読んだほうがすんなりと理解できます。 しかし、言語処理系のような複雑なプログラムだと、簡単に処理内容が 把握できるようなコードは、見つけられないんじゃないかと思っていました。 これは少々大変だな、と思っていたところに「野牛」を掲げた救世主が現れたのです… 注
| ||||||||||||||||||||||||||||||
言語処理系の制作に戻るもくじに戻る