编译原理（六）

心已赠人 2023-06-08 03:13 3阅读 0赞

### 编译原理（六） ###

*   *   *  自下而上的语法分析
         *   *  LR(0)分析
             *   *  构造NFA
                 *  直接使用闭包和状态转换函数
                 *  LR(0)项目集规范族的构造算法
                 *  LR(0)分析表的构造
             *  SLR分析方法
             *   *  SLR(1)分析表的构造算法
             *  LR(1)分析
             *   *  闭包Closure(I)
                 *  项目集规范族及识别活前缀的DFA
                 *  LR(1)分析表
             *  LALR(1)分析
             *   *  LALR分析表

### 自下而上的语法分析 ###

*  最左推导(Left-most Derive):每一步推导都替换当前句型的最左边的非终结符。  
    ——其逆过程称为最右归约
 *  最右推导(Right-most Derive):每一步推导都替换当前句型的最右边的非终结符。  
    ——其逆过程称为最左归约(规范归约)，得规范句型
 *  有文法G，开始符号为S, 如果有 S ⇒ ∗ x β y S\\overset\{\*\}\{\\Rightarrow\}xβy S⇒∗xβy,则xβy是文法G的句型，x,y是任意的符号串
    
     *  如果有 S ⇒ ∗ x A y , 且 有 A ⇒ + β , S\\overset\{\*\}\{\\Rightarrow\} xAy, 且有A\\overset\{+\}\{\\Rightarrow\}β, S⇒∗xAy,且有A⇒\+β,则β是句型xβy相对于非终结符A的短语
     *  如果有 S ⇒ ∗ x A y , 且 有 A → β , S\\overset\{\*\}\{\\Rightarrow\} xAy, 且有A\\rightarrow β, S⇒∗xAy,且有A→β,则β是句型xβy相对于 A → β A\\rightarrow β A→β的直接短语
 *  位于一个句型最左边的直接短语称为句柄.
 *  规范归约
    
     *  假定α是文法G的一个句子，如果序列：  α n , α n − 1 , … … , α 0 ( = S ) α\_n, α\_\{n-1\}, ……, α\_0 (=S) αn,αn−1,……,α0(=S)满足如下条件，则序列 α n , α n − 1 , … … , α 0 α\_n, α\_\{n-1\}, ……, α\_0 αn,αn−1,……,α0是一个规范归约:  
        (1)  α n = α α\_n =α αn=α 是给定的句子  
        (2)  α 0 = S α\_0 =S α0=S 是文法的开始符号  
        (3) 对任何i,  0 < i ≤ n ， α i − 1 0<i \\leq n，α\_\{i-1\} 0<i≤n，αi−1是从 α i α\_i αi经把句柄替换为相应文法产生式的左部符号而得到的。
     *  规范归约是最右推导的逆过程，又称为最左归约。
     *  最右推导又称规范推导，由规范推导所得到的句型称规范句型，规范推导的逆过程是规范归约。
 *  分析器的四种动作
    
     *  移进：将下一输入符号移入栈
     *  归约：当栈顶出现句柄，用产生式左侧的非终结符替换栈顶的句柄
     *  接受：分析成功，是归约的一种特殊情况
     *  出错：栈顶的内容与输入符号相悖，进行出错处理
 *  LR分析法：L——从左向右扫描输入串，R——构造最右推导的逆过程
 *  action\[Si,aj\]，指出如果当前栈顶为状态Si，输入符号为aj时应执行的动作。其动作有四种可能。
 *  goto\[Si,xj\]指出状态为Si，遇到Xj时应转到的下一状态
 *  分析表定义了一个以文法符号为字母表的DFA

#### LR(0)分析 ####

*  活前缀：规范句型的一个前缀，不含句柄之后的任何符号。在它之后增添一些终结符号后，就成为规范句型。即：  
    对于文法G，若  S ⇒ ∗ α β , β ∈ V T ∗ S\\overset\{\*\}\{\\Rightarrow\}\\alpha \\beta, \\beta \\in V\_T^\* S⇒∗αβ,β∈VT∗，称 α \\alpha α为活前缀。
 *  LR(0)项目：在文法G中每个产生式的右部适当位置添加一个圆点构成项目
 *  后继符号：在项目中紧跟在符号“·”后面的符号称为该项目的后继符号
    
     *  移进项目：后继符号为终结符：  A → α ⋅ a β A\\rightarrow α· aβ A→α⋅aβ
     *  待约项目：后继符号为非终结符： A → α ⋅ B β A\\rightarrow α· Bβ A→α⋅Bβ
     *  归约项目：后继符号为空：即圆点在最右边 A → α ⋅ A\\rightarrow α· A→α⋅
     *  接受项目：归约项目的左边是文法开始符号 S → α ⋅ S\\rightarrow α· S→α⋅
 *  后继符号集：项目集中各项目的后继符号所组成的集合称为后继符号集。项目集｛ E → E ⋅ ＋ T , F → ⋅ i E \\rightarrow E ·＋T,F\\rightarrow ·i E→E⋅＋T,F→⋅i｝的后继符号集为｛＋,i｝

##### 构造NFA #####

*  写出文法的所有项目，每个项目是一个状态
 *  规定项目1:  S ′ → ⋅ S S' \\rightarrow \\cdot S S′→⋅S为NFA的唯一初态
 *  若状态i和状态j出自同一产生式，而且状态j的圆点只落后于状态i一个位置:
    
     *  若i的圆点后是终结符a，从i到j画一条弧，标记为a
     *  若i的圆点后是非终结符A，则连两种弧：(1)从状态i画ε弧到所有的A→·β的状态。(2)从状态i到j画弧，标记为A
 *  归约项目表示结束状态，用双圈表示,双圈外加\*表示句子接受态acc

##### 直接使用闭包和状态转换函数 #####

*  一个项目集I的闭包Closure(I)的计算：  
    (1) I中的任何项目都 ∈ C l o s u r e ( I ) \\in Closure(I) ∈Closure(I)  
    (2) 若 A → α ⋅ B β 在 C l o s u r e ( I ) , 且 B ∈ V N A \\rightarrow \\alpha \\cdot B \\beta 在Closure(I),且 B \\in V\_N A→α⋅Bβ在Closure(I),且B∈VN，则对任何关于B的产生式：  B → ⋅ r ∈ C l o s u r e ( I ) B \\rightarrow \\cdot r \\in Closure(I) B→⋅r∈Closure(I)，r为任意符号串  
    (3) 重复(2)直到Closure(I)不再增加为止。  
    其中(2)的条件表示所有项目集中右边为·B的状态与B  → ⋅ \\rightarrow \\cdot →⋅ 的状态是等价的，因此，只要 B → ⋅ α B \\rightarrow \\cdot \\alpha B→⋅α进入Closure(I)中, 则所有B的圆点在左边的项目 B → ⋅ β B \\rightarrow \\cdot β B→⋅β都应进入同一个Closure(I)中。
 *  状态转换函数GO(I,X)的计算：  
    GO(I,X) = Closure(J) = Closure(move(I,X))  
    I是一个项目集，X是一个文法符号  
    其中J = \{任何形如 A → α X ⋅ β A \\rightarrow \\alpha X·\\beta A→αX⋅β的项目|  A → α ⋅ X β I A\\rightarrow \\alpha \\cdot X \\beta I A→α⋅XβI\}

##### LR(0)项目集规范族的构造算法 #####

*  拓广文法：在原文法G\[S\]上增加一个产生式 S ′ → S S' \\rightarrow S S′→S，这是为了得到唯一的接受状态 S ′ → S ⋅ S' \\rightarrow S · S′→S⋅
 *  设项目集规范族C只包含第一个状态\{S’→ · S\}的闭包，即C = \{ Closure(\{S’ → · S\}) \}
 *  利用GO函数对C中的每个项目集和每个符号X计算其下一状态，并将下一状态GO(I,X)加入到C中，直到C中状态数不再增加
    
     *  如果 G O ( I , X ) ≠ ∅ 且 G O ( I , X ) ∉ C 把 G O ( I , X ) 加 入 C 中 GO(I,X)\\neq \\varnothing 且GO(I,X)\\notin C 把GO(I,X)加入C中 GO(I,X)=∅且GO(I,X)∈/C把GO(I,X)加入C中
     *  在I和GO(I,X)之间添加标记为X的弧线

##### LR(0)分析表的构造 #####

设有文法G，则从LR(0)项目集规范族构造分析表的方法为：

*  对于 A → α ⋅ X β ∈ I k ， G O ( I k , X ) = I j A \\rightarrow \\alpha ·X\\beta \\in I\_k，GO (I\_k,X)=I\_j A→α⋅Xβ∈Ik，GO(Ik,X)=Ij
    
     *  若 X ∈ V T ， 则 置 a c t i o n \[ k , X \] = S j X \\in V\_T，则置action\[k,X\]=S\_j X∈VT，则置action\[k,X\]=Sj ,即把(j,a)移进栈
     *  若 X ∈ V N X \\in V\_N X∈VN，则置 g o t o \[ k , X \] = j goto\[k,X\]=j goto\[k,X\]=j
 *  对于 A → α ⋅ ∈ I k A\\rightarrow \\alpha · \\in I\_k A→α⋅∈Ik，则对所有的 x ∈ V T x\\in V\_T x∈VT和\# ，均置action\[k,x\]= r j r\_j rj (设 A → α A\\rightarrow \\alpha A→α是文法G’第j个产生式)，即用 A → α A\\rightarrow \\alpha A→α归约
 *  若 S ′ → S ⋅ ∈ I k S' \\rightarrow S · \\in I\_k S′→S⋅∈Ik，则置action\[k,\#\]=acc，即接受
 *  其他均置出错。

#### SLR分析方法 ####

*  若一个项目集中同时含有移进和归约项目，出现了冲突。
 *  解决冲突的条件：移进符号集合\{b\}, Follow(A), follow(B)两两不相交。
 *  解决的办法：当面临的输入符号为a：
    
     *  当a =b，则应移进；
     *  当a ∈follow(A)，则用产生式 A → β A\\rightarrow β A→β进行归约；
     *  当a ∈follow(B)，则用产生式 B → γ B\\rightarrow γ B→γ进行归约。

##### SLR(1)分析表的构造算法 #####

*  构造LR(0)的项目集规范族及识别活前缀的DFA
 *  判断冲突
 *  对每个冲突，计算规约项目左部符号的Follow集
 *  检查每个状态和每条边
    
     *   A → α ⋅ β ∈ I k 且 G O ( I k , X ) = I j 若 X ∈ V T ， 则 置 a c t i o n \[ k , X \] = S j , 即 把 ( j , a ) 移 进 栈 , 若 X ∈ V N ， 则 置 g o t o \[ k , X \] = j A\\rightarrow \\alpha \\cdot \\beta \\in I\_k 且GO(I\_k,X)=I\_j 若X \\in V\_T，则置action\[k,X\]=S\_j ,即把(j,a)移进栈,若X \\in V\_N，则置goto\[k,X\]=j A→α⋅β∈Ik且GO(Ik,X)=Ij若X∈VT，则置action\[k,X\]=Sj,即把(j,a)移进栈,若X∈VN，则置goto\[k,X\]=j
     *   对 于 A → α ⋅ ∈ I k ， 则 对 所 有 的 a ∈ V T ( 或 结 束 符 \# ) , a ∈ F o l l o w ( A ) ， 则 置 a c t i o n \[ k , a \] = r j ( 设 A → α 是 第 j 个 产 生 式 ) ， 即 用 A → α 归 约 对于A\\rightarrow \\alpha \\cdot \\in I\_k ，则对所有的a\\in V\_T(或结束符\\\#), a\\in Follow(A)，则置action\[k,a\]=r\_j (设A\\rightarrow \\alpha是第j个产生式)，即用A \\rightarrow \\alpha 归约 对于A→α⋅∈Ik，则对所有的a∈VT(或结束符\#),a∈Follow(A)，则置action\[k,a\]=rj(设A→α是第j个产生式)，即用A→α归约
     *  若 S ′ → S ⋅ ∈ I k S'\\rightarrow S · \\in I\_k S′→S⋅∈Ik，则置action\[k,\#\]=acc，即接受
     *  其他均置出错。

#### LR(1)分析 ####

LR(0)项目：为 \[ A → α ⋅ β , a 1 a 2 … a k \] ， A → α ⋅ β 是 一 个 L R ( 0 ) 项 目 ， a i ∈ V T ∗ \[A→α·β,a\_1a\_2…a\_k\]，A→α·β是一个LR(0)项目，a\_i∈V\_T^\* \[A→α⋅β,a1a2…ak\]，A→α⋅β是一个LR(0)项目，ai∈VT∗。

##### 闭包Closure(I) #####

*  闭包Closure(I)
    
     *  将I中的所有项目都加入Closure(I)。
     *  若项目\[A→α·Bβ,a\]∈Closure(I)，B→γ是一个产生式，那么对于任何b∈First(βa)，如果\[B→·γ,b\]原来不在Closure(I)中，则把它加进去。重复执行该过程，直到Closure(I)不再增大为止。
 *  I是一个项目集，X是一个文法符号，则转换函数GO(I,X)定义为：GO(I,X) = Closure(J)，J=｛任何形如\[A→αX·β,a\]的项目 | \[A→α·Xβ,a\]∈I｝。

##### 项目集规范族及识别活前缀的DFA #####

*  拓展文法，写出所有项目
 *  C=\{Closure (\{\[S’→ ·S,\#\]\})\};
 *  C中的每个项目集I和G’的每个符号X 求GO(I,X)
    
     *  如果 G O ( I , X ) ≠ ∅ 且 G O ( I , X ) ∉ C 把 G O ( I , X ) 加 入 C 中 GO(I,X)\\neq \\varnothing 且GO(I,X)\\notin C 把GO(I,X)加入C中 GO(I,X)=∅且GO(I,X)∈/C把GO(I,X)加入C中
     *  在I和GO(I,X)之间添加标记为X的弧线
 *  重复上一条步骤，直到C不再增大

##### LR(1)分析表 #####

*  若项目 \[ A → α ⋅ a β , b \] ∈ I k ， 且 G O ( I k , a ) = I j ， 其 中 a ∈ V T ， 则 置 a c t i o n \[ k , a \] = S j \[A→α·aβ,b\]∈I\_k，且GO(I\_k,a)=I\_j，其中a∈V\_T，则置action\[k,a\]=S\_j \[A→α⋅aβ,b\]∈Ik，且GO(Ik,a)=Ij，其中a∈VT，则置action\[k,a\]=Sj。即把输入符号a和状态j分别移入文法符号栈和状态栈。
 *  若项目 \[ A → α ⋅ , a \] ∈ I k ， 其 中 a ∈ V T ， 则 置 a c t i o n \[ k , a \] = r j \[A→α·,a\]∈I\_k，其中a∈V\_T，则置action\[k,a\]=r\_j \[A→α⋅,a\]∈Ik，其中a∈VT，则置action\[k,a\]=rj，即用产生式A→α进行归约，j是在文法中对产生式A→α的编号。
 *  若项目 \[ S ′ → S ⋅ , \# \] ∈ I k \[S'→S·,\\\#\]∈I\_k \[S′→S⋅,\#\]∈Ik，则置action\[k,\#\]＝acc，表示接受。
 *  若 G O ( I k , A ) ＝ I j ， 其 中 A ∈ V N ， 则 置 g o t o \[ k , A \] ＝ j GO(I\_k,A)＝I\_j，其中A∈V\_N，则置goto\[k,A\]＝j GO(Ik,A)＝Ij，其中A∈VN，则置goto\[k,A\]＝j。表示当栈顶符号为A时，从状态k转换到状态j。
 *  其他均置"报错标志"。

#### LALR(1)分析 ####

在LR(1)分析表中，若存在两个状态（项目集）除向前搜索符不同外，其它部分都是相同的，称这样的两个LR(1)项目集是同心的 。

##### LALR分析表 #####

*  构造LR(1)项目集规范族， C = I 0 ， I 1 ， … ， I n C=\{I\_0，I\_1，…，I\_n\} C=I0，I1，…，In。
 *  合并所有的同心集，得到LALR(1)的项目集族 C ′ = J 0 ， J 1 ， … ， J m C'=\{J\_0，J\_1，…，J\_m\} C′=J0，J1，…，Jm。含有项目\[S’→·S,\#\] 的Jk为初态。
 *  由C’构造动作(action)表。
    
     *  若 \[ A → α ⋅ a β , b \] ∈ J k ， 且 G O ( J k , a ) ＝ J j ， 其 中 a ∈ V T \[A→α·aβ,b\]∈J\_k，且GO(J\_k,a)＝J\_j，其中a∈V\_T \[A→α⋅aβ,b\]∈Jk，且GO(Jk,a)＝Jj，其中a∈VT，则置 a c t i o n \[ k , a \] = S j action\[k,a\]=S\_j action\[k,a\]=Sj，
     *  若项目 \[ A → α ⋅ , a \] ∈ J k \[A→α·,a\]∈J\_k \[A→α⋅,a\]∈Jk，其中 a ∈ V T a\\in V\_T a∈VT，则置action\[k,a\]=rj，rj的含义是按产生式A→α进行归约
     *  若项目 \[ S ′ → S ⋅ , \# \] ∈ I k \[S'→S·,\\\# \] \\in I\_k \[S′→S⋅,\#\]∈Ik，则置action\[k,\#\]=acc，表示分析成功，接受。
 *  goto表的构造。若不是同心集的项目集，转换函数的构造与LR(1)的相同；假定 I i 1 , I i 2 ， … ， I i n I\_\{i1\},I\_\{i2\}，…，I\_\{in\} Ii1,Ii2，…，Iin是同心集，合并后的新集为Jk，转换函数 G O ( I i 1 , X ) ， G O ( I i 2 , X ) ， … ， G O ( I i n , X ) GO(I\_\{i1\},X)，GO(I\_\{i2\},X)，…，GO(I\_\{in\},X) GO(Ii1,X)，GO(Ii2,X)，…，GO(Iin,X)也为同心集，将其合并后记作 J i J\_i Ji，因此，有 G O ( J k , X ) = J i GO(J\_k,X)= J\_i GO(Jk,X)=Ji，所以当X为非终结符时， G O ( J k , X ) = J i GO(J\_k,X)=J\_i GO(Jk,X)=Ji，则置goto\[k,X\]=i，表示在k状态下遇到非终结符X时，把X和i分别移到文法符号栈和状态栈。
 *  其他空白均填上“出错标志”。