最初の課題です。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. ミバエはバナナを好む
このように意味理解をしないと構文解析ができないという事例があります。英語の単語でよく使われるものには複数の品詞として使われるものが数多くありますので、決して例外とは言えないのです。英語という言語は動詞が軸になって動いていますので、動詞はどれだと探していけば構文は理解できるのですが、上の例では意味を理解しないと決定できないというジレンマがあるのです。
チョムスキーの功績は文法要素という考えを導入したことです。たとえば A pretty girl played the pianno. という文では、A pretty girl が主語であり、played が動詞であり、the pianoが目的語であるというようなつかみ方のことです。
有名なThis is the house that Jack built. というフレーズでは、This が主語、isが動詞で、the house that Jack builtが目的語となりますが、お気づきのように、目的語の中にさらに文が入っています。
自然言語はさておきプログラミング言語は人工言語ですので、形式論→意味論という標準理論が成立するように構築すればよいように思われますが、必ずしもうまくいっていません。とはいえ、数式の解釈だけに限ればチョムスキーの生成文法は大成功をおさめます。
プログラミング言語の場合は、形式解析を字句解析と構文解析という二段階に分けます。字句解析にはチョムスキー階層の正規文法(Regular Expression)が適用され、構文解析には文脈自由文法(Context Free Language)が使われます。それぞれのための有名なツールとしてlex, yaccがあります。
さて、とりあえず2+3*4と(2+3)*4を処理できるプログラムを作ります。文の要素としてexpr(式)、term(項)、factor(因子)があるとします。すると次のように文法を定義できます。なお、()*は、ゼロ個以上の並びを意味します。
expr : term (+term)* term : factor (*factor)* factor : 数値 または (expr)
これをプログラムにすると主要部のみですが、次のようになります。なお、入力にエラーがあっても無視するという仕様になっています。
void UngetToken(int token)
{
backedToken = token;
}
int GetToken()
{
if (backedToken >= 0)
{
int tk = backedToken;
backedToken = -1;
return tk;
}
int c = *pTop;
if ('0' <= c && c <= '9')
{
int x = 0;
while (1)
{
int cc = *pTop;
if ('0' <= cc && cc <= '9')
{
x *= 10;
x += cc - '0';
pTop++;
}
else
{
nVal = x;
return T_NUM;
}
}
}
pTop++;
if (c == '+')
return T_PLUS;
else if (c == '*')
return T_MUL;
else if (c == '(')
return T_IN;
else if (c == ')')
return T_OUT;
return T_EOF;
}
int factor()
{
int tk = GetToken();
if (tk == T_NUM)
return nVal;
if (tk == T_IN)
{
int x = expr();
int tk2 = GetToken();
// tk2 ! T_OUT -> error
return x;
}
}
int term()
{
int x = factor();
while (1)
{
int tk = GetToken();
if (tk == T_MUL)
{
x *= factor();
}
else
{
UngetToken(tk);
break;
}
}
return x;
}
int expr()
{
int x = term();
while (1)
{
int tk = GetToken();
if (tk == T_PLUS)
{
x += term();
}
else
{
UngetToken(tk);
break;
}
}
return x;
}
実行結果は次のようになっています。ちなみに、ここでは引き算と割り算は入っていません。これらは順番に気を付けることと、ゼロでの割り算は事前にチェックする必要があります。
