C言語の構文解析

C言語で書かれたプログラムの構文解析を行ってみる。

とりあえずこのページでは、解析結果として構文木を出力するものとする。

yacc/lex

自力で構文解析を行っても良いのだが、それでは余りにも負担が大きいから、ここではyaccとlexを用いるものとする。

また、このページではyaccとlexの使用方法については解説を行わないものとする。そもそも、俺は人に解説できるほどyaccとlexに精通しているわけでもないし。

文法

ANSI Cのyaccとlexの定義は、ネット上に多数転がっているが、とりあえず、下記のものを挙げておく。

yacc : http://www.quut.com/c/ANSI-C-grammar-y.html

lex : http://www.quut.com/c/ANSI-C-grammar-l-1998.html

上記URLに示されている定義を用いれば、とりあえずC言語のプログラムを受理する解析機ができあがるようだ。

だがしかし、入力文字列がC言語の文法を満たしているか否か判断したところで、クソの役にも立ちはしない。C言語のプログラムを変換、あるいは実行するためには、構文木を生成してやらなければならない。

構文木の生成

基本的には、yaccの解析結果をそのまま木構造として記録するようにしてやれば、目的の構文木が得られる。

例えば、下記のように記述してやればいい。
SELECTION_STATEMENT
    : IF '(' EXPRESSION ')' STATEMENT
        {
            $$ = ノードの生成( $1, $2, $3, $4, $5 );
        }
    | IF '(' EXPRESSION ')' STATEMENT ELSE STATEMENT
        {
            $$ = ノードの生成( $1, $2, $3, $4, $5, $6, $7 );
        }
    | SWITCH '(' EXPRESSION ')' STATEMENT
        {
            $$ = ノードの生成( $1, $2, $3, $4, $5 );
        }
     ;
だが、よくあることだが、世の中そうは単純にはできていない。実は、C言語の構文木を出力するためには、かなり複雑な処理を作り込んでやらなければならない。

なぜかというと、C言語の文法にはyaccとlexの機能だけでは解析しきれない部分があるためだ。

識別子の種類の判別

yaccとlexの機能では解析しきれない部分とは何か。それは、識別子の種類を判断することだ。

具体的には、現れた識別子がtypedefされたデータ型の名前なのか、変数名なのか、enumされた定数なのかが判断できないのだ。
typedef int TYPENAME;
    ……
TYPENAME a;
人間の目には、「TYPENAME」がデータ型の名前であることは明らかである。だが、lexからしてみれば「TYPENAME」は単なる識別子の一つに過ぎない。また、yaccは、変数や名前を宣言してから使うと言ったことは一切考慮しないため、「TYPENAME」がデータ型を表していると言うことが判断できない。

判断できないなら、判断できないなりに、適当に構文木を生成してくれれば良さそうなものだが、そうも行かない。なぜならば、yaccは入力された記号（ここでは「TYPENAME」）の種類に応じて、その後に続く記号列を推定しながら処理を進めて行くため、「TYPENAME」がデータ型なのかそれ以外の識別子なのかが判らないと、その後に続く構文を決定できないのだ。

だから、lexで識別子を見つけたら、その識別子の種類を判断して、yaccに教えてやらなければならないのだ。

識別子表の構築

lexで識別子を見つけたときに、単純に識別子が見つかった事だけを通知するのでなく、見つかった識別子がデータ型なのか、定数なのか、あるいは他の識別子なのかを言ってやるためにはどうしたらいいのか。

構文解析と同時に、識別子の一覧表を作り、識別子が現れるたびにその一覧表を検索して、種別を決定できるようにしてやればいい。
ENUMERATOR
    : IDENTIFIER
        {
            $1をenumされた定数として、識別子表に登録する。
            $$ = ノードの生成( $1 );
        }
    | IDENTIFIER '=' CONSTANT_EXPRESSION
        {
            $1をenumされた定数として、識別子表に登録する。
            $$ = ノードの生成( $1, $2, $3 );
        }
    ;
……
DIRECT_DECLARATOR
    : IDENTIFIER
        {
            $1を新しく宣言された変数として、識別子表に登録する。
            $$ = ノードの生成( $1 );
        }
……
DECLARATION
    : DECLARATION_SPECIFIERS INIT_DECLARATOR_LIST ';'
        {
            $1の先頭の要素が"typedef"である場合は、
            $2に含まれる識別子は、typedefされたデータ型となる。
            $$ = ノードの生成( $1, $2, $3 );
        }
具体的には、識別子が現れたところで、識別子表に識別子を登録してやればいい。そのとき、変数宣言とenumによる定数の定義はすぐに判断できるので、然るべき属性を持った識別子として識別子表に登録してやればいい。

しかし、typedefされた名前の場合は、識別子が現れた瞬間には判断が付かない。typedefであることがはっきりするのは、typedefの一文全体を読み込んだときである。専門的には、DECLARATIONという構文要素が現れたときである。

だから、そのタイミングで、DECLARATION中に含まれる識別子に対して、typedefされた識別子であるという属性をつけてやることになる。

なぜそんな回りくどい事をしなければならないのか。

それは、"typedef"という単語が、"auto"や"register"といった、データ型に付けられた属性と同列に見られるためだ。また、typedefの宣言は、文法上では一種の変数宣言と見なされるためだ。

そのため、typedefされる識別子が現れた瞬間には、それがtypedefなのか何なのか、判断しづらいのだ。（もっとも、やろうと思えばできなくはないのだろうが）

識別子のスコープ

単純に識別子表を作成する、といっても、事態はそれ程単純ではない。

実は、C言語の識別子にはスコープという概念がある。判りやすいのは変数のスコープである。
int a;  /* (1) */

void foo() {
    int a;  /* (2) */
    a = 0;
    {
        int a;  /* (3) */
        a = 2;  /* (X) */
        printf( "1 : a = %d\n", a );
    }
    printf( "2 : a = %d\n", a );
}
詳しい解説は行わないが、(1)と(2)と(3)の「a」という変数は、それぞれ別の変数であり、識別子としても区別されるべきものである。

すなわち、(X)の式で、「a」について識別子表を検索したとき、見つけられるべきは(3)で宣言した変数の「a」であるべきであって、(1)や(2)で宣言した変数の「a」であってはならない。

判りにくいから、別の例を挙げる。
#include <stdio.h>

int main()
{
    int a;  /* (1) */
    a = 1;
    {
        typedef double a;  /* (2) */
        a b;  /* (X) */
        b = 2.3;
        printf( "%f\n", b );
    }
    printf( "%d\n", a );
    return 0;
}
身の毛もよだつような恐ろしいプログラムだが、文法上はANSI Cに準拠している。

上記のプログラムでは、(X)の位置にある「a」は、(2)で宣言された、データ型としての「a」であって、(1)で宣言された、変数としての「a」ではない。

だから、下記のようなプログラムは、コンパイルが通らない。
#include <stdio.h>

int main()
{
    int a;  /* (1) */
    a = 1;
    {
        typedef double a;  /* (2) */
        a = 5;  /* (Y) */
        printf( "%d\n", a );
    }
    printf( "%d\n", a );
    return 0;
}
(Y)の部分で文法エラーを起こす。

だから、スコープを意識した識別子表の構築と、検索機能を実装しなければならない。

スコープの関係

以下に、具体的なスコープについて示す。

ルール1
まず、一つ目のルールとして、各識別子は大きく三つのグループに分けられる。

グループ1 変数・typedefされた名前・enumされた定数・関数名

グループ2 structやenumの名前

グループ3 ラベル

typedefされた名前とは、例えば「typedef int TYPENAME;」という文における、「TYPENAME」の部分のことを言う。

enumされた名前とは、例えば「enum A { NAME1, NAME2 };」という文における、「NAME1」や「NAME2」の部分のことを言う。

structやenumの名前とは、例えば「struct TYPENAME { ・・・ };」という文における、「TYPENAME」の部分や、例えば「enum A { NAME1, NAME2 };」という文における、「A」の部分のことを言う。

ラベルとは、goto 文のジャンプ先として指定されるラベルのことを言う。

識別子は、上記グループ内で1つのスコープを形成する。つまり、異なるグループに属する識別子であれば、同じ名前を重複して使用することができるが、同一グループ内に属する識別子を、重複して使用することはできない。

だから、下記のようなプログラムは文法上許される事になる。
#include <stdio.h>

int main()
{
    struct IDENT1 {
        int i;
        int j;
    } IDENT1;
    IDENT1.i = 1;
    IDENT1.j = 2;
    printf( "%d : %d\n", IDENT1.i, IDENT1.j );
    goto IDENT1;
IDENT1:
    return 0;
}
上記プログラムでは、structの「IDENT1」と、変数名の「IDENT1」と、ラベル名の「IDENT1」が重複して使用されているが、これらは全て異なるスコープに属しているため、特に問題となることはない。

しかし、下記のようなプログラムは文法上許されない。
double main;
int main()
{
    return 0;
}
関数名と変数名は同一のスコープを形成するため、識別子「main」を重複して使用することはできない。
int main()
{
    typedef double IDENT1;
    unsigned long IDENT1;
}
typedefされた名前と変数名は同一のスコープを形成するため、識別子「IDENT1」を重複して使用することはできない。
int main()
{
    struct IDENT1 { int i; } a;
    enum IDENT1 { X, Y, Z } b;
}
structの名前とenumの名前は同一のスコープを形成するため、識別子「IDENT1」を重複して使用することはできない。
ルール2
グループ1とグループ2では、波カッコで括ると入れ子状のスコープが形成される。また、上位のスコープで使用されている識別子と同一の識別子を下位のスコープで使用した場合は、その下位のスコープの範囲内では、下位のスコープで定義された識別子が参照される。

このルールは、通常変数におけるスコープとして語られることが多いが、実際は変数名に限った話ではない。

例えば、下記のようなプログラムについて考えてみる。
#include <stdio.h>

int main()  /* (1) */
{
    int main;  /* (2) */
    main = 0;  /* (3) */
    {
        typedef double main;  /* (4) */
        main a;  /* (5) */
        a = 1.0;
        printf( "%f\n", a );
    }
    printf( "%d\n", main );  /* (6) */
    return 0;
}
やや読みにくいが、説明のために色を付けさせてもらった。

上記プログラムでは、赤い部分が一番上位のスコープを形成し、その中に青い部分のスコープが存在し、更にその中に、緑の部分のスコープが入り込んでいる。

まず、(1))の「main」は関数名である。これは、赤い部分に記載されているため、一番上位のスコープに属している。

(2)の「main」は、変数名である。これは、青い部分に記載されているため、二番目のスコープに属している。よって、青い部分の中で「main」という識別子を使用した場合には、それはint型の変数と見なされる。

(4)の「main」は、データ型である。これは緑の部分に記載されているため、三番目のスコープに属している。よって、緑の部分の中で「main」という識別子を使用した場合には、それはdouble型の別名と見なされる。

また、今更説明の必要はないだろうが、識別子が重複しない限りは、下位のスコープの範囲内から、上位のスコープで定義された識別子を参照することができる。しかし、上位のスコープの範囲内から、下位のスコープで定義された識別子を参照することはできない。

スコープの形成にも、いろいろと細かいルールがある。基本的には、入れ子状のスコープは波カッコによって形成される。逆に言えば、波カッコが現れた場合には入れ子状のスコープが形成されると言うことになる。

例えば、下記のようなプログラムについて考えてみる。
#include <stdio.h>
int main()
{
  struct S {
    const char *i;
  } i;
  {
    double i = -2.3;
    switch ( 0 ) {
        int i = 10;
    default :
        printf( "%d\n", i );
        break;
    }
    printf( "%f\n", i );
  }
  i.i = "Hell world!";
  printf( "%s\n", i.i );
  return 0;
}
同じ色で塗り分けられた範囲は、同一のスコープを形成する。

だが、この波カッコルールにはいくつかの例外が存在する。

まず一点目は、enumの波カッコだ。enumの波カッコはスコープを形成しない。
#include <stdio.h>
int main()
{
  enum A {
    A1,
    A2
  };
  int A1;  /* (1) */
  A1 = 2;
  printf( "%d\n", A1 );
  return 0;
}
このプログラムは、(1)の部分でコンパイルに失敗する。なぜならば、enumの波カッコはスコープを形成しないので、識別子A1が重複するためである。

二点目は、関数の引数である。関数の引数は、波カッコの範囲からはずれているにもかかわらず、関数内で定義される自動変数と同等に取り扱われる。
#include <stdio.h>
int main( int argc, char *argv[] )
{
  double argc = 2.3;  /* (1) */
  printf( "%f\n", argc );
  return 0;
}
識別子「argc」と「argv」は、関数の範囲を表す波カッコの中で定義されたかのごとくに取り扱われる。よって、上記のプログラムは(1)の部分でコンパイルに失敗する。

ただし、このルールは関数名には適用されない。すなわち、識別子「main」は、波カッコの外で定義されたものとして取り扱われる。
ルール3

ラベル名のスコープは、関数単位に構築される。

これは余り説明の必要はないものと思われる。要は、ラベル名は波カッコによる影響は受けないと言うことだ。単純に、一つの関数内でのみ一意になっていればいいようである。

以上のルールに従い、構文解析と同時に識別子表の構築・検索を行うようにすれば、構文木を生成してやることができる。

プログラム例

例のごとく実例を示すが、今回はそれ程単純なプログラムというわけにはいかない。結構長い。

とりあえず、圧縮したものを公開しておく。

cparse.zip 37.5KB

コンパイル方法

ダウンロードしたファイルを展開して、makeを実行すれば、コンパイルできる。

ただし、使用するyaccやlex・コンパイラは、自分でmakefileを編集して設定する必要がある。

実行方法

デフォルトでは、Cのプログラムを標準入力から読み込み、標準エラー出力に解析結果を出力するようになっている。

しかし、以下の引数を指定することにより、入出力先のファイルを変更することができる。

a.exe -r 入力ファイル名 -d 出力ファイル名

何で入力が-rで、出力が-dなのか、ということについては質問してはいけない。

制限事項

このプログラムは何分サンプルである都合上、余り難しいことは考えないで作られている。その為、下記の制限事項がある。

入力されるプログラムには、文法エラーは無いものと想定している。もし、解析に失敗した場合には、適当なメッセージを表示して終了してしまう。

標準のANSI C89にのみ対応している。コンパイラ依存の拡張機能については、一切サポートしていない。

入力されるプログラムは、あらかじめプリプロセッサによる前処理が行われていることを前提としている。その為、コメントやプリプロセッサディレクティブは処理できない。

特に、2と3の制約はかなり厳しいものである。

一般的にいって、各コンパイラは、ヘッダファイル中ではコンパイラ独自の拡張機能を平気で使用している。互換性など微塵も考慮していないのが普通である。そのため、何も考えずにプリプロセッサを通したプログラムをこのサンプルで処理しようとしても、うまくいかないことが多い。

現実的には、ヘッダファイルをインクルードせずに、手で書いた小さなプログラムを解析するのが精一杯であると思われる。

実行例

簡単なプログラムと、それを処理した結果を示して、出力結果の見方を説明しておく。

以下のようなプログラムを処理する。
int main()
{
  int i = 0;
  i = i + 1;
  return i;
}
このプログラムを処理すると、次のような出力が得られる。

exp.txt 19.8KB

出力結果の3行目から、構文木が出力されている。また、「---- Ident Table 0 ---……」と書かれているところからは、識別子表が3つ出力されている。

Ident Table 0には、変数・typedefされた名前・enumされた定数・関数名のグループが登録される。Ident Table 1には、structやenumの名前が登録される。Ident Table 2には、ラベル名が登録される。

詳細な出力内容については、プログラムのソースコードを参照してもらうしかないが、とりあえず、下記の一行についてだけ説明しておく。
adr = 0x00886E28
type = STET_IDENTIFIER
type var =  0
Line Numebr =    2
union_type = STUT_IDENTIFIER
ident adr = 0x00886DF4
ident name = main
上記は、12行目の内容を、適宜改行して記載したものである。

adrは、この構文要素のアドレス値を示している。

typeとtype verは、この構文要素の種別を表している。ここでは、識別子を保持していることを示している。

Line Numberは、ソースコード上での行番号を示している。ただしこの値は、当該の構文要素を構成する記述が含まれる最後の行の行番号を示している。

union_typeは、この構文要素が保持する子ノードの種類を示している。ここでは、識別子の情報を保持していることを示している。

ident adrは、当該の識別子に関する情報を保持している、識別子表中のエントリのアドレスを示している。

ident nameは、識別子の名前を表している。ここでは、「main」という識別子を保持していることを示している。

ident adrに「0x00886DF4」と記載されているので、この文字列で出力結果を検索すると、117行目に行き当たる。そこには、下記のような内容が記載されている。
ptr = 0x00886DF4
name = main
type = ITIT_FUNCTION_NAME
BraceNumber = 0
SEU_BraceNumber = -1
pDeclarationSpecifiers = 0x00886DC0
pDeclarator = 0x00886EEC
pInitializer = 0x00000000
IsArray = FALSE
これは、識別子表中の、mainという識別子の情報そのものである。

詳しい解説は行わないが、識別子の名前がmainであり、それが関数名であることなどが判る。

最後に

このページで公開しているサンプルについては、特に著作権を主張するつもりもないから、勝手に使ってもらっても構わない。だがしかし、俺はこのサンプルについては何に保証もしないし、バグが無いとも言い切れない。

使うのなら、全て自己責任の上で。