2

コンパイラ コースの模擬試験がありますが、次の質問がありません。

  1. 文脈自由文法 (CFG) をスキャン/トークン化に使用できないのはなぜですか?
  2. 解析に決定論的有限オートマトン (DFA) を使用しないのはなぜですか?

誰にもアイデアはありますか？

4

1 に答える 1

9

これらのステートメントは両方とも正しくありません。

絶対にCFGを使用してスキャンとトークン化を行うことができます。実際、すべての正規言語も文脈自由であるため、正規表現の代わりに文脈自由文法を使用してスキャンするようにスキャナーを書き直すことができます。これを行わない主な理由は、通常はやり過ぎであるということです。トークンの構造が複雑になることはめったになく、正規表現は通常は問題なく機能します。ただし、CFGを使用する場合が考えられます。たとえば、C ++では、テンプレートでの近角中括弧の処理には、コンパイラによる特殊なケーシングが必要になることがよくあります。たとえば、正規表現の標準セットを使用すると、2つの閉じ中括弧がトークンとしてスキャンされますが、vector<vector<int>>としてトークン化する必要があります。文脈自由文法を使用してスキャンを行うと、より多くの文脈を持つことでこれを軽減できます。vector < vector < int > >>>

また、言語が十分に単純であれば、解析に正規表現を絶対に使用できます。ほとんどの言語は複雑すぎて正規表現でエンコードできないため（たとえば、ネストされた括弧を含むものは正規表現で解析できない）、代わりにCFGを使用する傾向がありますが、正規表現で解析できる言語もあります。たとえば、このようなテーブルとしてのDFAの記述は、正規表現によって確実に解析できます。

     0    1
 q0  q1   q0
 q1  q0   q1

ただし、ほとんどの実際のプログラミング言語には規則的な構造がないため、実際には、代わりに文脈自由文法が使用されます。

お役に立てれば！

于 2012-04-08T19:15:33.703 に答える