0

私が理解している限り、いくつかの例外を除いて、ほとんどの言語は文脈自由です。たとえば、C++ では乗算または乗算をa * b表す場合があります。type * pointer_declarationどちらが行われるかは、コンテキスト、つまり最初の識別子の意味によって異なります。もう 1 つの例はname、VHDL でのプロダクションです。

enum_literal ::= char_literal | identifer
physical_literal ::= [num] unit_identifier
func_call ::= func_identifier [parenthized_args]
array_indexing ::= arr_name (index_expr)
name ::= func_call | physical_literal | enum_litral | array_indexing

構文形式が異なることがわかりますが、オプションのパラメーターが省略されている場合は一致する可能性がありますf。

Scala プラグインの設計者と話していて、依存関係が変わったときに AST を再評価するために AST をビルドするということを知りました。AST がある場合は、ファイルを再解析する必要はありません。AST ファイルの内容を表示する価値もあります。ただし、文法が文脈依存の場合、AST は無効になります (f別のファイルで定義された関数であり、後でユーザーが列挙型リテラルまたは未定義に再修飾したとします)。この場合、AST が変更されます。依存関係を変更するたびに、AST が変更されます。評価して作成方法を教えてほしいという別のオプションは、あいまいな AST を構築することです。

私の知る限り、パーサー コンビネーターはPEG のようなものです。最初に一致した生成を返すことであいまいさを隠し、f私の文法では最初の選択肢であるため、関数呼び出しに一致します。最初の成功に頼るのではなく、次の選択肢に進むコンビネータを求めています。最終的に、一致するすべての選択肢のリストが返されます。それは私にあいまいさを返すでしょう。

あいまいなファイル コンテンツ ツリーをユーザーに表示する方法はわかりませんが、依存ファイルを再解析する必要がなくなります。また、現代の言語設計がこの問題をどのように解決するかを知りたいです。

あいまいなノードが解析され、結果のあいまいさが返されたら、パーサーを収束させたいと思います。なぜなら、それを超えて解析を進めnameたいからであり、あいまいさのたびにファイルの最後まで解析したくないからです。f(10)単一の引数を指定した関数呼び出しや、後でインデックス付けされる配列を返す nullary 関数呼び出しのような状況によって、状況は複雑になります。そのため、f(10) は、func_call直接または再帰的にarr_indexing -> name ~ (expr). そのため、 のようにいくつかの並列ルールのように曖昧になることはありませんfcall | literal。一部のブランチは、再収束する前に 1 つのパーサーよりも長くなる場合がありますfcall ~ (expr) | fcall。

どのように解決していきますか？あいまいなコンビネータを PEG に追加することは可能ですか?

4

1 に答える 1

2

最初に、「ほとんどの言語はいくつかの例外を除いて文脈自由である」と主張しますが、これは完全に真実ではありません。コンピューター言語を設計するとき、CFG はそのための事実上の標準であるため、ほとんどの場合、可能な限り文脈に依存しないようにします。多くの作業が楽になります。ただし、これは常に実行可能なわけではなく、多くの[?]言語は意味解析フェーズに依存して、可能なあいまいさを解消しています。

通常、パーサー コンビネーターは正式なモデルを使用しません。一方、PEG は、CFG と同様に文法の形式主義です。過去 10 年間で、いくつかの人々が CFG ではなく PEG を使用することを決定しました。その理由は次の 2 つです。PEG は設計上、明確であり、常に線形時間で解析される可能性があります。パーサー・コンビネーター・ライブラリーは、基礎となる形式として PEG を使用する場合がありますが、CFG を使用するか、まったく使用しないこともあります。

PEG はコンピューター言語の設計に魅力的です。なぜなら、CFG を使用する際に避けるのが難しい (または不可能でさえある) あいまいさを処理したくないからです。そのため、動的プログラミング (いわゆる packrat パーサー) を使用して O(n) 回解析される可能性があります。いくつかの理由で「あいまいさを追加する」ことは簡単ではありません。最も重要なのは、認識される言語がオプションが決定論的であるという事実に依存するためです。これは、たとえば lookahead をチェックするときに使用されます。「最初の選択肢を選ぶだけ」という単純なものではありません。たとえば、次のように PEG を定義できます。

S = "a" S "a" / "aa"

N "a" のシーケンスのみを解析します。ここで、N は 2 の累乗です。したがって、2、4、8、16、32、64 などの文字「a」のシーケンスを認識します。CFG のようにあいまいさを追加すると、別の言語である偶数の「a」(2、4、6、8、10 など) を認識できます。

あなたの質問に答えるために、

どのように解決していきますか？あいまいなコンビネータを PEG に追加することは可能ですか?

まず、これはおそらく良い考えではないと言わなければなりません。AST をあいまいにしたい場合は、代わりに CFG パーサーを使用する必要があります。

たとえば、ブール文法のパーサーに似た PEG のパーサーを作成することもできますが、同じ言語を維持しながらすべての選択肢を維持することにより、漸近的な解析時間は O(n) から O(n 3 ) に増加します。 . 実際、私たちは PEG の両方の長所を一度に失います。

もう 1 つの方法は、packrat パーサーをメモリに保持し、そのテーブルを横断して AST からのセマンティクスを処理することです。これは大きなメモリフットプリントを意味するため、あまり良い考えではありません。

理想的には、文法構造を変更することによって、可能性のあるあいまいさに関する情報をすでに持っている AST を構築する必要があります。これには手作業が必要で、通常は簡単ではありませんが、文法をもう一度確認するためにフェーズに戻る必要はありません。

于 2016-09-10T01:31:29.220 に答える