7

与えられた次の文法 

S -> L=L  
s -> L  
L -> *L  
L -> id

非終端記号の最初と次は何ですか？

文法がに変更された場合

S -> L=R  
S -> R  
L -> *R  
L -> id  
R -> L

最初とそれに続くものは何ですか？

4

1 に答える 1

23

大学でコンパイラコースを受講したとき、FIRSTとFOLLOWSをまったく理解していませんでした。Dragonの本で説明されているアルゴリズムを実装しましたが、何が起こっているのかわかりませんでした。私は今やると思います。

これらの2つのセットを正式に定義した本があり、その本は完全に理解できないと思います。私はそれらの非公式な説明をしようとします、そしてうまくいけばそれはあなたがあなたの本に何があるかを理解するのを助けるでしょう。

最初のセットは、非終端記号の拡張の最初の部分として表示される可能性のある終端記号のセットです。FOLLOWSセットは、非終端記号の拡張後に表示される可能性のある終端記号のセットです。

=最初の文法では、端末は、、、*およびの3種類しかありませんid。（$入力の終わりの記号である、を終端記号と見なすこともできます。）非終端記号はS（ステートメント）とL（Lvalue-割り当てることができる「もの」）だけです。

FIRST（S）は、ステートメントを開始する可能性のある非終端記号のセットと考えてください。直感的には、ステートメントを。で始めないことがわかります=。したがって、FIRST（S）に表示されるとは思わないでしょう。

では、ステートメントはどのように始まりますか？外観を定義する2つのプロダクションルールがありS、どちらも。で始まりLます。したがって、FIRST（S）に何が含まれているのかを理解するには、FIRST（L）に何が含まれているのかを実際に確認する必要があります。Lvalueがどのように見えるかを定義する2つのプロダクションルールがあります。それは、*またはで始まりidます。したがって、FIRST（S）= FIRST（L）= { *、id}。

FOLLOWS（S）は簡単です。S開始記号であるため、何も続きません。したがって、FOLLOWS（S）で唯一のものは$、入力の終わりの記号です。

FOLLOWS（L）は少し注意が必要です。表示されるすべてのプロダクションルールLを確認し、その後に何が表示されるかを確認する必要があります。最初のルールでは、それが続く可能性があることがわかり=ますL。=FOLLOWS（L）もそうです。Lしかし、そのルールには、プロダクションルールの最後に別のルールがあることにも気づきます。したがって、フォローできるもう1つのことLは、そのプロダクションに続く可能性のあるものです。Sプロダクションに続くことができるのは入力の終わりだけであることはすでに理解しています。したがって、FOLLOWS（L）= { =、$}。（他のプロダクションルールを見ると、L常にそれらの最後に表示されるので、それら$から取得するだけです。）

この簡単な説明ϵを見てください。空の文字列を含むプロダクションがないため、今のところはすべて無視してください。「最初のセットのルール」では、ルール＃1、＃3、および＃4.1が理にかなっているはずです。「フォローセットのルール」では、ルール＃1、＃2、および＃3が意味をなすはずです。

ϵプロダクションルールがあると、事態はさらに複雑になります。次のようなものがあるとします。

D -> S C T id = V  // Declaration is [Static] [Const] Type id = Value
S -> static | ϵ    // The 'static' keyword is optional
C -> const | ϵ     // The 'const' keyword is optional
T -> int | float   // The Type is mandatory and is either 'int' or 'float'
V -> ...           // The Value gets complicated, not important here.

ここで、FIRST（D）を計算する場合、Sは「空」である可能性があるため、FIRST（S）だけを調べることはできません。staticFIRST（D）が{ 、、、 }constでintあることを直感的に知っていfloatます。その直感はルール＃4.2で成文化されています。SCTこの例でY1Y2Y3は、「簡単な説明」のルールと考えてください。

FOLLOWS（S）を計算する場合は、FIRST（C）を確認することはできません。これは、空である可能性があるため、FIRST（T）も確認する必要があります。したがって、FOLLOWS（S）= {、、const} 。これは、「フォローセットのルール」＃2および＃4（多かれ少なかれ）を適用することで得られます。intfloat

それがお役に立てば幸いです。また、2番目の文法のFIRSTとFOLLOWSを自分で理解できることを願っています。

役立つ場合Rは、Rvalue（定数やリテラルなど、割り当てることができない「もの」）を表します。左辺値は右辺値としても機能します（ただし、その逆はできません）。

a = 2;  // a is an lvalue, 2 is an rvalue
a = b;  // a is an lvalue, b is an lvalue, but in this context it's an rvalue
2 = a;  // invalid because 2 cannot be an lvalue
2 = 3;  // invalid, same reason.
*4 = b; // Valid!  You would almost never write code like this, but it is
        // grammatically correct: dereferencing an Rvalue gives you an Lvalue.
于 2010-02-18T07:52:53.387 に答える