Compiler-solution for First set, Follow set and LL(1) Parsing table

Solution for First Set

To compute FIRST(X) for all grammar symbols X, apply the following rules until no more terminals or ε can be added to any FIRST set.

  1. If X is a terminal, then .

  2. If X is a nonterminal and is a production for some , then place in if for some , is in , and is in all of . If is in for all , then add to . For example, everything in is surely in . If does not derive , then we add nothing more to , but if , then we add , and so on.

  3. If is a production, then add to .

Now, we can compute for any string as follows. Add to all non- symbols of . Also add the non- symbols of , if is in ; the non- symbols of , if is in and ; and so on. Finally, add to if, for all , is in .

Solution for Follow Set

To compute for all nonterminals , apply the following rules until nothing can be added to any set:

  1. Place $ in , where is the start symbol, and $ is the input right end marker.

  2. If there is a production , then everything in except is in .

  3. If there is a production , or a production , where contains , then everything in is in .

  1. 对于文法的开始符号,置 $ 于中；
  2. 若是一个产生式，则把加入到中
  3. 若是一个产生式，或是一个产生式且 ，则把加入到中

（可以是终结符或者非终结符(包括)，β可以是终结符或者非终结符)

Solution for LL(1) Parsing Table

Suppose the parsing table is , where is the number of nonterminals and is the number of terminals. The table is initialized to be empty.

The entry is a production rule that parser will apply when the current nonterminal is and the next input symbol is .

For each production in the (left factored, non-left recursive) grammar, do the following:

  1. Foe each token in , add the grammar production to .
  2. If is in then, for each token in the , add to .
  3. All other entries in the table are left blank and correspond to a syntax error.

流程：

遍历两次 Production Rule

第一次遍历，对每个 Production Rule 检查 Rule-1

  • 如果 是终结符，则把 加入到 中
  • 如果 是非终结符，则把 加入到

第二次遍历，对每个 Production Rule 检查 Rule-2

查看Production Rule 中所有可以产生 的非终结符
对这些非终结符把 加入到

Table Of Contents
Compiler-solution for First set, Follow set and LL(1) Parsing table
Solution for First Set
Solution for Follow Set
Solution for LL(1) Parsing Table