2

私の理解が正しければ、構文解析によって一連のシンボルがツリーに変換されます。私の質問は、標準的な手順 (LR、LL、PEG、..?) を使用して次の 2 つの例を解析することは可能ですか、それとも特殊なパーサーを手動で作成する必要がありますか?

  1. Python ソース コード、つまり空白でインデントされたブロック

パーサーが先頭のスペースの数を追跡し、それらを中括弧に置き換えてブロックを区切るふりをどこかで読んだと思います。標準の解析手法が十分に強力ではないため、それが基本的に必要なのか、それともパフォーマンス上の理由からですか?

  1. PNG 画像形式。ブロックはヘッダーとブロック サイズで始まり、その後にブロックのコンテンツが続きます。

コンテンツにはヘッダーに似たバイトが含まれる可能性があるため、次の x バイトが「解析」されないこと、つまりスキップされることを「認識する」必要があります。これを PEG で表現するにはどうすればよいでしょうか。つまり、「閉じ括弧」はコンテンツの長さで表されます。

4

2 に答える 2

0

実際問題として、ほとんどすべてのパーサーの構築には、構文解析機構の制限を克服するためにエッジの周りにいくつかの巧妙なハックが必要です。

純粋な文脈自由パーサーは Python を実行できません。あなたがリストしたすべてのパーサー技術は、純粋なコンテキストフリーよりも弱いため、それもできません。インデントを追跡し、INDENT/DEDENT トークンを生成するレクサーのハックは、インデントの問題を明示的な「括弧」に変えます。これは、コンテキストフリーのパーサーによって簡単に処理されます。

通常、どこかに長さ N のリストが含まれているため、ほとんどのバイナリ ファイルも処理できません。N は、リスト本体が検出される前に提供されます (これは、指定した例のようなものです)。繰り返しますが、これはより複雑なハックで回避できます。ネストされたリストの長さのスタックを保持する必要があり、パーサーは、あるリスト要素から次のリスト要素に移動するときに通知する必要があります。最上位の長さカウンターがデクリメントされ、パーサーはシグナル「reduce」または「shift」を返します。他のより複雑なリンク構造は、通常、この方法で解析するのはかなり困難です。このようにパーサーを連携させることは、必ずしも容易ではありません。

于 2014-09-18T17:05:58.780 に答える
0

質問の例はどちらも文脈自由ではないため、厳密に言えば、文脈自由文法で解析することはできません。しかし実際には、どちらも非常に簡単に解析できます。

Python アルゴリズムについては、Pythonリファレンス マニュアルで詳しく説明されています(ただし、文脈を理解して読む必要があります)。そこで説明されているのは、行頭の空白を体系的にトークンに置き換える前処理ステップINDENTですDEDENT。

明確にするために：これは実際には前処理ステップではなく、暗黙的および明示的な行結合の後に発生することを観察することが重要です。(リファレンス マニュアルには、これらの手順を説明する前のセクションがあります。) 特に、行は括弧、中括弧、および大括弧内で暗黙的に結合されるため、プロセスは解析と絡み合っています。

実際には、行結合アルゴリズムとインデント アルゴリズムの両方をプログラムで実行できます。通常、これらは、括弧のスタックとインデント レベルの両方を維持するカスタム スキャナー (トークナイザー) 内で行われます。その後、トークン ストリームは通常のコンテキスト フリー アルゴリズムで解析できますが、トークナイザーは(正規表現を使用する場合もありますが) コンテキスト依存のロジック (スペースのカウントなど) を必要とします。【注1】

同様に、明示的なサイズを含む形式 (PNG ファイル、Google protobuf、および HTTP チャンク エンコーディングを含むほとんどのシリアル化形式など) はコンテキストフリーではありませんが、トークナイザーは単に長さを読み取ってから読み取る必要があるため、明らかに簡単にトークン化できます。その多くのバイト。

さまざまな文脈依存の形式主義があり、これらには間違いなく用途がありますが、実際の解析では、最も一般的な戦略は、チューリングと同等の形式主義 (プログラミング言語などflex)を使用することです。トークナイザーとパーサーの文脈自由形式。【注2】

ノート：

  1. Python のインデントが文脈自由でないことはすぐにはわからないかもしれません。文脈自由文法はいくつかのカテゴリーの一致を受け入れることができるからです。たとえば、(すべての偶数回文の言語) は のように文脈自由です。{ωω-1 | ω∈Σ*}{anbn}

    ただし、これらの例を拡張することはできません。これは、文脈に依存しない言語で可能な唯一のカウントの合意がブラケットであるためです。したがって、回文はコンテキストフリーですが (単一のスタックでチェックを実装できます)、明らかに非常に似ているものはそうではなく、どちらもそうではありません。{ωω | ω∈Σ*}{anbncn}

  2. そのような形式主義の 1 つは、「正規」表現での後方参照です。これは、一部の PEG 実装で使用できる可能性があります。後方参照は、さまざまな文脈依存言語の表現を許可しますが、すべての文脈自由言語の表現を許可するわけではありません。残念ながら、文字列が後方参照のある正規表現と一致するかどうかを判断する問題は NP 完全であるため、後方参照のある正規表現は実際にはうまくいきません。この質問は、姉妹 SE サイトで興味深いものになるかもしれません。(また、そのサイトhttp://cs.stackexchange.comで質問できるように質問を再構成することもできます。)

于 2014-09-18T17:07:12.187 に答える