6

私はこのバイソンの紹介を読んでいます。

私には2つの質問がありますが、誰かが私を理解するのを手伝ってくれるといいですね。

  1. 用語context free grammarはどういう意味ですか？

  2. 上記のリンクから：すべての文脈自由言語をBisonで処理できるわけではなく、LALR（1）である言語のみを処理できます。簡単に言うと、これは、先読みのトークンを1つだけ使用して、入力文字列の任意の部分を解析する方法を指示できる必要があることを意味します。「先読みのトークンを1つだけ使用して、入力文字列の任意の部分を解析する方法を指示できる」とはどういう意味ですか。

4

2 に答える 2

21

文脈自由文法は、正規表現よりも厳密に強力でありながら、マシンで簡単に処理できる文字列のセットの記述です。より正式には、文脈自由文法は4つのもので構成されます。

  • 生成される文字列の要素である終端記号のセット。バイソンパーサーの場合、これは通常、スキャナーによって生成されたトークンのセットです。英語のような自然言語の文法の場合、これはすべての英語の単語のセットである可能性があります。

  • 非終端記号のセット。直感的には、非終端記号は、「名詞」や「動詞」などの品詞のようなものを表します。

  • プロダクションのセット。各プロダクションは、非終端記号を他の終端記号と非終端記号のセットに置き換える方法を示しています。たとえば、プロダクションVariable -> Type Nameでは、非終端記号が表示された場合Variable、それを文字列に置き換えることができるとしていますType Name。

  • 派生が開始する非終端記号である開始記号。

例として、Cスタイルの関数宣言用のこの単純な文脈自由文法を考えてみましょう。

Function -> Type ident(Arguments)
Type -> int
Type -> Type *
Arguments -> e   (the empty string)
Arguments -> ArgList
ArgList -> Type ident
ArgList -> Type ident, ArgList

ここで、開始記号はFunctionです。この文法を前提として、非終端記号を繰り返し選択し、一致する生成の右側の1つに置き換えることで、Cスタイルの関数宣言を生成できます。各ステップで、これまでに作成した文字列はセンテンスフォームと呼ばれます。たとえば、上記の文法から導き出すことができるいくつかの異なる関数宣言を次に示します。

Sentential Form                       Production
-------------------------------------------------------------------
Function                              Function -> Type ident(Arguments)
Type ident(Arguments)                 Type -> int
int ident(Arguments)                  Arguments -> e
int ident()

Sentential Form                       Production
-------------------------------------------------------------------
Function                              Function -> Type ident(Arguments)
Type ident(Arguments)                 Type -> Type*
Type* ident(Arguments)                Type -> int
int* ident(Arguments)                 Arguments -> ArgList
int* ident(ArgList)                   ArgList -> Type ident, ArgList
int* ident(Type ident, ArgList)       ArgList -> Type ident
int* ident(Type ident, Type ident)    Type -> Type*
int* ident(Type* ident, Type ident)   Type -> Type*
int* ident(Type** ident, Type ident)  Type -> int
int* ident(int** ident, Type ident)   Type -> int
int* ident(int** ident, int ident)

ほとんどのプログラミング言語は、文脈自由文法で記述できる構造を持っています。パーサーの仕事は、プログラムと文法を取り、そのプログラムが文法によってどのように生成されるかを決定することです。

LALR（1）に関しては、残念ながらLALR（1）の正式な定義は簡単ではありません。コンパイラー構築コースの指導を終えたばかりで、LALR（1）について話すことができたのは、最初に関連する構文解析手法について2つの講義を行った後です。資料の正式な紹介が必要な場合は、ボトムアップ構文解析に関する私のスライドをコースのWebサイトで入手できます。

LALR（1）は、ボトムアップ構文解析アルゴリズムと呼ばれる構文解析アルゴリズムの一種です。これは、プログラムを開始記号に戻すために、文法の生成を逆の順序で適用しようとすることを意味します。たとえば、上記の文法によって生成されたこの文字列について考えてみましょう。

int** ident(int* ident)

ボトムアップ解析では、プログラムを一度に1トークンずつ調べて、この文字列を解析します。非終端記号に戻すことができるものを見つけたときはいつでも、そうします。（より正確には、LALR（1）は、アルゴリズムがより多くのコンテキストを持つように、他の基準も満たされている場合にのみこの種の削減を行いますが、この例では、これについて心配する必要はありません）。解析の各ステップは、シフトまたはリデュースのいずれかであると言われます。シフトとは、入力のもう1つのトークンを調べて、適用する削減に関する詳細情報を取得することを意味します。削減とは、いくつかのトークンと非終端記号を取得し、生成を逆にして非終端記号に戻すことを意味します。

文字列のボトムアップ解析のトレースは次のとおりです。

Workspace           Input                     Action
-----------------------------------------------------------------
             int** ident(int* ident)   Shift
int             ** ident(int* ident)   Reduce Type -> int
Type            ** ident(int* ident)   Shift
Type*            * ident(int* ident)   Reduce Type -> Type*
Type             * ident(int* ident)   Shift
Type*              ident(int* ident)   Reduce Type -> Type*
Type               ident(int* ident)   Shift
Type ident              (int* ident)   Shift
Type ident(              int* ident)   Shift
Type ident(int              * ident)   Reduce Type -> int
Type ident(Type             * ident)   Shift
Type ident(Type*              ident)   Reduce Type -> Type*
Type ident(Type               ident)   Shift
Type ident(Type ident              )   Reduce ArgList -> Type ident
Type ident(ArgList                 )   Reduce Arguments -> ArgList
Type ident(Arguments               )   Shift
Type ident(Arguments)                  Reduce Function -> Type ident(Arguments)
Function                               ACCEPT

バイソンを使用すると、シフト/削減の競合が不変に発生し、競合が削減/削減されるため、シフトと削減について知っておくことが重要です。これらのエラーは、パーサージェネレーターが、パーサーがシフトするか削減するか、または2つの削減のどちらを実行するかを判断できない状態になる可能性があると判断したことを意味します。これに対処する方法の詳細については、バイソンのマニュアルを参照してください。

文脈自由文法と構文解析アルゴリズム全般について詳しく知りたい場合は、 Grune and Jacobsによる「 ParsingTechniques：A Practical Guide、Second Edition」というタイトルの優れた本があります。これは、資料の最高の扱いを示しています。私が今まで見てきました。これは、より広く使用され始めているLALR（1）よりも大幅に強力な多くの手法（GLRやEarleyなど）を含む、あらゆる種類の解析アルゴリズムをカバーしています。私はこの本を強くお勧めします-それが私が構文解析をとてもよく理解している主な理由です！

お役に立てれば！

于 2011-08-24T17:12:53.903 に答える
1

1）簡単に言うと-コードのフォーマットとコンテキストは個々の部分にとって重要ではなく、意味を理解するためにコードがどのようにフォーマットされているかがわかりません。例として、Cプログラムを1行で書くことも、すべての単語を別の行に書くこともでき、プログラムは同じ意味になります。 ウィキペディアには、より正式な定義があります。

2）LALR（1）の意味はもっと複雑ですが、簡単に言えば、一度に1つの単語を読んで、次の単語/記号だけを見て意味を段階的に理解することとして、一部の話し言葉は有名ではないことで有名です。 LALR（1）であること-文の終わりに到達したときに、その文が質問またはステートメントであることを理解できない場合。一部のプログラミング言語もそのように構築できますが、実際的な理由から、すべてLALR（1）構文に準拠しているため、私は何も知りません。ただし、C / C ++がステートメントを正しく解析するために2つの記号を先読みする必要がある例外があると思います（したがって、LALR（2）ですが、頭のてっぺんからそれらが何であるかを思い出せないので、誰かがそれを指摘してくれることを願っていますコメントで。

いずれにせよ、ここにあるこの本は、コンパイラーとパーサーを理解することになると聖書です。

于 2011-08-24T17:10:09.677 に答える