First set and follow set in vernacular

FIRST Set

It can be understood as the starting symbol of the current non terminal character （ Terminator ） Set of

Solution ：

step ：

1. if X->a…, The Terminator ａ Join in FIRST(X) in ;

2. if X->e , The Terminator e Join in FIRST(X) in (e It means an empty set );

3. if X->BCD…E, Will First（B） All the elements （ Except for the empty set ） Join in First（X）, And then test First（B）, if First（B） There is no empty set in , namely e, Then stop , If it exists, it is directed to B View behind , take First（C） All elements in （ Except for the empty set ） Join in First（X）, And then test First（C） If there e… straight In the end , if E All previous nonterminal First The set contains e, ... is detected E when , take First（E） Also joined First（X）, if First（E） contains e, Will e Join in First（X）.

• The first two are easy to understand , The third explanation is ： A paragraph of grammar , If the preceding nonterminal symbol cannot deduce an empty set , Then the terminator generated by the following non terminator will never become the first character of grammar , Therefore, it is necessary to consider the case of empty sets .

give an example ：

Grammar, for example ：

• S→ABc
• A→a|ε
• B→b|ε

First Set method :
All opening symbols or possible symbols that can be derived from non terminating symbols ε, But the beginning symbol is required to be the ending symbol . Such a question A Can be derived a and ε, therefore FIRST（A）=｛a,ε｝; Empathy FIRST（B）={b,ε};S Can be derived aBc, You can also deduce bc, You can also deduce c, therefore FIRST(S）=｛a,b,c｝

FOLLOW Set

about Follow Set , We can understand it as the current candidate （ Right style ） The set of summary symbols that appear after the non terminator of .

Solution ：

step ：

1. Grammar start symbol S, Set up # On FOLLOW(S) in ;

2. For production ：A->aBC, Empty set will be removed e Of First（C） Join in Follow（B） in ;

3. For production ：A->aB perhaps A->aBC,( among C Empty strings can be derived ,C=>*e), Will Follow（A） Join in Follow（B） in .

• Follow（B） yes B The character set after the end of the string , stay A->aBC Under the situation of ,B Push the character set after the end of the string , That is to say C Push out the set of characters at the beginning of the string , namely First（C） Remove from e Set .
  A->aB , that A Push the character set after the end of the string , And B Push the character set after the end of the string , If it is equivalent, you can put Follow(A) Assign a value to Follow(B).

give an example ：

Grammar, for example ：

• S→ABc
• A→a|ε
• B→b|ε

Follow The solution of set ：
The closing symbol or... Immediately following it ＃. But grammar identifiers contain ＃, When asking, we should also consider ε. The specific method is to find out all the production formulas containing the symbols you require , See which works . Follow（S）=｛＃｝
As required A Of Follow Set Generative formula ：S→ABc A→a|ε , But only S→ABc Useful . Follow in A The ending symbol of the next year is FIRST（B）=｛b,ε｝, When FIRST（B） The element of is ε when , Follow in A The symbol after is c, therefore Follow（A）=｛b,c｝ Empathy Follow（B）=｛c｝

summary

First

for example ：A->aB | CD

This includes the composition First（A） In two cases ：

1. Start with Terminator , Of course, put this terminator in A Of First in

2. Start with a non Terminator , The first C Of First Put it in A Of First in , Look again if C Of First If you have time in your spare time D Of First Put it in A Of First in , If D If you're free, go back and so on

skill ：First Generally look from bottom to top . If you want to find A Of First, We are looking for A The definition of , namely A The formula on the left , Look at his right and look for .

Follow

Such as S->(L) | aL | LC

look for Follow Three situations of ： First in the candidate （ On the right ） The non terminator was found in , Such as L（ Note that there is only one definition in this example , But find Follow To see all non terminators on the right ）

1. If L To the right of is the Terminator , Then this terminator is added L Of Follow

3. If L To the right of is a non Terminator , So take this non Terminator First Remove the empty space L Of Follow in

3. If L At the end , that ,’->' The symbol on the left Follow Become L Of Follow

4. Another thing to note ： The beginning of the symbol Follow To add ‘#’

skill ：Follow Generally look from top to bottom . If you want to find L Of Follow, To find the right side of the equation L, Then come to L Of Follow, This is related to First Is different .

References used in this article 1
References used in this article 2

I would like to thank the above two predecessors .