問題タブ [context-free-grammar]

ゼロから設計したい新しいプログラミング言語 (命令型プログラミング言語) の文法 (コンテキストフリー) を定義する方法。

言い換えれば、新しいプログラミング言語をゼロから作成したい場合、どのように進めますか。

ランダムな「DearJohnLetter」を生成できるようにすることを目標に、Grammar ファイルを読み込む (データ構造に分割する) 必要があるプロジェクトに取り組んでいます。

私の問題は、.txt ファイルを読み取るときに、ファイルが完全に空白の行であると想定されているかどうかを確認する方法がわからないことです。これは、プログラムにとって有害で​​す。

ファイルの一部の例を次に示します。次の行が空白行であるかどうかを確認するにはどうすればよいですか? （ところで、私はバッファリングされたリーダーを使用しています）ありがとう！

私はANTLRにまったく慣れていないので、これはおそらく簡単な質問です。
数字と識別子（文字で始まり、1つ以上の文字または数字で続く文字列）を含む算術式を含むことになっている単純な文法を定義しました。

文法は次のようになります。

ANTLRIDEEclipseプラグインでANTLRv3を使用しています。インタープリターを使用して式を解析する(8 + a45)と、解析ツリーの一部のみが生成されます。

2番目の項（a45）が解析されないのはなぜですか？両方の用語が数字の場合も同じことが起こります。

Is there a way to specify custom class name (meaning independent of the grammar name) for the ANTLRv3 generated Parser and Lexer classes?

So in the case of

Automatically it would crate MDDParser and MDDLexer, but I would like to have them as MDDBaseParser and MDDLexer.

計算理論のコースのノートを見直しているのですが、特定の証明を完了する方法を理解するのに苦労しています。質問は次のとおりです。

これにはポンピング補題を使用する必要があることは明らかです。だから、私たちは持っています

1. |ヴィ| >= 1
2. |vxy| <= p (p はポンピング長、>= 1)
3. uv^ixy^iz はすべての i >= 0 に対して A に存在します

選択する正しい文字列を考えようとすると、これには少し不安が残ります。0^p 1^q 0^p と思っていたのですが、あいまいに aq ができるかどうかわからないし、u に縛りがないので、手に負えなくなるかもしれません..

では、これについてはどうすればよいでしょうか。

私はちょうど別の言語にいくつかの考えを入れていました（最終試験が近づいているので見直しています）、言語を処理するための有効なプッシュダウンオートマトンを考えることができません A = {0^n 1^n 0^n | n >= 0}。これは文脈自由言語ではありませんよね？

shift-reduce 解析について学習しようとしています。ANSI C Yacc grammarに触発された、操作の順序を強制する再帰規則を使用する次の文法があるとします。

そして、shift-reduce 解析を使用して 1+2 を解析したいと考えています。まず、1 が NUMBER としてシフトされます。私の質問は、P、次に M、次に A、最後に S に還元されるのかということです。どこで停止するかをどのように知るのですか？

それが S までずっと還元され、それから '+' をシフトするとします。これで、以下を含むスタックができました。

「2」をシフトすると、リダクションは次のようになります。

ここで、最後の行のどちらかの側で、S は P、M、A、または NUMBER である可能性があり、任意の組み合わせがテキストの正しい表現であるという意味で有効です。パーサーはどのようにしてそれを「知る」のですか

式全体を A、次に S に還元できるようにするには? 言い換えれば、次のトークンをシフトする前に削減を停止することをどのように知るのでしょうか? これは LR パーサー生成における重要な問題ですか?

編集：質問への追加は次のとおりです。

を解析するとします1+2*3。一部のシフト/リデュース操作は次のとおりです。

これは正しいですか (確かに、まだ完全には解析されていません)? さらに、1 シンボルによる先読みは、 を読み取った後に避けられない構文エラーが発生するため、に還元A+Mしないことも教えてくれますか?A*3

次の CFG を CNF の CFG に変換する必要があるという問題があります。

手順は次のとおりです。

1. イプシロン遷移を削除 - 完了
2. ユニットプロダクションを削除
3. 次の方法で CNF に変換します。
   1. 学期ごとに新しい非端末を導入する
   2. 生産ルールの端末を新しい非端末に置き換えます
   3. 各プロダクションの右側の長さを減らすために新しい非終端記号を導入する

上記の問題でそれを行う方法について少し混乱しています。ほとんどの場合、ステップ 2 とユニット プロダクションで混乱しています。

私は次の問題を抱えています：

言語L1={a ^ n * b ^ n：n>=0}およびL2={b ^ n * a ^ n：n> = 0}は文脈自由言語であるため、L1L2の下で閉じられ、L = {a ^ n * b ^ 2n A ^ n：n> = 0}は、クロージャプロパティによって生成されるため、コンテキストフリーである必要があります。

これが本当かどうかを証明しなければなりません。それで私はL言語をチェックしました、そしてそれが文脈自由であるとは思わない、そして私はまたL2がちょうどL1が逆になっているのを見ました。

L1、L2が決定論的であるかどうかを確認する必要がありますか？

ある言語を与えられた場合、それが規則的であるか、CF であるが規則的ではないか、句構造であるが CF ではないかをどのように判断しますか? この問題に対処する良い方法はありますか? ランダムに FA や PDA を作成することもできますが、もっと良い方法があると思います。

古典的な例:

L = { a^nb^nc^n | n >= 0}

どこから始めますか？ありがとう。