直接コード化対テーブル駆動型レクサー？

Question

私はコンパイラ構築の世界では新しく、直接コード化されたコードとテーブル駆動型のレクサー・アナライザの違いは何ですか？

可能であれば、簡単なソースコードの例を使用してください。

ありがとうございました。

編集：3つのタイプに

本Engineering a Compilerにおいて、著者は分割レクサー：テーブル駆動、直接符号化され、そして手が符号化されました。

Answer 1

"直接コード化"とは、レクサージェネレータの出力として生成されるものではなく、手書きのレクサーを意味します。その場合は... （下記を参照してください。）

... テーブル駆動レクサーは取るためにどのアクションを決定するためにルックアップテーブルのいくつかの種類を使用しています（通常は自動的に生成された）プログラムです。正規表現ab*aに対応finite automatonを考えてみましょう（意図的に最小化されていない）：

我々は唯一の文字「a」と「b」、我々は、ルックアップテーブルのように、それをエンコードすることができを考慮に自分自身を制限した場合そう：

int scan(void) { 
    char ch; 
    int state = 0; 

    while (!accept[state]) { 
     ch = getchar() - 'a'; /* Adjust so that a => 0, b => 1. */ 
     if (transitions[state][ch] == REJECT) { 
      fprintf(stderr, "invalid token!\n"); 
      return 0; /* Fail. */ 
     } else { 
      state = transitions[state][ch]; 
     } 
    } 
    return 1; /* Success! */ 
} 

：

#define REJECT -1 

/* This table encodes the transitions for a given state and character. */ 
const int transitions[][] = { 
    /* In state 0, if we see an a then go to state 1 (the 1). 
    * Otherwise, reject input. 
    */ 
    { /*a*/ 1, /*b*/ REJECT }, 
    { /*a*/ 2, /*b*/ 3  }, 
    { /*a*/ -1, /*b*/ -1  }, /* Could put anything here. */ 
    { /*a*/ 2, /*b*/ 3  } 
}; 

/* This table determines, for each state, whether it is an accepting state. */ 
const int accept[] = { 0, 0, 1, 0 }; 

は今、私たちは、実際にテーブルを使用するドライバが必要です

もちろん、実際のレクサーでは、すべてのトークンが対応する受け入れ状態を持つため、受け入れテーブルを変更してトークン識別子を格納する必要があります。しかし、私は2つのことを強調したい：

1. 表駆動型レクサーは、必ずしもDFA状態のレベルで動作するとは限りません。
2. テーブルドリブンレクサーを手作業で書くのは、面倒でエラーが起こりやすいプロセスですので、お勧めしません。

手書き（より良い名前の不足のため）をレクサーは、通常、ルックアップテーブルを使用しません。この1つは完全ではありません、テーブル駆動型レクサーの例のように

enum token { 
    ERROR, 
    LPAREN, 
    RPAREN, 
    IDENT, 
    NUMBER 
}; 

enum token scan(void) { 
    /* Consume all leading whitespace. */ 
    char ch = first_nonblank(); 
    if (ch == '(') return LPAREN; 
    else if (ch == ')') return RPAREN; 
    else if (isalpha(ch)) return ident(); 
    else if (isdigit(ch)) return number(); 
    else { 
     printf("invalid token!\n"); 
     return ERROR; 
    } 
} 

char first_nonblank(void) { 
    char ch; 
    do { 
     ch = getchar(); 
    } while (isspace(ch)); 
    return ch; 
} 

enum token ident(void) { 
    char ch; 
    do { 
     ch = getchar(); 
    } while (isalpha(ch)); 
    ungetc(ch, stdin); /* Put back the first non-alphabetic character. */ 
    return IDENT; 
} 

enum token number(void) { 
    char ch; 
    do { 
     ch = getchar(); 
    } while (isdigit(ch)); 
    ungetc(ch, stdin); /* Put back the first non-digit. */ 
    return NUMBER; 
} 

：我々は括弧、識別子と小数整数を持つシンプルなLispのような言語のレクサーをしたいとします。 1つは、IDENTとNUMBERのようなトークンの一部である文字を格納するには何らかのバッファリングが必要です。別の場合、EOFは特に上手く処理されません。しかし、うまくいけばそれの要点を得る。

---

編集：Engineering a Compilerでの定義に基づいて、直接符号化レクサーは、基本的に2つのハイブリッドです。表を使用するのではなく、コードラベルを使用して状態を表現します。以前と同じDFAを使用する方法を見てみましょう。私の個人的な経験で

int scan(void) { 
    char ch; 

state0: 
    ch = getchar(); 
    if (ch == 'a') goto state1; 
    else { error(); return 0; } 

state1: 
    ch = getchar(); 
    if (ch == 'a') goto state2; 
    else if (ch == 'b') goto state3; 
    else { error(); return 0; } 

state2: 
    return 1; /* Accept! */ 

state3: 
    ch = getchar(); 
    if (ch == 'a') goto state2; 
    else if (ch == 'b') goto state3; /* Loop. */ 
    else { error(); return 0; } 
} 

---

書き込みレクサーへの「最良の」アプローチは、私が上記で概説した手書きのアプローチです。これはすべてのプラットフォームで、あらゆる言語で動作し、lexのような古代のツールを学ぶ必要はなく、おそらく最も重要なのは、ツールで実装するのが難しい、または不可能な機能でレクサーを拡張する柔軟性があることです。たとえば、あなたのレクサーがPython-esqueブロックのインデントを理解したい、あるいは特定のトークンクラスを動的に拡張する必要があるかもしれません。