编译原理（四）

一时失言乱红尘 2023-10-09 12:31 13阅读 0赞

### 编译原理（四） ###

*  语法分析

# 语法分析 #

1.  FIRST集合  
     F I R S T ( α ) = \{ a ∣ α ⇒ ∗ a … , a ∈ V T \} FIRST(α) = \\\{a| α \\overset\{\*\}\{\\Rightarrow\} a…,a\\in V\_T \\\} FIRST(α)=\{ a∣α⇒∗a…,a∈VT\}

> 求某一非终结符A的首终结符集First(A)的算法为：  
> 1.若有产生式 A → a α , a ∈ V T A \\rightarrow aα,a∈V\_T A→aα,a∈VT，把a加到First(A)中；  
> 2.若有产生式 A → ε A \\rightarrow ε A→ε, 把ε加到First(A)中；  
> 3.若有产生式 A → X α ， X ∈ V N A\\rightarrow Xα，X∈V\_N A→Xα，X∈VN，把First(X)中非ε元素加到First(A)中；  
> 4.若有产生式 A → X 1 X 2 X 3 . . . X k α A\\rightarrow X\_1X\_2X\_3...X\_kα A→X1X2X3...Xkα,其中 X 1 X 2 . . . X k ∈ V N X\_1X\_2...X\_k∈V\_N X1X2...Xk∈VN。则\{  
> 当 X 1 X 2 X 3 . . . X i ⇒ ∗ ε ( 1 ≤ i ≤ k ) 时 ， 把 F i r s t ( X i + 1 . . . X k ) 的 非 ε 元 素 加 到 F i r s t ( A ) 中 X\_1X\_2X\_3...X\_i\\overset\{\*\}\{\\Rightarrow\} ε(1≤i≤k)时，把First(X\_\{i+1\}...X\_k)的非ε元素加到 First(A)中 X1X2X3...Xi⇒∗ε(1≤i≤k)时，把First(Xi\+1...Xk)的非ε元素加到First(A)中；  
> 当 X 1 X 2 X 3 . . . X k ⇒ ∗ ε X\_1X\_2X\_3...X\_k\\overset\{\*\}\{\\Rightarrow\} ε X1X2X3...Xk⇒∗ε时，把First(α)加入First(A)中  
> 5.重复执行上述过程，直到First(A)不再增大

若 α ⇒ ∗ ε ， 则 ε ∈ F I R S T ( α ) 若α \\overset\{\*\}\{\\Rightarrow\} ε ，则ε \\in FIRST(α) 若α⇒∗ε，则ε∈FIRST(α)  
2. FOLLOW集合  
 F O L L O W ( A ) = \{ a ∣ S ⇒ ∗ … A a … ， a ∈ Ｖ T \} FOLLOW(A)=\\\{a|S \\overset\{\*\}\{\\Rightarrow\}…Aa…，a \\in Ｖ\_T \\\} FOLLOW(A)=\{ a∣S⇒∗…Aa…，a∈ＶT\}  
特别，若  S ⇒ ∗ … A ， 则 ， \# ∈ F O L L O W ( A ) S \\overset\{\*\}\{\\Rightarrow\} …A，则，\\\# ∈FOLLOW(A) S⇒∗…A，则，\#∈FOLLOW(A)  
其中’\#’ 为文本结束符号  
构造FOLLOW(U)的算法为：  
对文法的识别符号Z，令\#∊FOLLOW(U)；  
若文法中有形如A→αUβ的规则，则FIRST(β)中的非ε元素∊FOLLOW(U);  
若文法中有形如A→αU或A→αUβ而FIRST(β)中含有ε的规则，则FOLLOW(A)  ⊆ \\subseteq ⊆FOLLOW(U)

> 1.如果A是开始符号，＃∈Follow(A)  
> 2.若有产生式 B → α A a β , a ∈ V T B\\rightarrow αAaβ,a∈V\_T B→αAaβ,a∈VT，则  
> 把a加入到Follow(A)中；  
> 3.若有产生式 B → α A X β ， X ∈ V N B \\rightarrow αAXβ，X∈V\_N B→αAXβ，X∈VN，则  
> 把First(Xβ)中非ε元素加入Follow(A)中；  
> 4.若 B → α A 或 B → α A β ， β ⇒ ∗ ε B \\rightarrow αA 或 B\\rightarrow αAβ，β \\overset\{\*\}\{\\Rightarrow\} ε B→αA或B→αAβ，β⇒∗ε，则  
> 把Follow(B)加入到Follow(A)中；  
> 5.连续使用上述规则，直到Follow(A)不再增大。

1.  SELECT集合  
    给定上下文无关文法的规则 A → α （ A ∈ V N , α ∈ V ∗ ） A→α（A\\in V\_N, α\\in V^\*） A→α（A∈VN,α∈V∗）的SELECT集合为  
    若 α ⇏ ∗ ε α \\overset\{\*\}\{\\nRightarrow\} \\varepsilon α⇏∗ε，则SELECT(A→α)=FIRST(α)  
    若 α ⇒ ∗ ε α \\overset\{\*\}\{\\Rightarrow\} \\varepsilon α⇒∗ε，则SELECT(A→α)=(FIRST(α)-\{ε\})∪FOLLOW(A)  
    注意  
    小结：

> FIRST集合的计算是针对符号串的，ε可能在FIRST集合中；  
> FOLLOW集合的计算是针对非终结符号的，ε不可能在FOLLOW集合中；  
> SELECT集合的计算是针对文法规则的，ε不可能在SELECT集合中；  
> “\#”可能出现在FOLLOW和SELECT集合中

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTQ2NjUw_size_16_color_FFFFFF_t_70]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTQ2NjUw_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/2019092519274953.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTQ2NjUw,size_16,color_FFFFFF,t_70