問題タブ [ll]

LL(1) 文法で FIRST と FOLLOW をどのように使用する必要があるかを誰かに説明してもらえますか? 構文テーブルの構築に使用されることは理解していますが、方法がわかりません。

今日は、文法の First と Follow を見つける方法を読んでいます。私はこの文法を見ました：

S→ACB | CbB | バ

あ→だ | 紀元前

B→g | ε

C → h | ε

主張は、

FIRST(S) = FIRST(ABC) U FIRST(CbB) U FIRST(Ba)

= {d, g, h, ε} U {h, b} U {g, a}

= {d、g、h、ε、b、a}

a と b がこのセットにどのように含まれているかわかりません。誰でもこれを説明できますか？

私は Pascal のサブセット用の語彙アナライザーの作成に取り組んでいます。これは、コンパイラーの赤いドラゴンの教科書の最後で推奨されているプログラミング プロジェクトです。解析テーブルを作成できるように、文法を LL に変更しています。私は他にぶら下がっているあいまいさを無視しており、それが存在する唯一のあいまいさであると信じています。すべてのイプシロン プロダクションを削除しました。左因数分解に進む前に、イプシロン プロダクションを正しく削除したかどうかについてのフィードバックが必要でした。私はかなり長い間これを見つめてきたので、後で問題を引き起こす何かを見落としていて、それをチェックする人がいないかどうかは本当にわかりません. 私はこれが長い投稿であることを知っています。これを知っている人にチェックしてもらうために他にどこに行くべきか本当にわかりません。お時間をいただき、誠にありがとうございます。

元の文法:

文法ポスト イプシロン生成の削除

もちろん、2 番目の文法は大きく異なります。それへの参照を見つけて|を作成することにより、すべてのイプシロンプロダクションを削除しました。それの有無にかかわらずオプション。イプシロンを削除すると、プロダクションに 1 行しか残らなかったため、そのプロダクションを完全に削除し、以前にプロダクションが呼び出された場所にラインを移動しました。たとえば、次のように変更して、この方法で完全に排除しました。

に

命題論理の次の文法を考慮します。

conectives の優先順位は、-、/\、/、->、<-> です。

結合性も考慮されます。たとえばp\/q\/r、 と同じにする必要がありますp\/(q\/r)。他のコネクティブも同様です。

Java で予測トップダウン パーサーを作成するふりをします。ここにはあいまいさや直接左再帰は見られませんが、これを LL(1) 文法と見なす必要があるかどうかはわかりません。たぶん、間接的な左再帰ですか？

これが LL(1) 文法ではない場合、私の意図のためにそれを変換するために必要な手順は何ですか?

私が理解している限り、FOLLOW-Set は、入力ストリームにエラーがあるかどうかを最初の可能な瞬間に教えてくれます。そうですか？

そうでなければ、実際に何のために必要なのか疑問に思っているからです。パーサーがスタックの上に非ターミナルを持っているとします (私たちのクラスでは、LL パーサーの抽象化としてスタックを使用しました)。

すなわち

X はスタックの一番上にあるため、次のステップで置き換えます。したがって、パーサーは解析テーブルに、X にどの派生を使用するかを尋ねます。入力が

+とはどちらbも端末です。

X""の FIRST セットに空の文字列があるとします。+そして、彼の FIRST セットには NOが含まれています。

この状況で私が見る限り、パーサーは X の FIRST セットにないことを単純にチェックし、パーサーができる唯一の方法であるため+、X を空の文字列に分解させる派生を使用できます。""エラーをスローすることなく、入力の解析を続行します。入力ストリームが無効な場合、パーサーはいずれにせよ後でそれを認識します。ここで FOLLOW セットが、エラーなしで解析を続行できるかどうかをすぐに特定するのに役立つことを理解しています。

私の質問は、FOLLOW セットが果たす唯一の役割ですか?

私の質問がここにあることを願っています - そうでない場合は申し訳ありません。また、ご不明な点がございましたら、お気軽にお問い合わせください。

前もって感謝します

で定義される文法 G が与えられると、

この文法は LL(1) ですか?

これを 1 行に圧縮できることは理解していますが、それはこの質問のポイントではありません。

主に、LL(1) 文法には、同じ非終端記号で始まる複数の規則を含めることができますか?

フォローアップの質問として、上記の文法の解析テーブルを作成するにはどうすればよいですか?

私は次のことを解決しました：

この投稿を見ましたが、FIRST と FOLLOW からテーブルに移行する方法がわかりませんでした。