一般に、文脈自由文法が明確かどうかは判断できないことを私は知っています。ただし、これは、文脈自由文法のサブセットについてこれを決定できないことを意味するものではありません。

文法は、入力テキストを構文木に変換するために使用されます。与えられた入力に対して複数の構文木を生成できる場合、その文法はあいまいです。

LR パーサー アルゴリズムは、最初に文法を LR パーサー テーブルに変換します。その後、LR パーサー オートマトンを使用して、LR パーサー テーブルを使用して特定の入力ストリームを解析ツリーに処理します。通常、最初のステップはパーサー ジェネレーターによって実行され、2 番目のステップは解析操作ごとに実行されます。

LR パーサー テーブル構築アルゴリズムを考えてみましょうconstruct(G) = T | error。アルゴリズムは文脈自由文法を受け取りますG。テーブルの構築が成功すると、競合のない LR パーサー テーブルTが返されます。テーブルの構築に失敗した場合、エラーが返されます。このようなアルゴリズムの例は、SLR、LALR、および CLR です。アルゴリズムの失敗の典型的な例は、shift-reduce および reduce-reduce の競合です。

有限の入力ストリームと競合のない LR パーサー テーブルの場合、LR パーサー オートマトンは、指定された入力ストリームから 1 つの解析ツリーを決定論的に導出するか、入力ストリームが文法と一致しない場合にエラーを返すことができます。解析ステップは次のように形式化できますparse(T, I) = O | error。ここTで、 は競合のない LR 解析テーブル、Iはトークンの入力ストリームO、単一の解析ツリーです。入力ストリームが文法に一致しない場合、エラーが返されます。

質問

上記のステートメントを要約すると、競合のない LR パーサー テーブルに何らかの方法で変換できる文法は明確です。ただし、アルゴリズムがエラーを返した場合、これは文法があいまいであるかどうかについてのステートメントを意味するものではありません。したがって、LR テーブル構築アルゴリズムは、文脈自由文法のサブセットが明確であるかどうかを半決定します。これは正しいです？

私の結論が失敗する可能性のあるいくつかのステップを次に示します。

• LR テーブル構築アルゴリズムが終了しない可能性があります
• LR パーサー オートマトンが終了しない可能性があります
• LR テーブル構築アルゴリズムが正しくないため、LR パーサー オートマトンは、構築元の文法とまったく同じセットの入力ストリームを受け入れないか、文法とは別の解析ツリーを導出します。

私の知る限り、上記のどれも一般的な LR テーブル構築アルゴリズムには当てはまりません。

これについて明確な声明を見つけることができなかったので、説明と、この質問が議論され、明確に回答されている参考文献をいただければ幸いです。

私の結論が正しければ、LR パーサーはその言語で書かれたすべてのプログラムを適切に解析できるようにするため、この質問はプログラミング言語を設計する際に非常に重要だと思います。文法が明確であることを保証する他の方法はありますか?

次の 2 つの式を見てください。

baz、 、FooおよびBarが (baz型またはメソッドであるFoo可能性があり、型または変数である可能性がある)を知らなければ、 が型引数リストを表すのか小なり演算子を表すのBarかを明確にする方法はありません。<

適切なプログラミング言語は、このような式を解析するときに whatbazに依存するべきではFooありません。Barそれでも、Swift は、空白をどこに置いても、以下の式のあいまいさを解消することができます。

コンパイラはこれをどのように管理しますか? そして、さらに重要なことに、Swift 言語仕様には何か場所があります。このためのルールが記述されています。Language ReferenceSwift bookの一部を調べたところ、次のセクションしか見つかりませんでした。

特定の構文では、先頭に<or>が付いた演算子が 2 つ以上のトークンに分割される場合があります。残りは同じ方法で処理され、再度分割される場合があります。>その結果、 のような構造で終了文字間のあいまいさを解消するために空白を使用する必要はありませんDictionary<String, Array<Int>>。この例では、終了>文字は単一のトークンとして扱われず、ビット シフト>>演算子として誤って解釈される可能性があります。

この文脈でとは何certain constructsを指しますか? 実際の文法には、型引数に言及する生成規則が 1 つだけ含まれています。

明示的なメンバ式 → 後置式の.識別子ジェネリック引数句の_{オプション}

説明やリソースをいただければ幸いです。

Rascal で、プロダクションのオプション部分の位置にレイアウトがあると曖昧になるのはなぜですか? たとえば、"{ }"はあいまいですが、次の文法からのようStart1にうまく解析Start2されますが、まったく同じであると予想されます。

さらに、同じあいまいさを引き起こさない、Start2以外の重複なしで表す別の方法があるかどうかを知りたいです。Start1

明らかに、このコードには大量の重複はなくStart2、ここでは適切なオプションですが、これは単なる例です。私は、3 つまたは 4 つのオプション部分を含む多くのプロダクションを含む文法を扱っています。最後のケースでは、表示されている表記法でStart2すでにプロダクションのオプションではない部分を 2^4=16 回複製する必要があり、これは私の意見では本当に面倒です。 .

Verilog の仕様を読んでいると、パス パルスの指定に関する独特な構文構造に気付きました。具体的には、次の形式のステートメント

仕様によると、in_port識別子out_port(\エスケープされた識別子を含む) または括弧で囲まれた[]範囲の識別子のいずれかになります。

括弧を使用して構成をトークン化する際の問題を無視すると、通常の識別子の一部になるPATHPULSE可能性があるため、潜在的なあいまいさの問題が依然として存在するようです。$たとえば、モジュールが次のように宣言されている場合:

次に、パス パルス ステートメントを指定します。

$どちらが入力ポートと出力ポートを分離しているかを判断する方法はありません。

私の質問はこれです:PATHPULSEこのあいまいさを避けるために構造をトークン化するより良い方法はありますか? それとも、これは Verilog の不足ですか?

この演習には少し問題があります。

この文法を考えると：

a) 文字列とあいまいであることを示します

b) どの言語が文法を捉えているかを言う

c) 文法を変更し、子孫パーサーを構築する

私による解決策：

a) 文字列 ' ab 'のあいまいさを示します。

b) 文法はこの言語を捉えます:

c) 私の問題は、文法を変更してパーサーを構築することです。私はさまざまな文法を試しますが、それらもあいまいです。たとえば、次のようになります。

演習用の正しい文法を見つけるのを手伝ってくれますか、それとも入力してください。