1

わかりました。Follow_k（N）セットを計算する方法を理解しました（Nは非終端記号です）。A-> aBcの形式のすべての生成ルールについて、First_k（First_k（c）Follow_k（A））をFollow_k（B）に追加します。 ）（a、cは、終端記号と非終端記号の任意のグループ、またはラムダです）。...そして、追加するものがなくなるまでこれを繰り返します。

しかし、次のようなプロダクションルールはどうなりますか：S-> ABCD（A、B、C、Dはすべて非終端記号です）？

First_k
（First_k（BCD）Follow_k（S））をFollow_k（A）
に追加するか、First_k（First_k（CD）Follow_k（S））をFollow_k（B）
に追加するか、First_k（First_k（D）Follow_k（S））を追加する必要がありますFollow_k（C）
に追加するか、First_k（First_k（lambda）Follow_k（S））をFollow_k（D）に追加する
か、上記のすべてを実行しますか？

更新：
次の文法を例にとってみましょう。

S-> ABC
A-> a
B-> b
C-> c

直感的には、Follow_1（S）= {} Sの後に何も続かないため
Follow_1（A）= {b} bがAの後に続くため、
Follow_1（B）= {c} cがBの後に続くため、
Follow_1（C）= {} Cの後には何も続きません。
アルゴリズムを使用してこの結果を取得するには、S->ABCのすべてのケースを考慮する必要があります。

しかし、私の判断や例は正しくないかもしれないので、質問はまだ開いたままです...

4

1 に答える 1

2

このような他の文法の問題で問題が発生した場合は、最初にこれをオンラインで提供し、フォローして、セットファインダーを試してみてください。これは自動であり、その出力に対する回答を比較して、これらをどのように処理するかを感じることができます。

しかし、次のようなプロダクションルールはどうなりますか：S-> ABCD（A、B、C、Dはすべて非終端記号です）？

フォローセットを見つけるためのルールは次のとおりです。

  1. 最初に$（入力マーカーの終わり）をFollow（S）に入れます（Sは開始記号です）
  2. プロダクションA→aBb（aは文字列全体にすることができます）がある場合、εを除くFIRST（b）のすべてがFOLLOW（B）に配置されます。
  3. プロダクションA→aBがある場合、FOLLOW（A）のすべてがFOLLOW（B）になります
  4. FIRST（b）にεが含まれているプロダクションA→aBbがある場合、FOLLOW（A）のすべてがFOLLOW（B）になります。

例の文法を使用してみましょう。

  • S-> ABC
  • A-> a
  • B-> b

  • C-> c

    1. ルール1は、follow（S）に$が含まれていることを示しています。
    2. ルール2は次のようになります。follow（A）にはfirst（B）が含まれます。また、follow（B）にはfirst（C）が含まれています。
    3. ルール3は、follow（C）にはfollow（S）が含まれていると述べています。
    4. あなたの作品はどれもnull許容ではないので、ルール＃4は気にしません。シンボルがεを導出する場合、またはヌル可能な非終端記号を導出する場合、シンボルはヌル可能です。

Nullabilityの推移性は、人々をつまずかせる可能性があります。この文法を考えてみましょう。

  • S-> A
  • A-> B
  • B->ε

Bはεを導出するので、Bはnull許容です。Aはεを導出するBを導出するため、Aもnull許容です。SはAを導出し、Bはεを導出します。したがって、Sもnull許容です。

確かに、あなたはそれを提起しませんでしたが、それはコンパイラーコースでの一般的な混乱の原因であるため、私はそれをレイアウトすると思いました。

また、いくつかのサンプル文法が必要な場合は、http：//faculty.stedwards.edu/laurab/cosc4342/g1answers.txtが便利な場合があります。

于 2012-05-09T23:51:24.357 に答える