構文解析

C言語を使って簡単な構文解析のプログラムを書いた.
フルスクラッチではなくて字句解析にはre2c 構文解析にはlemonを使った.
いまどきはre2cとlemonを使うようです.

備忘録として簡単な電卓を作る過程をまとめておきたい.

長くなるので今回はre2cの使い方だけ記す.

電卓

四則演算の計算式を文字列として与える.
四則演算の規則に従って文字列を解析して計算する.
使える文字は数字と演算子(二項も単項も) それと括弧が使えるものとする.
空白は無視する.

インストール

MacではHomebrewを使ってre2cもlemonもインストールできます.
Windowsではre2cがここからlemonがここからダウンロードできる.

re2c

re2cは正規表現でパターンを指定するとマッチするトークン(文字の塊)を抜き出してくれる.
正規表現を含めたコードを書いてそれをre2cに通せばCのコードを生成してくれる.
例えば次のようなコードを書く.
名前をlexer.reとする.

#include <stdio.h>

char *scan(char *p)
{
/*!re2c
	re2c:define:YYCTYPE = "char";
	re2c:define:YYCURSOR = p;
	re2c:yyfill:enable = 0;
	re2c:yych:conversion = 1;
        re2c:indent:top = 1;
	[0-9]+ {return p;}
	'+' {return p;}
	'-' {return p;}
	"\000" {return (char *)0;}
	. {return "ERROR";}
*/
}

int main(int argc, char const *argv[])
{
	char *target = "12+2-31";
	char *temp = target;
	while ((target = scan(target)) != (char *)0)
	{
		fprintf(stderr, "%.*s\n", (int)(target - temp), temp);
		temp = target;
	}
	return 0;
}

実行してみると

[re2c] re2c -i -o lexer.c lexer.re                                    22:08:05
[re2c] gcc -O2 lexer.c                                                22:08:23
[re2c] ./a.out                                                        22:08:25
12
+
2
-
31

となってちゃんと数式を分解出来ていることがわかります.

コードの

/*!re2c
	re2c:define:YYCTYPE = "char";
	re2c:define:YYCURSOR = p;
	re2c:yyfill:enable = 0;
	re2c:yych:conversion = 1;
        re2c:indent:top = 1;
	[0-9]+ {return p;}
	'+' {return p;}
	'-' {return p;}
	"\000" {return (char *)0;}
	. {return "ERROR";}
*/

という部分がre2cへの命令になっています.
re2c…という行はお約束の部分です.
くわしくはmanを見てください.
終わりから5行目までがパターンマッチ指定です.
正規表現を使います.
ここさえちゃんとかけばどんな文字列でも簡単に分解することができます.

re2cの返す文字列はパターンマッチした文字よりあとの文字列になるのでパターンの文字を抽出したければscanを通す前の文字列を保管しておく必要がある,
こんかいはtempに保管してある.
あとはtempとtargetの差を出力すれば完了.