最初の課題です。2+3*4と入力したら14と出力し、(2+3)*4と入力したら20と出力するプログラムを作れ。やることは小学生レベルですが、プログラムは簡単ではありません。とはいえ、インチキコーディングもあります。こんな感じです。
if (!strcmp(input, "2+3*4"))
printf("14\n");
else
printf("20\n");
これは、完成したらこんな感じになりますというデモの時のダミーコードです。ちゃんとした中身を入れるのは、かなりの仕事です。さて、K&Rと言いますと初心者には勧められないテキストとして有名です。ここではSecond Edition(英語版)をベースに話を進めますが、hello worldのプログラムを書く目的として、to learn a new programming languageとあります。すでに複数のプログラミング言語を習得した人が対象だと思いますよね。ちなみに僕はFortran, Basic, COBOL, アセンブラなどを身につけた後で、このテキストを読みました。
このテキストには、最後にラスボスがいます。リファレンスマニュアルのA13.Grammarという箇所です。ここには、Cの文法が厳密な形で定義されています。文法(Syntax)というのは、骨組みのことです。骨だけで身がない、食べられる肉がないとも言えます。肉の部分は意味論(Semantics)と言いますが、それはテキスト全体にあります。
プログラミング言語の歴史を考えると、エイダ・ラブレスのころは機械語で直接コーディングしていました。1950年代の前半にFortranが登場します。Fortranという名前がFormula Translatorから来ているように、計算式を普通に書けるようにしようというのが、最初の目的でした。そこでは、+を)+(で置き換えて、全体を()でくくるというテクニックが使われていたそうです。2+3*4は(2)+(3*4)となるわけです。このFortranを開発したのはバッカスなどですが、同じ時期にチョムスキーという人が生成文法を発表します。その応用事例として計算式のコンパイルに使ったのがALGOLです。そこからpascalやCなど現代のプログラミング言語の主流となるALGOL系の言語が続々と登場します。このチョムスキー流の言語理解ということを知らないとK&Rの意図するところも分からないということになります。
意味が分からないと言われることもあるK&Rですが、Cとは構造化アセンブラである(Low Levelとテキストにあります)と理解すればなんと素晴らしいと思います。よく言われる文字列コピーの while(*p++=*q++); という箇所ですが、これはアセンブラに置き換えようとすると、実にぴったりなんですね。僕なんかはアセンブラの方からCに入ったので、なんてカッコいいのだと感動したものです。
さて、チョムスキーの生成文法には標準理論という言葉があります。それは、まず形式論で文の構造を解析し、そのあとで意味論によって内容を理解するというものです。もともとチョムスキーは人文系の学者なので英語などの自然言語を対象にしていますが、意味論を考えないと構文が決定できないという事例は多数あります。たとえば、次の二つの文を見てください。
Time flies like an arrow. 時は矢のように飛ぶ
Fruit flies like a banana. ミバエはバナナを好む
このように意味理解をしないと構文解析ができないという事例があります。英語の単語でよく使われるものには複数の品詞として使われるものが数多くありますので、決して例外とは言えないのです。英語という言語は動詞が軸になって動いていますので、動詞はどれだと探していけば構文は理解できるのですが、上の例では意味を理解しないと決定できないというジレンマがあるのです。
自然言語はさておきプログラミング言語は人工言語ですので、形式論→意味論という標準理論が成立するように構築すればよいように思われますが、必ずしもうまくいっていません。とはいえ、数式の解釈だけに限ればチョムスキーの生成文法は大成功をおさめます。
プログラミング言語の場合は、形式解析を字句解析と構文解析という二段階に分けます。字句解析にはチョムスキー階層の正規文法(Regular Expression)が適用され、構文解析には文脈自由文法(Context Free Language)が使われます。それぞれのための有名なツールとしてlex, yaccがあります。
字句解析とは、文字の並びから単語の並びに切り分けることです。英語であれば空白で区切られたものが単語です。プログラミング言語では数値、変数、演算子などがあります。最初の2+3*4を字句解析すると、数値(2)、演算子(+)、数値(3)、演算子(*)、数値(4)という五つの単語からできた式であるということになります。単語の種類のことをトークン(token)と言います。数値の中身などを属性と言います。
構文解析のためには、数式というものをトップダウンに定義していきます。こんな感じです。
数式とは 項(term) または 項(term) + 因子(factor)
因子とは 因子(factor) または 因子(factor)*要素(prim)
要素とは 数値 または (数式)
最後に、カッコでくくられた数式は一番下のレベルの要素であるという定義になっています。これは再帰的な定義です。ご存じのようにかっこを組み合わせて行けばいくらでも複雑な数式が作れるのですから、これは当然のことです。ただし、プログラミングとしては、再帰呼び出しを行わないと余計に複雑なコーディングになりますし、再帰呼び出しをすれば技術レベルが格段にアップしてしまいます。
それでは、次には具体的なコーディングをお見せしようかと思います。とはいえ、なにせ再帰呼び出しですので、簡単ということはない気がします。