問題タブ [context-free-grammar]

これを前置きするために、この種のものについての私の知識は貧弱です.

とにかく、CYK 構文解析アルゴリズムがどのように機能するかを独学できるように、代数式の構造を記述する文脈自由文法を開発してきました。このような構造が中置代数式だけで機能する仕組みは理解していますが、「-」演算子の単項定義と 2 項定義の両方を処理できる文法を開発する方法がわかりません。

参考までに、私が CNF で書いた文法 (S は開始記号) を次に示します。

S -> x
A -> OS
S -> LB
B -> SR
S -> KS
O -> +
O -> -
O -> *
O -> /
O -> ^
K -> -
L -> (
R - > )

問題は、「-」演算子に遭遇したときに、CYK 解析アルゴリズムが S -> KS と A -> OS のどちらを決定するかをどのように事前に知ることができるかということです。そのような文法はもはや文脈自由ですか? そして最も重要なことは、プログラミング言語は 2 進数と単項の両方のマイナス記号を含む言語を処理できるため、これを合理的に解析するにはどうすればよいでしょうか?

Haskellで命題論理を表現するために次のデータ構造を使用しています。

この構造に関するコメントは大歓迎です。

ただし、ここで、アルゴリズムを拡張してFOL（述語論理）を処理したいと思います。HaskellでFOLを表現する良い方法は何でしょうか？

上記の拡張版であるバージョンと、より古典的な文脈自由文法に基づくバージョンを見てきました。これに関する文献はありますか、それは推奨される可能性がありますか？

私はANTRLを使用していますが、これは私の文法であり、エラーが発生します。

これはエラーです。「決定は、複数の選択肢を使用して「ELSE」などの入力と一致する可能性があります」。

どうすれば修正できますか？

質問には次のように記載されています。

言語 A = {a^ib^jc^k | を生成する文脈自由文法を与えてください。i=j or j=k where i,j,k >= 0} 文法があいまいですか? なぜですか、そうでないのですか？ 【はじめに。TOC Sipser 2.10 へ]

この本には、単に言語の記述から文脈自由文法を生成する方法について、あまり多くの良い例がありません。

プッシュダウン オートマトンを作成してから、そこから変換を試みる必要がありますか? または、このことに関する一般的なガイドラインはありますか？

I'm currently trying to implement a LALR parser generator as described in "compilers principles techniques and tools" (also called "dragon book").

A lot already works. The parser generator is currently able to generate the full goto-graph.

The goto-graph:

I have trubbles with implementing the algorithm to generate the actions-table! My algorithm computes the following output:

sx... shift to state x
rx... reduce to state x

The r? means that I don't know how to get the state (the ?) to which the parser should reduce. Does anyone know an algorithm to get ? using the goto-graph above?

If anything is describe no clearly enough, please ask and I will try to explain it better! Thanks for your help!

さて、私はフォローセットを理解しようとしていますが、1つのことを除いて理解できたと思います:

このページのルールに従い、FOLLOW(X) にはファイルの終わり文字である $ を含める必要があります (ルール 1)。次に、ルール 3 に従って、FOLLOW(X) には FOLLOW(X) のすべてが含まれており、私の脳は溶けてしまいます。

私にとって、直感的に、FOLLOW(X) は {a,b,$} のはずですが、この例をkfg Editで試してみると{$} しか得られません。なんで？

言語が文脈自由かどうかはどうすればわかりますか?

文脈自由文法で左再帰を削除することを理解しようとしています。私は特定のフォームに慣れていますが、これには少し戸惑います.

また、適切なパーサーを設計する必要がありますが、それは可能です。ただし、この左再帰 (特に最初の再帰) を理解すると、混乱します。

PL / SQLプログラミング言語の公式文法はどこにありますか？Antlrプロジェクトにはユーザー提供の文法があるようですが、もっと信頼できる情報源を見つけたいと思っていました。

定義による文法には、非常に単純な文法の例である生成が含まれます。

C# で Grammar クラスを実装したいのですが、ターミナル シンボルと非ターミナル シンボルを区別する方法など、プロダクションを格納する方法がわかりません。私は考えていました：

左側は常に非終端記号になります (これは文脈自由文法に関するものです)。ただし、プロダクションの右側には終端記号と非終端記号を含めることができます

だから今、私は実装の2つの方法について考えています:

1. 非終端記号は角かっこを使用して記述されます。次に例を示します。

   E+E は文字列 "[E]+[E]" として表されます

2. 追加のデータ構造 NonTerminal を作成します

   struct NonTerminal {文字列シンボル; }

E+E は配列/リストとして表されます。

しかし、もっと良いアイデアがあると思います。