I have worked with lex for executing some code whenever some regular expression is found, Can Yacc do something more than that? If yes, then what?
45078 次
5 に答える
35
はい、YACC はパーサーで、Lex は字句解析器です。これらは通常一緒に使用されます。文字列入力を Lex し、Lex によって提供されるトークン化された入力を YACC します。
現在、正規表現は正規言語のみを表すことができます。正規言語の制約の 1 つは、「メモリ」の不足です。以前に何が起こったかに基づいて、文字列のさらに下に受け入れのルールを定義することはできません。
これは、括弧の場合に最も明確に見られます。通常の言語は、ネストされた括弧を正しいレベルに一致させることができません。または他のそのような構造。(ほとんどの) コンピューター言語の文法は、できるし、できるし、そのため、Lexer や正規表現で構文解析することはできません。そこでYACCの出番です。
質問を逆にすることもできます。YACC にもっと多くのことができるのであれば、それを字句解析に使用してみませんか? まあ、たまたま、正規表現の有効性を非常に効率的に検証できることがありますが、これは一般的な文法の場合とは異なり、同じレベルではありません。それでも、YACC は、言語の字句規則が十分に単純であれば、基本的な字句解析を行うことができます。
于 2009-07-27T18:11:45.637 に答える
10
lexは入力をトークン化するためのものです。つまり、入力を、文法で定義されている最下位レベルのオブジェクトに分離します。たとえば、lexを使用して、キーワード、識別子、文字列、コメント、空白などを識別します。
yaccは文法を解析するためのものです。文法は言語の説明であり、通常はEBNFまたはその他の文脈自由文法で定義されます。文法をyaccに記述したら、それを使用して、言語の要素が認識されたときにツールのアクションを実行できます。これは、たとえば、式を解くための構文ツリーの構築、スコープオブジェクトの定義、変数定義の記録などです。
それらは無料の製品です。
于 2009-07-27T18:13:05.303 に答える
10
lex は字句解析器です。テキストをトークンに分割します。その威力は、正規表現マッチングとほぼ同等です。yacc はパーサー ジェネレーターです。一連のトークン (lex など) を受け取り、それらを一連のステートメントとして解釈します。その能力は、文脈自由文法とほぼ同等です。
lex と yacc の典型的な用途は、プログラミング言語の実装です。lex は入力をトークン化し、キーワード、定数、句読点などに分割します。次に、yacc が実際のコンピューター言語を実装します。たとえば、for ステートメントや関数定義を認識します。
実際には、lex を使用して入力テキストをチャンクに処理することがよくあります。次に、yacc を使用してこれらのチャンクをつなぎ合わせ、より大きな意味に処理します。
于 2009-07-27T18:12:10.050 に答える
3
通常、lex と yacc は一緒に使用されます。これは、通常、両方を使用してアプリケーションを構築する方法です。
入力ストリーム (文字) -> Lex (トークン) -> Yacc (抽象構文ツリー) -> アプリケーション
より一般的には、Lex が行うことは、最初からソース ファイルを読み取り、いくつかの正規表現との一致を試みることです (lex には、これに対する独自の特別な構文があり、perl や sed の正規表現とは少し異なります)。そして、認識したトークンごとに別のプログラムを呼び出します。トークンは、キーワードや演算子のように単純な列挙値の場合もあれば、リテラル値の場合のように何らかのメタデータが添付されている場合もあります。
Lex は通常 (必ずしもそうではありませんが)、Yacc を呼び出すために使用されます。Yacc は、大まかに言えば、各トークンをスタックにプッシュすることによって機能する LALR パーサー アルゴリズムを使用します。スタックに認識される一連のトークンがある場合、スタックはすべてのトークンをポップし、アクションを実行して、別のトークンをスタックにプッシュします。
Yacc が扱う対象の適切な語彙は、実際には端末と非端末です。端末は、呼び出しプログラム (通常は Lex) から取得したトークンであり、非端末は、スタック上のシーケンスと一致した結果です。
通常、各 Yacc ルールによって実行されるアクションは、ルールが対応する計算の結果を評価するか、別のアプリケーション層が処理する構文ツリーなどの中間表現を生成することです。
yacc は、lex と同様に、他とは別に使用できます。たとえば、ソース テキストから個々の文字を渡すことで Yacc を使用し、Yacc ルールを使用して各種類のトークンを認識することができます。ただし、Yacc はそのように簡単に使用できるようには設計されていないため、結果として得られるレクサーは、Lex の同等のレクサーよりもはるかに複雑になります。より一般的な使用法は、パフォーマンス上の理由から、またはよりスマートなレクサーが必要なために、手作業でコード化されたレクサーを作成することです。2 番目のケースの一般的な例は、型または変数を記述するために使用されているかどうかを知るために、識別子の以前の使用について知る必要がある C に似た言語で使用される場合です。
于 2009-07-27T18:24:41.490 に答える
1
Lex is a tool for building lexical analyzers, that can do some rather stupid lexical stuff (like finding keywords). Yacc is a parser generator, that can create parsers for real computer languages. Its analysis is normally based upon the output of lex (which is a stream of tokens) and from this can create your parse-tree of the programming language -- something that is more than lex does.
Traditionally, compiler builders distinguish between lexical and syntactical analysis -- which are two important steps in a compiler (further ones to follow eg. code creation, optimization).
于 2009-07-27T18:10:39.537 に答える