Compiler Ch4-Grammer

First and follow

是兩個很重要的Function，用來建構top-down 跟 bottom-up Parser

假設rule是以下這些
S -> ABc
A -> a | B
B -> b | λ

1.First(T)

定義：

將 T (可以是terminal 或 nonterminal) 展開時，可能遇到的第一個 terminal symbol 所成的集合
所以

First(A) = { a , b , λ }

First(B) = { b , λ }

2.Follow(T)

定義：

接在T( nonterminal ) 後所有可能的第一個terminal
在開始算Follow之前，先把$(input right end marker)放到Start symbol後
所以

Follow(B) = { c , $}

Follow(A) = First(B) + Follow(B) = { b , c }

在算Follow(A)時，即是在找接在A之後的第一個terminal有哪些，
而 S->ABc 因此去尋找B的First set，即是在找A後的第一個terminal，
會發現 First(B) 有 λ，因此當B->λ時，A後的第一個Terminal在Follow(B)內，以此類推。