パーサーがどのように機能するかを理解したいと思います。LL、LR(0)、LR(1)の部分、構築方法、NFA、DFA、パーステーブルなどについて学びました。
問題は、ある状況でパーサーの要求に応じてレクサーがトークンを抽出する必要があることです。1 つの個別のパスですべてのトークンを抽出することはできません。私はこの種の状況を正確に理解していないので、これについての説明を受け付けています。
問題は、レクサーがどのように仕事をするべきかということです。現在の「コンテキスト」、つまり解析されるはずの現在の非端末に基づいて認識すべきですか？それはまったく違うものですか？GLR 構文解析についてはどうですか?レクサーがさまざまな端末を試すことができる別のケースですか、それとも構文上の問題にすぎませんか? また、それが何に関連しているのかを理解したいと思います.
どうもありがとう
簡単な答えは、語彙素の抽出はコンテキスト内で実行する必要があるということです。言語の語彙素と見なされるものは、言語のさまざまな部分でかなり異なる場合があります。たとえば、COBOLでは、データ宣言セクションに「PIC」文字列と場所に依存するレベル番号01〜99があり、これらはプロシージャセクションには表示されません。
したがって、レクサーは、言語のどの部分が処理されているかを何らかの形で知り、収集する語彙素を知ることができます。これは多くの場合、語彙素の言語セット全体のサブセットを処理する字句解析状態を持つことによって処理されます（サブセット内でかなりの重複があることがよくあります。たとえば、識別子は私の経験ではかなり似ている傾向があります）。これらの状態は、高レベルの有限状態マシンを形成し、相変化語彙素が検出されたときにそれらの間で遷移します。たとえば、COBOLプログラムのデータ宣言またはプロシージャセクションへのエントリを示すキーワードです。JavaやC＃のような現代言語はこれの必要性を最小限に抑えますが、私が遭遇した他のほとんどの言語は本当にレクサーでこの種の助けを必要としています。
いわゆる「スキャナーレス」パーサー（「GLR」と考えている）は、レクサーを完全に取り除くことで機能します。これで、レクサーが語彙素を生成する必要がなくなり、字句状態を追跡する必要もなくなります。：-}このようなパーサーは、個々の文字のレベルに文法を書き込むだけで機能します。通常、語彙素の説明に書くものとまったく同じ文法規則があります。問題は、なぜそのようなパーサーがどの「語彙素」を生成するかについて混乱しないのかということです。ここでGLR部分が役立ちます。GLRパーサーは、選択が最終的に解決される限り、入力の多くの可能な解釈（「ローカルにあいまいな解析」）を喜んで処理します。したがって、「あいまいなトークン」の場合に実際に発生するのは、両方の「トークン」の文法規則です。
私の会社は言語用のパーサーをたくさん作っています。複雑な言語を処理するのに非常に優れているため、GLRパーサーを使用します。文脈自由文法を書くと、パーサーができます。語彙素ベースの語彙素エクストラクタを使用し、通常の語彙素の正規表現仕様と、特定の語彙素によってトリガーされる語彙素状態遷移を使用します。間違いなくスキャナーレスGLRパーサーを構築することはできますが（レクサーにトークンとして単一の文字を生成させることにより:)、状態ベースのレクサーの効率は余分な手間をかける価値があることがわかります。
実用的な拡張機能として、私たちのレクサーは実際には、単なる有限状態マシンではなく、高レベルの状態マシンにプッシュダウンスタックオートマトンを使用します。これは、サブステートが同一である高レベルのFSAがある場合、およびレクサーがネストされた構造を管理する場合（たとえば、括弧を一致させる場合）、モードスイッチを管理する場合（たとえば、括弧がすべて一致する場合）に役立ちます。
レクサーのユニークな機能：スキャナーレスパーサーが行うことのほんの少しも行います：キーワードが認識されると、レクサーはキーワードと識別子の両方をパーサーに挿入します（スキャナーレスパーサーを文法規則でシミュレートします各）。もちろん、パーサーは「コンテキスト内」で必要なものだけを受け入れ、間違った選択肢を単に破棄します。これにより、多くの言語で発生する「識別子として解釈されるコンテキスト内のキーワード」を簡単に処理できます。
理想的には、トークン自体が明確であるべきです。パーサーが追加の作業を行うことなく、常に入力ストリームをトークン化できる必要があります。
これは必ずしも単純ではないため、次のようなツールが役立ちます。
レクサー アクションは、スキャナーの開始条件を変更できます。つまり、さまざまなルール セットをアクティブ化できます。
この典型的な例は、文字列リテラルの字句解析です。文字列リテラルを解析する場合、通常、トークン化の規則はそれらを含む言語とは完全に異なります。これは、排他的開始条件の例です。
あいまいな字句解析は、それらの 2 つの別個の開始条件を識別でき、事前のコンテキストが与えられたときにレクサーが適切に入力できるようにすれば、それらを分離できます。
これは、レクサーで状態を保持し、パーサーでそれを変更するための派手な名前です。パーサーの特定のアクションが実行されると、レクサーの状態が変更され、その結果、レクサー アクションが異なるトークンを返します。これは、レクサーとパーサーの両方を推論するのがより難しくなり、いくつかのこと (GLR パーサーなど) が不可能になるため、必要な場合は避ける必要があります。
利点は、コードへの比較的小さな影響で、大幅な文法の変更を必要とすることを実行できることです。解析からの情報を使用してレクサーの動作に影響を与えることができます。これにより、「あいまいな」文法と見なされる問題を解決することができます。
論理、推理
1回の解析でそれを字句解析することが可能である可能性が高く、上記のツールは、入力をどのようにトークン化し、それを字句解析の言語に変換しようとするかについて考えることに次ぐべきです。:)
実際のところ、あなたの入力は、好むと好まざるとにかかわらずトークンで構成されており、必要なことは、既に知っているルールをプログラムに理解させる方法を見つけることだけです。