プログラミング言語を作るの 2 章を読み進めた記録。興味があったけど手を出せずにいた自作プログラミング言語ですが、この記事を読んでまあつべこべ言わず手を動かそうと決心して、コードを書き始めた。成果物はここにあります。

処理系のうごき

プログラミング言語の処理系は通常以下のような流れで動く

電卓プログラムの字句解析

lex というレキシカルアナライザを自動生成してくれるツールを使う。UNIX 系の OS であれば最初から入っていることが多い。定義には正規表現を使う。

# 定義部: 必要なヘッダファイルや関数などを定義できる
%{
#include <stdio.h>

# 後ほど yacc によって生成されるヘッダファイルを include する
#include "y.tab.h"

# いまはおまじない的な理解でok
int yywrap(void) {
    return 1;
}
%}

# 規則部: 正規表現でマッチした場所の後ろのCコードが実行される
#     return で返されている書くシンボルは
#     yacc によって生成された y.tab.h の中で定義したものトークンに対応する
%%
"+"     return ADD;
"-"     return SUB;
"*"     return MUL;
"/"     return DIV;
"("     return LP;
")"     return RP;
"\n"    return CR;
([1-9][0-9]*)|0|([0-9]+\.[0-9]+) {
    double temp;
    sscanf(yytext, "%lf", &temp);
    yylval.double_value = temp;
    return DOUBLE_LITERAL;
}
[ \t]|[\s];
. {
    fprintf(stderr, "lexical error.\n");
    exit(1);
}
%%

電卓プログラムの構文解析

yacc というパーサを自動生成してくれるツールを使う。

# 定義部: いろいろと自由に定義できる場所
%{
#include <stdio.h>
#include <stdlib.h>
#define YYDEBUG 1
%}
# トークンと非終端子のとりうる型を共用体で表現している
# いまのところ double_value しかつかわれる見込みがないが、まあ例として...
%union {
    int     int_value;
    double  double_value;
}
# トークンの宣言： %token <TYPE> SYMBOL1, SYMBOL2...
%token <double_value>       DOUBLE_LITERAL
%token ADD SUB MUL DIV LP RP CR
%type <double_value> expression term primary_expression # 非終端子の型を定義している

# 規則部: 構文規則とCで書かれたアクション
%%
line_list
    : line
    | line_list line
    ;
line
    : expression CR
    {
        printf(">>%lf\n", $1);
    }
expression
    : term
    | expression ADD term
    {
        $$ = $1 + $3;
    }
    | expression SUB term
    {
        $$ = $1 - $3;
    }
    ;
term
    : primary_expression
    | term MUL primary_expression
    {
        $$ = $1 * $3;
    }
    | term DIV primary_expression
    {
        $$ = $1 / $3;
    }
    ;
primary_expression
    : DOUBLE_LITERAL
    | LP expression RP
    {
        $$ = $2;
    }
    | SUB DOUBLE_LITERAL
    {
        $$ = -$2;
    }
    ;
%%
int
yyerror(char const *str)
{
    extern char *yytext;
    fprintf(stderr, "parser error near %s\n", yytext);
    return 0;
}

int main(void)
{
    extern int yyparse(void);
    extern FILE *yyin;

    yyin = stdin;
    if (yyparse()) {
        fprintf(stderr, "Error ! Error ! Error !\n");
        exit(1);
    }
}

構文規則だけを抜き出すと以下のような感じ？

line_list  := line | line_list line
line       := expression CR
expression := term | expression AND term | expression SUB term
term       := primary_expression | term MUL primary_expression | term DIV primary_expression
primary_expression := DOUBLE_LITERAL | LP expression RP | SUB DOUBLE_LITERAL

動かす

Makefile を書いた

all: calc
y.tab.c: calc.y
 yacc -dv $<
lex.yy.c: calc.l
 lex $<
calc: y.tab.c lex.yy.c
 $(CC) -o $@ $^

以下のような感じ

$ make
$ ./calc
1+2
>>3.000000
1+2*3
>>7.000000

コマンドラインから、温かみのある手動ビルドをしたいときは以下のような具合

$ yacc -dv calc.y
$ lex calc.l
$ cc -o calc y.tab.c lex.yy.c

shift と reduce

パーサーのうごきをちゃんと押さえておく。1 + 2 * 3 という入力があったときの動きは以下の通り。

スタックの動き