プログラミング言語を作る (1)

はじめに

学習目的でスクリプト言語を作っている。
github.com

日々使っている言語も仕組みを知らなければ高いパフォーマンスを出せないし、仕組みを知りたければ自分で作ってみるのが一番だ。

単純な四則演算からはじめて、これまでに以下の機能を実装した。

• 整数/実数
• 四則演算 (+, -, * , /, %)
• 文字列
• 変数代入
• 変数参照
• 比較演算 (==, !=, <, >, <=, >=)
• 組込関数の呼び出し
• ユーザー関数の定義
• ユーザー関数の呼び出し
• while文
• if (elsif, else) 文
• 1行コメント

だいぶ混み入ってきたので、ここらで一旦情報をまとめておく。

環境

言語はC言語を使う。
どの言語を使っても良いのだが、スクリプト言語上にスクリプト言語を作ってもしょうがない。Javaも考えたが、PHPやRubyと同じ土俵で仕組みを勉強したかったから。
C++であればオブジェクト指向で構造的に作れるので、今switchで分岐しているような処理はかなり綺麗に書けると思う。
字句解析、構文解析には定番のflex / bisonを使った。
字句解析は正規表現なので自前で作ることもできそうだ。構文解析についても作り方を紹介している書籍があったが、今回はひとまずbisonにお任せした。

仕組み

言語開発の全体の流れは、

1. 字句解析 ( = language.l )
2. 構文解析 ( = language.y )
3. 構文木作成 ( = language.c )
4. 構文木評価 ( = language.c )

となる。

実装

字句解析

字句解析はflexのルールに則って定義する。前述の通り正規表現なのでわかりやすい。

%{
#include <stdio.h>
#include <stdlib.h>
#include "language.tab.h"
#include "language.h"
%}

%%
"while" { return WHILE; }
"elsif" { return ELSIF; }
"function" { return DECLARE; }
"if" { return IF; }
"else" { return ELSE; }
-?[0-9]+"."[0-9]+ { yylval.str = yytext; return NUMBER; }
-?[0-9]+ { yylval.str = yytext; return NUMBER; }
"println" { yylval.fn = B_print; return FUNC; }
"\n"
[a-zA-Z][a-zA-Z0-9_]* { yylval.sym = lookup(yytext); return IDENT; }
\"(\\\\.|[^\"])*\" { yylval.str = yytext; return STRING; }
"//"[^\n]*\n /* ignore one line comment */
"+" |
"-" |
"*" |
"/" |
"%" |
"=" |
"|" |
"," |
";" |
"{" |
"}" |
"(" |
")" { return yytext[0]; }
"==" { yylval.fn = 1; return CMP; }
"!=" { yylval.fn = 2; return CMP; }
">" { yylval.fn = 3; return CMP; }
"<" { yylval.fn = 4; return CMP; }
">=" { yylval.fn = 5; return CMP; }
"<=" { yylval.fn = 6; return CMP; }
[ \t] /* ignore white space */
. { yyerror("Mystery character %c\n", *yytext); }
%%

yytextは入力文字列、yylavalは構文解析への出力文字列となる。yylval.strやyylval.fnなどの型はlanguage.yで共用体として定義しているので、これにあったものを選択する。
ここではステート文、関数定義修飾子、整数、実数、println(組込関数)、変数、文字列、1行コメント、演算子、スペース文字、改行文字を定義し、それ以外はエラーとしている。

構文解析

構文解析では、まず字句解析から受け取るトークンの型を共用体で定義する。

%union {
	char* str;
	struct ast *a;
	struct symbol *sym;
	struct symlist *sl;
	int fn;
}

整数に関してはもともとint型で定義していたが、実数を実装した段階でchar*型に変更し、構文木作成時に変換する方法に変更した。

次に、これらの型とトークンを紐づける。

%token <str> NUMBER
%token <sym> IDENT
%token <str> STRING
%token <fn> CMP
%token <fn> FUNC
%token WHILE
%token IF
%token ELSE
%token ELSIF
%token DECLARE
%type <a> factor
%type <a> exp explist
%type <sl> symlist
%type <a> let call declare  if else elsif elsiflist elselist ifstmt
%type <a> stmt stmts
%type <a> program

終端記号はtokenで、非終端記号はtypeで定義する。

演算子の結合優先順位も設定できる。

%left '+' '-'
%left '*' '/' '%'
%right '='

また、下にある演算子が優先されるので、乗除演算が加減演算に優先することもここで表現できる。
これにより構文ルールで乗除と加減を分けて定義する必要がなくなる。

構文解析の肝となる定義は、BNFを使って表現する。

%%
program
	: stmts { eval($1); }
	;
stmts
	: stmt
	| stmt stmts { $$ = newast(NODE_STMTS, NULL,  $1, $2); }
	;
stmt
	: let
	| call
	| declare
	| WHILE '(' exp ')' '{' stmts '}' { $$ = newast(NODE_WHILE, NULL, $3, $6); }
	| ifstmt
	;
let
	: IDENT '=' exp ';'{ $$ = newasgn($1, $3); }
	;
call
	: IDENT '(' explist ')' ';' { $$ = newcall($1, $3); }
	| IDENT '(' ')' ';' { $$ = newcall($1,  NULL); }
	| FUNC '(' explist ')' ';' { $$ = newfunc($1, $3); }
	;
declare
	: DECLARE IDENT '(' symlist ')' '{' stmts '}' { dodef($2, $4, $7); }
	| DECLARE IDENT '(' ')' '{' stmts '}' { dodef($2, NULL, $6); }
	;
ifstmt
	: if
	| if elselist { $$ = newast(NODE_SELECT, NULL, $1, $2); }
	;
elselist
	: elsiflist
	| else
	| elsiflist else { $$ = newast(NODE_SELECT, NULL, $1, $2); }
	;
elsiflist
	: elsif
	| elsif elsiflist { $$ = newast(NODE_SELECT, NULL, $1, $2); }
	;
elsif
	: ELSIF '(' exp ')' '{' stmts '}' { $$ = newast(NODE_IF, NULL, $3, $6); }
	;
else
	: ELSE '{' stmts '}' { $$ = newast(NODE_ELSE, NULL, NULL, $3); }
	;
if
	: IF '(' exp ')' '{' stmts '}' { $$ = newast(NODE_IF, NULL, $3, $6); }
	;
symlist
	: IDENT { $$ = newsymlist($1, NULL); }
	| IDENT ',' symlist { $$ = newsymlist($1, $3); }
	;
explist
	: exp ',' explist { $$ = newast(NODE_EXPLIST, NULL,  $1, $3); }
	| exp
	;
exp
	: factor CMP factor { $$ = newcmp($2, $1, $3); }
	| factor '+' factor { $$ = newast(NODE_EXP, "+", $1, $3); }
	| factor '-' factor { $$ = newast(NODE_EXP, "-", $1, $3); }
	| factor '*' factor { $$ = newast(NODE_EXP, "*", $1, $3); }
	| factor '/' factor { $$ = newast(NODE_EXP, "/", $1, $3); }
	| factor '%' factor { $$ = newast(NODE_EXP, "%", $1, $3); }
	| factor
	;
factor
	: '(' exp ')' { $$ = $2; }
	| NUMBER { $$ = newnum($1); }
	| IDENT { $$ = newref($1); }
	| STRING { $$ = newast(NODE_STR, $1, NULL, NULL); }
	;
%%

factorはプライマリとなる数値表現、変数、文字列を表している。

expはfactorそのもの、もしくはfactor同士の演算を表している。
最初は整数の四則演算だけだったので、ここで直接計算結果を返して完結していたが、言語を作る以上ここで構文木を作る必要がある。
newastやnewasgnなどの関数はそのためのものである。

explistはexpそのもの、もしくはexpをカンマ区切りで連ねた物である。
exp (',' exp)*のような書き方ができなかったので、このような再帰表現を用いている。

symlistは変数、または変数をカンマ区切りで連ねたものである。これはexplistを同じ方法で定義している。

ifとelseはそれぞれif文とelse文の定義。
これだけなら簡単なのだが、elsifは0回以上の繰り返しを想定しないといけないため、elsif、elsiflistを定義し、elseと組み合わせたelselistも定義している。
最終的にはifstmtへとreduceされる。

declareはユーザー関数の定義である。

callはユーザー関数とビルトイン関数の定義。
組込関数ではprintfなどCのネイティブ関数を用いているため、ユーザー定義関数とは明確に区別している。
ユーザー関数については引数のあるなし両方を定義している。

letは変数へのexpの代入である。

stmtはletやcall、whileやifなどの文を指す。
stmtsはstmtの繰り返しで、プログラム全体ど同義である。

最後にprogramはstmtsそのものを指すが、ここまでreduceされた段階で全ての構文木が作成されているので、evalを呼び出してプログラムを実行する。

長くなるので次回へ続く。

参考資料

今回は直接参照することはなかったが、Javaを使った言語作成方法を解説していておもしろい。
自前で構文解析を行っているので、bisonを使わない場合にも参考になるだろう。

2週間でできる! スクリプト言語の作り方 (Software Design ｐlus)

flexとbisonについての書籍。
中はほとんど読んでないが、今回のプログラムは本書のサンプルをベースに始めている。
SQLの解析も行っているので、今後読み進めたい。

Flex & Bison