mini-Pythonインタープリタ そにょ４

University Programming

いよいよ演習が始まる。結局一人で演習をすることになってしまった。とりあえず字句解析の入力部分のTips的なものを書いてみる。ネタバレになるので読みたくない人はすっ飛ばしてください。
mini-PythonはLL(1)文法になるように設計されているので、基本的に次の文字を見ればその字句がわかると言うようになっています（←これ構文解析の話。ごっちゃにしてた）。講義の仕様ではCで書かれているのでfgetcで一文字ずつ読むchar_streamが設計されています。これに倣うとC++を使う場合では

string m_fileName;
ifstream m_fileStream;
char m_currentChar;

m_fileStream.open(fileName.c_str());

m_currentChar = m_fileStream.get();

これで一文字読める。


さて、仕様のnext_token()ではこの関数が呼ばれたときに、解析する字句の最初の文字が読まれているようになっている。この関数の中ではこんな感じに、現在の文字を判別して字句を決定して、最後に一文字読んで処理を終了している。

next_token()
{
    //省略

    switch(currentChar)
    {
    case '\n':
        set_token(TOK_NEWLINE);
        next_char();
        break;
    // 省略
    }
    return;
}

ここで思うのは、next_char()をnext_token()の頭で呼べばいいんじゃないかということだ。

next_token()
{
    next_char();

    //省略

    switch(currentChar)
    {
    case '\n':
        set_token(TOK_NEWLINE);
        break;
    // 省略
    }
    return;
}

だが残念なことにそれではうまくいかない。例えば現在の文字が">"であった場合、以下の三通りの字句が考えられる。

">" => ">",">=",">>"

これを決定するにはnext_char()でさらに次の文字（"="か">"）を読む必要がある。その文字を見て字句が決定され、関数は処理を終了し、またnext_token()が呼ばれ、その頭でnext_char()が呼ばれる。これら3つの字句が共に2文字であれば全く問題はないのであるが、">"は1文字であるためその次の文字が読み捨てられてしまうのだ。つまりこの方法だと以下の例の5が読み捨てられてしまうのだ。

if(a>5){

そこで考えるのは、もし"="か">"でなければ1文字前に戻ると言うこと（次回のnext_token()呼び出し時に5が読まれるようにしておくこと）。これはできないことはないが非常に難しい。というかそもそもLL(1)文法なので後戻り処理はスマートではない。


名著『コンパイラの構成法と最適化』の字句解析の部分を読んでいると「まずはプログラムから１行読み出し……」と書いてあって気づいた。なにも一文字ずつ読む必要はないのだ。
なぜ一文字ずつ読んでいたのかというと、講義の仕様はC言語なのでgetline()を使用するときに、バッファサイズを決定しなくてはならない、つまり1行に読める長さを決めなくてはならないからである。十分に大きな数を設定しても構わないと思うが、それはプログラムの性能として良くはないだろう。
ここでC++でも同じではないかという人がいるかもしれない。確かにcinを用いても

char line[1024];
cin.getline(line,sizeof(line));

となり、バッファサイズの制限が課せられる。しかし標準文字列（std::string）のgetlineを使うと

string line;
getline(cin,line);

これで可変長の文字列をcinから読み込むことができる。
で、なぜ1行読めばいいかというと、char[]もstd::stringもインデックスでアクセスできるので、先読みが非常に簡単にできるということである。先の">"の例で言えば、これがi文字目だった場合line[i+1]でその次の文字を参照でき、その文字が"="か">"でなかった場合でも、後戻りずる必要がないのだ。"="か">"であった場合はその字句を処理した後iをインクリメントすればよい。


"getline"で検索をかけてもcin.getline()がヒットしやすいので知らない人も結構いるようだ。
ちなみにこのgetline(cin,line)、1億文字ある行を持つファイル(1行で100MBぐらい)を読んでも大丈夫でした（←これがやりたかった）。
原理的にはこれで大丈夫だと思うが、念のため問題点がないか調査中。

getline テンプレート関数で、区切り記号が発生した後、余分な文字を読み取ります。
http://support.microsoft.com/kb/240015/ja

うちはVS2005だから大丈夫だと思うが。


ていうかpeek()使えよ、って話。