お気楽Ｃ言語プログラミング超入門

はじめに

今回は簡単な電卓プログラムを例題にして、「字句解析 (lexical analysis)」と「構文解析 (syntax analysys)」の基本的な手法について説明します。

●プログラミング言語処理系の基本的な構造

簡単な電卓プログラムといっても、基本的な構造はプログラミング言語の処理系 (インタプリタやコンパイラ) と大きな違いはありません。たとえばコンパイラの場合、次のような構造に分けることができます。

ソースコード → [字句解析] → [構文解析] → [意味解析] → [コード生成] → 目的コード


                        図 : コンパイラの構造

字句解析は入力された文字を順番に調べて、名前、数値、予約語、演算子など、意味のある「かたまり (トークン : token)」に分解します。構文解析はトークンの並びが構文規則にあっているかチェックします。構文解析を行うプログラムのことを「パーサ (parser)」と呼びます。

構文的には正しいプログラムでも、意味のうえでは間違っている場合があります。これをチェックするのが意味解析です。コード生成はターゲットマシンで実行するためのコード (機械語) を生成します。機械語ではなくアセンブリコードを出力するコンパイラも多いです。

インタプリタの場合、字句解析、構文解析、意味解析まではコンパイラとほとんど同じです。コードを生成するかわりに、プログラムを解釈して実行する処理が必要になります。最も原始的な方法は、ソースコートを読み込みながら逐次実行していくことです。この場合、字句解析、構文解析、意味解析を何度も繰り返し行うことになります。簡単な方法ですが、ループなどの繰り返しがある場合、無駄な処理が多くなるため実行速度は遅くなります。

もうひとつは、字句解析、構文解析、意味解析まで行った情報を何らかの形で保存しておき、それを解釈しながら実行していくことです。一般的には、解析して得られた情報は「構文木」という形で保存されます。また、プログラムを実行するための仮想マシンを用意し、そのマシンが直接実行できるコード (バイトコードなど) を生成する方法もあります。この場合、仮想マシンがコードを読み込みながら実行していくことになります。

今回作成する電卓プログラムは式を計算するだけの簡単なものなので、字句解析と構文解析ともに難しいところはほとんどありません。構文解析は「再帰降下法」を使うと簡単にプログラムできます。

●文法の表現

ほとんどのプログラミング言語は、「文脈自由文法 (context free grammer : CFG)」という方法で文法を定義することができます。文脈自由文法は「生成文法」と呼ばれる文法の一種です。文を生成する規則を定義し、その規則によって生成される文はその文法を満たしていると考えます。逆に、文法を満たしていない文は、その規則では生成することができない、ということになります。文脈自由文法は BNF (Backus Naur Form)、それを拡張した EBNF や構文図などで表すことができます。

ここで用語について簡単に説明します。「終端記号」は対象となるプログラミング言語で使用する記号のことで、BNF や EBNF では "..." で表します。「非端記号」は BNF や EBNF で用いる記号のことで、BNF では <...> で表します。

BNF の場合、構文規則は次の形式で表します。

非端記号 ::= 定義1 | 定義2 | ... | 定義n

ただし、| は「または」を表す。定義は終端記号や非端記号からなる。

簡単な例を示しましょう。a がいくつか並んだあとに b がいくつか並んだ記号列 (aa...bb...) を BNF であらわすと次のようになります。

<SeqAB> ::= <SeqA> <SeqB>
<SeqA>  ::= "a" | "a" <SeqA>
<SeqB>  ::= "b" | "b" <SeqB>

記号列を <SeqAB> とすると、a が並んだ記号列 <SeqA> のあとに b が並んだ記号列 <SeqB> が続けばいいので、定義は <SeqA> <SeqB> になります。<SeqA> は記号 "a" だけではなく "a" のあとに <SeqA> が続くパターンがあります。定義は "a" | "a" <SeqA> となります。<SeqB> も同様です。ここで、<SeqA> と <SeqB> は再帰的に定義されていることに注意してください。

この規則を適用することで、<SeqAB> を満たす任意の記号列を生成することができます。次の例を見てください。

<SeqAB> => <SeqA> <SeqB> => "a" <SeqA> <SeqB> => "a" "a" <SeqA> <SeqB>
 => "a" "a" "a" <SeqB> => "a" "a" "a" "b" <SeqB> => "a" "a" "a" "b" "b"

<SeqA> に定義 "a" <SeqA> を適用すると、"a" が一つ多い <SeqA> を生成することができます。定義 "a" を適用すると、そこで <SeqA> の生成は終了します。同様に <SeqB> の定義を適用することで記号列 <SeqB> を生成し、最終的には記号列 <SeqAB> を生成することができます。

文法が複雑になると BNF では読みにくくなることがあります。このような場合、EBNF を使うと便利です。EBNF で用いられる主な規則を示します。

非端記号は <...> で囲まない
::= のかわりに = を使う
非端記号や終端記号を並べる場合はカンマ , で区切る
規則の最後に記号 (セミコロンやピリオドなど) を付加する
{ α } : αの 0 回以上の繰り返し
[ α ] : αまたは空
( α ) : グループ化

EBNF で用いられる記号は正規表現と似ているので、正規表現がわかる方であれば EBNF を理解するのは難しくないでしょう。

<SeqAB> を EBNF で表すと次のようになります。

SeqAB = "a", { "a" }, "b", { "b" }.

BNF よりもわかりやすいと思います。

もうひとつ簡単な例を示しましょう。整数を EBNF で表すと、次のようになります。

整数       = ["+" | "-"], 無符号整数.
無符号整数 = 数字 | 非零数字, { 数字 }.
数字       = "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" | "0".
非零数字   = "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9".

        図 : 整数の EBNF

整数は +, - の符号が付いた (または省略された) 無符号整数で表すことができます。無符号整数は数字が 1 桁の場合と、2 桁以上ある場合に分けられます。桁が複数ある場合、先頭が 0 以外の数字 (非零数字) で、そのあとに数字がいくつか続きます。あとは、非零数字と数字を定義するだけです。

●式の構文

次は数値と演算子 +, - *, / とカッコ ( ) を使った数式の構文を考えてみましょう。式は数値と演算子をつないだものです。演算子には優先順位があり、+, - よりも *, / の計算を先に行わなければなりません。そこで、*, / でつながれたものを「項 (term)」として定義することにします。すると、式は項を演算子 +, - でつないだものとして定義することができます。

次に項の定義について考えます。数値と演算子 *, / だけならば簡単ですが、カッコが出てきたら、その中を式として計算しなければなりません。そこで、演算子 *, / でつながれるものを「因子 (factor)」として定義します。そうすると、項は因子を演算子 *, / でつないだものとして定義することができます。最後に、因子を定義します。これは数値またはカッコで囲まれた式となります。

なお、演算子 +, -, *, / は左結合なので、同じ優先順位の演算子は左から順番に計算していくことに注意してください。この規則を BNF と EBNF で表すと次のようになります。

[BNF]
 <式>  ::= <項> | <式> "+" <項> | <式> "-" <項>
 <項>  ::= <因子> | <項> "*" <因子> | <項> "/" <因子>
<因子> ::= <数値> | "(" <式> ")"

[EBNF]
 式  = 項, { ("+" | "-"), 項 }.
 項  = 因子, { ("*" | "/"), 因子 }.
因子 = 数値 | "(", 式, ")".

[注意] 数値の定義は省略

たとえば、式 12 + 34 + 56 * 78 と (12 + 34 + 56) * 78 を構文木であらわすと、次のようになります。

                 式
               ／│＼
             ／  │  ＼
           ／    │    ＼
         ／      │      ＼
       式        ＋        項
     ／│＼              ／│＼
   ／  │  ＼          ／  │  ＼
 項    ＋    項      因子  ＊  因子
 │          │       │        │
因子        因子      56        78
 │          │
 12          34

図 : 12 + 34 + 56 * 78 の構文木

                  式
                  │
                  項
                ／│＼
              ／  │  ＼
            因子  ＊   因子
           ／│＼       │
         ／  │  ＼     78
       （    式    ）
           ／│＼
         ／  │  ＼
       式    ＋   項
     ／│＼       │
   ／  │  ＼    因子
 項    ＋    項   │
 │          │   56
因子        因子
 │          │
 12          34

図 : (12 + 34 + 56) * 78 の構文木

構文木の場合、BNF の定義にそって構築すると簡単でわかりやすいでしょう。プログラムを作る場合は、EBNF の定義にそって行うと簡単です。EBNF で表した規則の左辺 (非端記号) を関数に割り当てます。右辺に出現する非端記号は対応する関数を呼び出します。終端記号は、正しい記号が現れていることを確認してそれを返します。選択 | は if や cond などで、{ } は繰り返しで表すことができます。

EBNF の定義が再帰的な構造になっているので、プログラムも再帰呼び出しの形になります。このような構文解析を「再帰降下法」と呼びます。具体的な説明はプログラムを作るところで行います。

●字句解析

それでは字句解析からプログラムを作っていきましょう。字句解析は入力ストリームから 1 記号ずつ読み取り、それをトークンに切り分けます。たとえば、数値を取得する場合、その数値が整数なのか実数なのか、また整数だとしてもそれが何桁あるのか、実際に記号を読み込んでみないとわかりません。このような場合、記号を先読みしておいて、それを大域変数に保存しておく方法がよく用いられます。

先読みした記号が数字であれば、さらに記号を読み込みます。そうでなければ、その記号を大域変数に保存しておいて、今まで読み込んだ記号から数値を生成します。そして、次の処理は大域変数に保存しておいた記号から始めればいいわけです。もちろん、記号を大域変数に保存しないで、記号を入力ストリームに戻す方法もあります。今回はオーソドックスに先読みした記号を大域変数に保存しておくことにしましょう。

記号を読み込むプログラムは次のようになります。

リスト : 記号の読み込み

// 外部変数
int ch;       // 記号
int token;    // トークン
double value; // 数値
jmp_buf err;  // エラー脱出用

// 記号の先読み
void nextch(void)
{
  ch = getchar();
}

// 先読み記号の取得
int getch(void)
{
  return ch;
}

外部変数 ch に先読みした記号 (文字型データ) を格納します。切り分けたトークンは token に、数値は value にセットします。今回の電卓プログラムでは、扱うことができる数値を浮動小数点数 (double) のみとします。トークンは enum で定義します。

リスト : トークンの定義

// トークン
enum {Eof, Number, Add, Sub, Mul, Div, Lpar, Rpar, Semic, Others};

// トークン名
char *token_name[] = {
  "EOF",
  "Number",
  "+",
  "-",
  "*",
  "/",
  "(",
  ")",
  ";",
  "Others",
};

セミコロン ';' は数式を入力するときの区切り記号として使います。電卓プログラムはセミコロンを見つけたら、入力された数式を計算して返します。式の最後には必ずセミコロンを入力してください。関数 nextch は標準入力から getchar で 1 バイト読み込み、それを ch にセットします。関数 getch は ch の値を返すだけです。

トークンを切り分ける関数 get_token は次のようになります。

リスト : トークンの切り分け

void get_token(void)
{
  // 空白文字の読み飛ばし
  while (isspace(getch())) nextch();
  if (isdigit(getch())) {
    token = Number;
    value = get_number();
  } else {
    switch(getch()){
    case '+':
      token = Add;
      nextch();
      break;
    case '-':
      token = Sub;
      nextch();
      break;
    case '*':
      token = Mul;
      nextch();
      break;
    case '/':
      token = Div;
      nextch();
      break;
    case '(':
      token = Lpar;
      nextch();
      break;
    case ')':
      token = Rpar;
      nextch();
      break;
    case ';':
      token = Semic;
      nextch();
      break;
    case EOF:
      token = Eof;
      break;
    default:
      token = Others;
    }
  }
}

最初に空白文字を読み飛ばします。空白文字のチェックはライブラリ (ctype.h) の関数 isspace で行います。改行文字も空白文字として認識されることに注意してください。空白文字の場合は nextch で次の文字を読み込みます。

次に、関数 isdigit で先読みした記号が数字 (0 - 9) かチェックします。そうであれば、関数 get_number を呼び出して数値に変換して value にセットします。token には Number をセットします。

それ以外の場合は getch() の値で処理を分岐します。'+', '-', '*', '/' の場合は演算子なので、該当するトークンを token にセットし、nextch で次の文字を読み込みます。'(' と ')' の場合はカッコを表すトークン Lpar, Rpar をセットします。

';' の場合はセミコロンを表すトークン Semic をセットします。EOF の場合はトークン Eof をセットします。この場合、nextch で次の文字を読み込む必要はありません。それ以外の場合はトークン others をセットします。

次は数値を求める関数 get_number を作ります。

リスト : 数値を求める

#define SIZE 1024

// 整数部をバッファに格納する
int get_fixnum(char *buff, int i)
{
  while (isdigit(getch())) {
    buff[i++] = getch();
    nextch();
  }
  return i;
}

double get_number(void)
{
  char buff[SIZE + 1];
  char *err;
  int i = get_fixnum(buff, 0);
  if (getch() == '.') {
    buff[i++] = getch();
    nextch();
    i = get_fixnum(buff,i);
  }
  if (getch() == 'e' || getch() == 'E') {
    buff[i++] = getch();
    nextch();
    if (getch() == '+' || getch() == '-') {
      buff[i++] = getch();
      nextch();
    }
    i = get_fixnum(buff, i);
  }
  buff[i] = '\0';
  double value = strtod(buff, &err);
  if (*err != '\0')
    error("get_number: not Number\n");
  return value;
}

配列 buff に数値を表すデータを格納します。関数 get_fixnum は数字 (0 - 9) を buff にセットします。最初に get_fixnum で数字を取り出します。次に、文字が '.' であれば実数なので、'.' と小数部を表す整数を buff にセットします。さらに、文字が 'e' または 'E' であれば、指数部の指定と判断してそれを buff にセットします。次に、符号 '+', '-' があるかチェックし、指数部を表す整数を get_fixnum で取得します。

最後に、buff をヌル文字で終端して、関数 strtod で数値データに変換します。変換不能な文字がある場合は関数 error でエラーを表示します。error は longjmp で大域脱出します。エラー処理はあとで説明します。

●構文解析

次は構文解析を作りましょう。字句解析と構文解析は別々に処理することも可能ですが、今回のプログラムでは構文解析を行う処理から関数 get_token を呼び出し、そのつど字句解析を行うことにします。プログラムは次のようになります。

リスト : 構文解析

// プロトタイプ宣言
double expression(void);
double term(void);
double factor(void);

// 式
double expression(void)
{
  double val = term();
  while (true) {
    switch (token) {
    case Add:
      get_token();
      val += term();
      break;
    case Sub:
      get_token();
      val -= term();
      break;
    default:
      return val;
    }
  }
}

// 項
double term(void)
{
  double val = factor();
  while (true) {
    switch (token) {
    case Mul:
      get_token();
      val *= factor();
      break;
    case Div:
      get_token();
      val /= factor();
      break;
    default:
      return val;
    } 
  }
}

// 因子
double factor(void)
{
  switch (token) {
  case Lpar:
    get_token();
    double val = expression();
    if (token == Rpar)
      get_token();
    else 
      error("')' expected");
    return val;
  case Number:
    get_token();
    return value;
  default:
    error("unexpected token");
  }
}

「式」に対応する関数が expression、「項」に対応する関数が term、「因子」に対応する関数が factor です。式の定義は EBNF で項, { ("+" | "-"), 項 } です。最初に term を呼び出して項の値を val にセットします。{ } に対応するのが while 文による繰り返しです。token が Add, Sub の場合、get_token で次のトークンを求め、term を呼び出して次の項の値を求め、val と演算を行います。token が Add, Sub 以外の場合は val を返します。

term も EBNF の定義因子, { ("*" | "/"), 因子} と同じ処理になります。最初に factor を呼び出して因子の値を val にセットします。term と同様に { } に対応するのが while 文による繰り返しです。token が Mul, Div の場合は、get_token で次のトークンを求め、factor を呼び出して次の因子の値を求め、val と演算を行います。token が Mul, Div 以外の場合は val を返します。

factor も EBNF の定義数値 | "(" 式 ")" と同じ処理になります。token が Lpar (左カッコ) の場合、get_token で次のトークンを求めてから、expression を再帰呼び出しして式の値を求めます。

次に、token の値が Rpar (右カッコ) であることをチェックします。右カッコがない場合は関数 error でエラーを送出します。Rpar の場合は、get_token で次のトークンを求めてから val を返します。token が Number の場合は value の値を返します。このとき、get_token で次のトークンを求めることに注意してください。token がそれ以外の値であればエラーを送出します。

●式の入力と評価

最後に式を入力して expression を評価する処理を作ります。次のリストを見てください。

リスト : 式の入力と評価

void toplevel(void)
{
  double val = expression();
  if (token == Semic) {
    printf("=> %.14g\nCalc> ", val);
    fflush(stdout);
  } else {
    error("invalid token");
  }
}

int main(void)
{
  printf("Calc> ");
  fflush(stdout);
  nextch();
  while (true) {
    if (!setjmp(err)) {
      get_token();
      if (token == Eof) break;
      toplevel();
    } else {
      // 入力のクリア
      while (getch() != '\n') nextch();
      printf("Calc> ");
      fflush(stdout);
    }
  }
  printf("bye\n");
  return 0;
}

関数 toplevel は expression を評価して入力された数式を計算します。そのあと、token がセミコロン (Semic) かチェックします。セミコロンであれば、expression の返り値 val を表示します。そうでなければ、入力された数式に誤りがあるのでエラーを送出します。

関数 main は電卓プログラムを実行します。まず最初にプロンプト "Calc> " を表示して、入力データを nextch で 1 記号先読みします。関数 fflush はストリームのバッファに溜まっているデータを吐き出す働きをします。

通常、ストリームはバッファリング動作を行いますが、これは標準入出力も例外ではありません。バッファリング動作には次の 3 種類があります。

完全バッファリング
入力はバッファが満たされるまで行われ、バッファが空になるまでファイルからの入力は行われない。出力はバッファが一杯になってからファイルに書き出される。
行バッファリング
入力はバッファが満たされるか改行文字に出会うまで行われ、バッファが空になるまでファイルからの入力は行われない。出力は改行文字に出会ったときにファイルに書き出される。
非バッファリング
バッファリング動作を行わない。

fopen でストリームをオープンすると完全バッファリングとして動作しますが、標準入出力は行バッファリングで動作します。したがって標準出力に文字を出力する場合、改行文字が含まれていなければ fflush を使って意識的にバッファの内容を吐き出す必要があるわけです。

それから、数式の "入力 - 実行 (評価) - 表示" を while 文で繰り返し行います。これを Read - Eval - Print - Loop (REPL) といいます。最初に、setjmp で外部変数 err に現在の状態を格納します。関数 error はここに大域脱出します。次に、get-token で切り分けたトークンが Eof ならば break で while 文を終了します。そうでなければ toplevel を実行します。

関数 error でジャンプしてきたときは、改行まで入力データを読み飛ばしてから、プロンプトを表示します。関数 error は次のようになります。

リスト : エラー

_Noreturn
void error(char *mes)
{
  fprintf(stderr, "%s, %s\n", mes, token_name[token]);
  longjmp(err, 1);
}

_Noreturn は最新の規格 (C11) で導入された関数指定子で、abort, exit, longjmp などを実行して、呼び出し元に戻ってこない関数であることを表します。関数 error は引数のエラーメッセージ mes を表示してから、longjmp で main の REPL に戻ります。

●実行例

それでは簡単な実行例を示します。

Calc> 1 - 2 + 3 * 4;
=> 11
Calc> (1 - 2 + 3) * 4;
=> 8
Calc> (1 - 2) * (3 + 4);
=> -7
Calc> 1.23456 * 1.11111;
=> 1.3717319616
Calc> 1.23456 / 1.11111;
=> 1.1111051111051
Calc> 1 / 2;
=> 0.5
Calc> (1 + 2;
')' expected, ;
Calc> 1 + 2);
invalid token, )
Calc> bye

プログラムの終了は Ctrl-D を入力してください。正常に動作していますね。

●単項演算子の追加

次は、単項演算子の + と - を追加しましょう。文法は次のようになります。

[EBNF]
 式  = 項 { ("+" | "-"), 項 }.
 項  = 因子 { ("*" | "/"), 因子 }.
因子 = 数値 | ("+" | "-"), 因子 | "(" 式 ")".

[注意] 数値の定義は省略

因子の定義に ("+" | "-"), 因子を追加するだけです。これで +3 や -5 を処理することができます。プログラムは次のようになります。

リスト : 単項演算子の追加

// 因子
double factor(void)
{
  switch (token) {
  case Lpar:
    get_token();
    double val = expression();
    if (token == Rpar)
      get_token();
    else 
      error("')' expected");
    return val;
  case Number:
    get_token();
    return value;
  case Add:
    get_token();
    return factor();
  case Sub:
    get_token();
    return -factor();
  default:
    error("unexpected token");
  }
}

因子で token が Add の場合は、get_token のあとに factor を再帰呼び出しするだけです。- の場合は get_token のあとに factor() を再帰呼び出しして、演算子 - で符号を反転するだけです。とても簡単ですね。

●実行例 (2)