First集合とFollow集合
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2020/01/06 06:08 UTC 版)
「正規LR法」の記事における「First集合とFollow集合」の解説
先読みと比較される終端記号を決定するには、いわゆるFirst集合とFollow集合を用いる。First(A)とは、非終端記号Aに合致する規則のあらゆる連鎖の最初の要素となりうる終端記号の集合である。アイテムI [A → α • B β, x] のFollow(I)とは、非終端記号Bの直後となりうる終端記号の集合であり、ここで、α, βは任意の記号列、xは任意の先読み終端記号である。アイテム集合kおよび非終端記号BのFollow(k,B)とは、•にBが続くようなkに含まれるすべてのアイテムのFollow集合の和集合である。First集合は言語のすべての非終端記号の閉包から直接決定できるが、Follow集合はFirst集合を使用してアイテムから決定される。 今回の例では、下記のアイテム集合の完全なリストから確認できるように、First集合は以下のようになる。 First(S) = { n, '+', '(' } First(E) = { n, '+', '(' } First(T) = { n, '+' }
※この「First集合とFollow集合」の解説は、「正規LR法」の解説の一部です。
「First集合とFollow集合」を含む「正規LR法」の記事については、「正規LR法」の概要を参照ください。
- First集合とFollow集合のページへのリンク