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

2024-11-28 1
手机查看

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