Schemeをつくろう(2) 字句解析と構文解析

字句解析は作ってあったので、昨日作ったリスト部分と結合していきたいと思います。

まず

デバッグが容易になるようにファイルと文字ストリームを抽象化したStreamクラスを作りました。

/* stream.h */
struct Stream {
    union {
        char *string;
        FILE *fp;
    } input;
    int end;
    int buffer; /* for string */
    int  (*next)(struct Stream *);
    void (*back)(struct Stream *, int);
};
typedef struct Stream Stream;

void string_stream_init(Stream *s, char *str);
void file_stream_init(Stream *s, FILE *fp);

stream->next()みたいな感じで、クラス風に使えます。なかなか使い勝手が良いです。

字句解析

字句解析はK&Rそのままって感じになりました。

構文解析

構文解析部分でちょっと泣きそうに。

ツリーが解析できん!!

掘っても掘っても先が見えてこねぇ(笑

迷った挙句、以下の事に気付かされました。

構文解析でも押し戻しが必要。
リストの末尾に追加しなければならないので、appendが必要。(追記:再帰で書けばappendは必要ない)

特に、構文解析でも「押し戻しがいる」ということに気付くのに時間がかかりました。

ちなみにgaucheのソースを見たら字句解析と構文解析を同時に行ってました。激しくスマートです。

書くべぇ〜

ヘッダ。

/* lex.h */

char *yytext; /* global */

object *perse(Stream *s);

実装。

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

#include "stream.h"
#include "list.h"
#include "lex.h"

enum { L_EOF, L_NUM, L_SYMBOL, L_UNGET };

static int yytype = L_UNGET;

static int lex(Stream *s);
static void unget_lex(int t);

static object *append(object *list1, object *list2); /* tmp */


static int lex(Stream *s)
{
    int c;
    int type;
    int yyindex = 0;

    if (yytype != L_UNGET) {
        int unget = yytype;
        yytype = L_UNGET;
        return unget;
    }

    while(isspace(c = s->next(s)))
        ;
    switch (c) {
    case '\0' : case EOF :
        type = L_EOF;
        break;
    case '0': case '1': case '2': case '3': case '4':
    case '5': case '6': case '7': case '8': case '9':
        do
            yytext[yyindex++] = c;
        while(isdigit(c = s->next(s)));
        s->back(s, c);
        type = L_NUM;
        break;
    case '(': case ')':
        type = c;
        break;
    default :
        do
            yytext[yyindex++] = c;
        while (c = s->next(s), !(isspace(c) ||
                                 c == '\0' || c == EOF ||
                                 c == '(' || c == ')'));
        s->back(s, c);
        type = L_SYMBOL;
        break;
    }
    yytext[yyindex] = '\0';
    return type;
}

static void unget_lex(int t)
{
    yytype = t;
}


object *perse(Stream *s)
{
    int type = lex(s);

    switch (type) {
    case L_EOF :
        return NULL;
    case L_NUM :
        return integer(atoi(yytext));
    case L_SYMBOL :
        return symbol(yytext);
    case '(' :
        /* TODO : dot & error */
        { object *o = null();
            for(;;) {
                object *p;
                type = lex(s);
                if (type == ')')
                    return o;
                else {
                    unget_lex(type);
                    o = append(o, cons(perse(s), null()));
                }
            }
        }
    default :
        // TODO : error
        break;
    }
}


/* append (適当) */
static object *append(object *list1, object *list2)
{
    object *res;

    if (is_null(list1))
        res = list2;
    else
        res = cons(car(list1), append(cdr(list1), list2));

    free_object(list1); /* GC */
    return res;
}

appendでリストのコピーをしているのでGCを欲してます(笑

さて、テストを書きます。

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

#include "stream.h"
#include "list.h"
#include "lex.h"

#define DEBUG_STDIN 0

static void prompt(void);

static int add_iter(int n, object *o);
static object *add(object *o);

int main(void)
{
    Stream s;
    object *o;

#if DEBUG_STDIN
    file_stream_init(&s, stdin);
#else
    char *input = "\
(+ 1 2 3 4 5 6 7 8 9 10) \
(+) \
(hello (Scheme) World!!) \
";

    printf("input> %s\n", input);
    string_stream_init(&s, input);
#endif

    yytext = malloc(1024);

    prompt();
    while ((o = perse(&s)) != NULL) {
        if (is_pair(o) && is_symbol(car(o)) &&
            strcmp(get_symbol(car(o)), "+") == 0)
            o = add(cdr(o));  /* eval :) */
        display(o);
        newline();
        prompt();
        free_objects(o);
    }

    free(yytext);

    return EXIT_SUCCESS;
}

/* test */
static void prompt(void)
{
#if DEBUG_STDIN
    printf("scm> ");
    fflush(NULL);
#endif
}

/* add (eval) */
static int add_iter(int n, object *o)
{
    int sum = (is_null(o)) ?
        n :
        add_iter(n + get_integer(car(o)), cdr(o));

    free_object(o);  /* GC */

    return sum;
}

static object *add(object *o)
{
    return integer(add_iter(0, o));
}

なげぇなぁ〜

動かしてみます。

input> (+ 1 2 3 4 5 6 7 8 9 10) (+) (hello (Scheme) World!!)
55
0
(hello (Scheme) World!!)

55って!!

可変長の足し算作っちゃいました。

足し算しか出来ないSchemeが出来ました。

Schemeへの道のりは遠そうだ・・・。