コンパイラ/字句解析

トークンの規定

コンパイラ/正規言語を参照のこと。

実現

字句解析器の実現には二つの方法が考えられる。それは、

1. Lexなどのツールを使って実現する方法
2. 手書きで実現する方法

である。ここでは手書きで実現する方法を考えたい。

主なテクニック

先読み

字句を認識する際に先読みが必要になる時がある。一文字ならまだ良いが、複数文字を先読みしなければならない時もある。以下は先読みのアルゴリズムである。

characters = { }
function nextchar()
    if characters が空でない
        characters の底から一文字読み、それを c とおき、底の文字を消して次の文字を底とおく;
    else
        ファイルから一文字読み、それを c とおく;
    return c;

function lookforword()
    ファイルから一文字読み、それを c とおく;
    characters の一番上に c を積む;
    return c;

予約語

プログラムには予約語といって、コンパイラ、言語にとって他の識別子とは違い特別な意味を持ち、いかなる場合でも定義することはできない語がある。もし予約語がなければ、

while while == break if if break = else; else while = break;

といった構文が可能になってしまう。これはコンパイラにとっても人間にとっても不便であるのは想像がつくだろう。

予約語にまつわるはなし

PL/Iには予約語がなく、IF や CALL なども変数名に使うことが出来ます。 COBOLは500ほどの予約語があり、「PICTURE」と「PIC」のように正規形と短縮形のどちらもが予約語とされています。 また、「ZERO」と「ZEROS」「ZEROES」の様な格変化バリアントまで予約語になっています。 このため多くの単語が予約語と衝突するので、適用業務では 0TOTAL_PRICE の様に数字の 0 を前置する習慣があります（COBOLの識別子は、他の言語と異なり先頭に数字が来るのを許す）。

遷移図からの実現

遷移図とは、DFAまたはNFAを図に表したものであることは既に説明済みである。ここからはNFAからDFAができていると仮定して、話を進める。

最も単純で機械的な方法は、状態ごとにラベルを作り、読み込んだ文字に応じて遷移先の状態のラベルに goto する、という方法だろう。また、状態を state という変数に格納して、switch 構文内で状態を実現する方法である。各 case ラベル内で遷移先の状態を state に再代入すれば良い。

また、遷移図を意味的に解釈して通常のコードとして書くこともできるだろう。

サンプル

Keyword →
    if | else | for | while
Id →
    Letter (Letter | Digit)*
Num →
    Digit+
Operator →
    < | > | <= | >= | ==

これの遷移図を作ると、以下のようになる (ただしKeyWordは省略、予約語を後で認識するようにする)。

開始状態は0、二重丸は受理状態を示す。上図は受理状態からラベルが伸びているが、ここでは最長一致戦略を用いる。

以下にこの言語を受理するコードを示す。使用言語はC言語である。

int main() {
    
    return 0;
}

char nextChar() {
    /* 次の一文字をバッファから読み込んで返す関数 */
}

Token nextToken() {
}

struct Token {

};

問題

以下にC言語のトークン規定を正規表現で示す。なお、インラインは考えないものとする。

ただし、改行・空白は意味を持たなず、' | ' や ' || ' は正規表現の演算子としての意味ではなく、実際の入力という意味である。

Keywords →
    void | char | short | int | long | float | double | auto | static | const | signed | unsigned |
    extern | volatile | register |
    return | goto | if | else | switch | case | default | break | for | while | do | continue |
    typedef | struct | enum | union |
    sizeof

Letter →
    a | b | c | … | y | z | _
Digit →
    0 | 1 | 2  | … | 8 | 9

Identifier →
    Letter (Letter | Digit)*

Characters →
    " で囲まれる文字列
    ' で囲まれる文字列

DecimalNumber →
    (1 | 2 | 3 | … | 8 | 9) Digit*
OctalNumber →
    0 (1 | 2 | 3 | … | 6 | 7 )*
HexNumber → 
    0 x (Digit | A | B | C | D | E | F)+
RealNumber →
    DecimalNumber . Digit+
    OctalNumber . (1 | 2 | 3 | … | 6 | 7 )+
    HexNumber . (Digit | A | B | C | D | E | F)+
    DecimalNumber e (+ | -) Digits+
    OctalNumber e (+ | -) (1 | 2 | 3 | … | 6 | 7 )+
    HexNumber e (+ | -) (Digit | A | B | C | D | E | F)+
    
Number → DecimalNumber | OctalNumber | HexNumber | RealNumber

Symbols →
    + | - | * | / |%| ( | ) | ! | & | '||' | ? | , | .
    : | ; | ^ | { | } | [ | ] |
    < | > | = | <= | >= | != | == | && | '||' |
    += | -= | *= | /= | %= | ^= | ++ | -- | << | >> | ->

Token →
    Keywords | Identifier | Characters | Number | Symbols

以上に対して遷移図を作り、字句解析器を作りなさい。