構文解析1 #Parser

概要

字句解析ができたので，実装した字句解析機を使って構文解析をしてみる．字句解析機の実装では，勝手にトークンの種類を定義したので，まずは構文解析で定義するトークンを使うように差し替える．その後，上向き構文解析器の一つであるyacc(の亜種であるbison)を使って簡単な文法を定義し，yaccと自作の字句解析機を合成して構文解析をしてみる．

構文の定義

yaccを使った構文は，以下のような構造で定義する

xxx.y

%{
// (1)宣言部
%}
// (2)共用体の定義
// (3)トークン定義
%%
// (4)構文の定義
%%
// (5)関数の定義

(1)
宣言部記述した文字列は，そのまま自動生成されるプログラムに反映される．そのため，#includeなどを書いておく

(2)
後述する構文定義では，トークンにマッチした時にある値を返す．特に指定しなければ数値が返されるが，構文木を作るときなど，返す値の型を任意に定義したいことがある．その場合，この部分にunionで型を定義する．すると，パーサーを自動生成したとき，YYSTYPEという名前で定義され，さらにYYSTYPE yylvalのように，yylvalという変数が自動生成される仕組みになっている．よって，字句解析機では，ヘッダファイル(後述)をincludeするたけで，この変数が使えるようになる．

(3)
プログラムで使うトークンを

%token LP
%token RP
...

のように定義していく．ここで定義したトークンは，自動生成されるヘッダファイルに反映される．

(4)
構文をBNFで定義していく．このとき，(3)で定義したトークンを使用することができる

(5)
任意の関数を定義する．自動生成されるプログラムをコンパイルするとき，yyerrorという関数を定義していないとエラーになるので，最低でもそれは定義しておく必要がある．

構文解析機の生成

文法を定義したら，次のコマンドで自動生成する

>bison --yacc -dv xxx.y

この結果，y.tab.c, y.tab.h, y.outputというファイルが自動生成される．y.tab.cがパーサ本体，y.tab.hはそのヘッダ，y.outputは構文解析に使う表が生成される．この表を生成することが上向き構文解析の肝である．

ここまでに定義した文法ファイルを載せておく

grammer.y

%{
#include <stdio.h>
#define YYDEBUG 1
%}
%union{
    int iv;
    double dv;
    char *name;
}

%token LP
%token RP
%token LC
%token RC
%token COMMA
%token LOGICAL_AND
%token LOGICAL_OR
%token EQ
%token ASSIGN_T
%token NE
%token GT
%token GE
%token LE
%token LT
%token SEMICOLON
%token COLON
%token ADD
%token SUB
%token MUL
%token DIV
%token MOD
%token ADD_ASSIGN_T
%token SUB_ASSIGN_T
%token MUL_ASSIGN_T
%token DIV_ASSIGN_T
%token MOD_ASSIGN_T
%token INCREMENT
%token DECREMENT
%token EXCLAMATION
%token DOT

%token INT_LITERAL
%token DOUBLE_LITERAL
%token IDENTIFIER


%token IF
%token ELSE
%token ELSIF
%token WHILE
%token FOR
%token RETURN
%token BREAK
%token CONTINUE
%token TRUE
%token FALSE
%token BOOLEAN_T
%token INT_T
%token DOUBLE_T
%token STRING_T

%%
translation_unit
    : statement
    ;
statement
    : IDENTIFIER LP RP SEMICOLON
    ;
%%
int
yyerror(char const *str)
{
    extern char *yytext;
    fprintf(stderr, "parser error near %s\n", yytext);
    return 0;
}

字句解析機のトークンを変更しテスト

自作した字句解析機では，これまでscantest.hにトークンを定義していたので，これを自動生成したものに差し替えてテストしてみる．scantest.hはscanner.c, scantest.c, keyword.keyファイルでincludeしていたので，そのかわりにy.tab.hをincludeする．

scanner.c

//#include "scantest.h" // 入れかえる
#include "y.tab.h"

変更後，コンパイルして実行すると，うまく言っていることが確認できる．

>make scant
>./scant
INT_LITERAL: 123456710
SEMICOLON:
INT_LITERAL: 1
ADD
INT_LITERAL: 2
SEMICOLON:
IF
SEMICOLON:
....

構文解析のテスト

字句解析器を構文解析器の自動生成プログラムと合成することはできたので，次に構文解析をしてみる．先の文法定義から，この構文解析器は，

print();

のように，識別子，（，），セミコロン，の並びを受理するので，そのようなテストファイルを書く．

tests/prog1.cs

print();

そして，以下のようなテストプログラムを生成する

parsetest.c

#include <stdio.h>
#include <stdlib.h>

int main(void) {

    extern int yyparse(void);
    extern FILE *yyin;
    yyin = fopen("tests/prog1.cs", "r");
    if (yyin == NULL) {
        fprintf(stderr, "cannot open file\n");
        exit(1);
    }

    if (yyparse()) {   // (1)構文解析の実行
        fprintf(stderr, "Parse Error\n");
        exit(1);
    }

    fclose(yyin);
    return 0;
}

externしているyyparseはy.tab.cに，yyinはscanner.cに定義されており，yyparseの中で暗黙的にyylexが呼ばれている．

(1)
入力位構文エラーがある場合にはtrueとなり，処理を中断する．エラーなくパースできればそのまま終了となる．

>/usr/bin/gcc -c -g -DDEBUG parsetest.c
>/usr/bin/gcc -o prst y.tab.o scanner.o keyword.o parsetest.o
>prst

このように何も表示されない．つまり，パースに成功している．
ここまでの実行は，以下のコマンドで確認できる．

>git clone https://github.com/hiro4669/csua.git
>cd csua
>git branch parse_test origin/parse_test
>git checkout parse_test
>make
>cd comp
>./prst

目次に戻る