yacc を遊ぶ：パーサーの動き確認

「THE UNIX PROGRAMMING ENVIRONMENT」のチャプター８のhocをサンプルに、yaccのパースの動きを確かめてみる。

この本では、hoc4でパーサーからインタプリタコードを生成するステップに移るが、 生成すべきコードとの結びつきがイマイチ想像できんかったから。

とりあえず、サンプル：

[hoc.y]

%{
#include <stdio.h>
#include <ctype.h>
#define YYSTYPE double
%}
%token NUMBER
%right  '='
%left   '+' '-' /* left associative, name precedence */
%left   '*' '/' /* left assoc., higher procedence */
%%
list:   /*nothing*/
        | list '\n'         { printf("list\n"); }
        | list expr '\n'    { printf("list expr: %f\n", $2); }
        ;

expr:   NUMBER              { printf("NUMBER: %f\n", $1); $$ = $1; }
        | expr '+' expr     { printf("%f + %f\n", $1, $3); $$ = $1 + $3; }
        | expr '*' expr     { printf("%f * %f\n", $1, $3); $$ = $1 * $3; }
        | '(' expr ')'      { printf("( %f )\n", $2); $$ = $2; }
        ;
%%
int main(int arc, char **argv) {
    yyparse();
}
int yyerror(char *s) {
    fprintf(stderr, "%s\n", s);
}
int yylex() {
    int c;

    while ((c=getchar()) == ' ' || c == '\t') {
        ;
    }
    if (c==EOF) {
        return 0;
    }
    if (c=='.' || isdigit(c)) { /*NUMBER*/
        ungetc(c, stdin);
        scanf("%lf", &yylval);
        return NUMBER;
    }
    return c;
}

[Makefile]

TARGET = hoc
OBJS = y.tab.o

all: $(TARGET)

$(TARGET): $(OBJS)
    gcc $(OBJS) -o $@

y.tab.o: y.tab.c
    gcc -c $< -o $@

y.tab.c: hoc.y
    yacc $<

clean:
    rm -f y.tab.c
    rm -f $(OBJS)
    rm -f $(TARGET)

さて、実行してみる。

hoc4_test $./hoc
1+2+3
NUMBER: 1.000000
NUMBER: 2.000000
1.000000 + 2.000000
NUMBER: 3.000000
3.000000 + 3.000000
list expr: 6.000000

なるほど、これ分かりやすい。 仮想スタックマシンの命令はPUSH、POP、 と演算命令なので以下のような感じかな。

NUMBER: 1.000000     :  -> PUSH (NUMBER)
NUMBER: 2.000000     :  -> PUSH (NUMBER)
1.000000 + 2.000000  :  -> res = ADD (POP() + POP()); PUSH (res);
NUMBER: 3.000000     :  -> PUSH (NUMBER)
3.000000 + 3.000000  :  -> res = ADD (POP() + POP()); PUSH (res);
list expr: 6.000000  :  -> 結果 = POP()

まあ、演算命令ADDはスタックから値を取り出すところも 命令の中に含まれるだろうが。