编译原理重点

Chapter4 语法分析

自顶向下语法分析

First 集
First 集即一个文法符号串可能推导出的串的第一个终结符的集合（包括空字符$\epsilon$）
1. 单个终结符的 First 集
  
  单个终结符的 First 集就是它自己。
  First(X)={X}
2. 单个非终结符的 First 集
  1. $A\rightarrow a…$
    
    产生式右部以终结符开头，$a\in First(A)$
  2. $A\rightarrow B…$
    
    产生式右部以非终结符开头，$First(B)\subseteq First(A)$
3. 多个符号形成的符号串的 First 集
  
  $A\rightarrow B_1B_2…B_n$ ，$B_i$是第一个$\epsilon \notin First(B_i)$的字符，则$First(A)=First(B_1) \cup First(B_2) \cup …\cup First(B_i)-{ \epsilon }$
  
  若$B_1, B_2, …, B_n$均能推出空串，则$First(A)=First(B_1) \cup First(B_2) \cup …\cup First(B_n) \cup {\epsilon}$
Follow 集

Follow 集即一个文法符号后面可能跟随的终结符号的集合(不包括空字符)
1. $Follow(S)= {@}$
2. 欲求的非终结符后跟终结符
  
  $A\rightarrow \alpha Bx\beta$（$x$是终结符），则 $a\in Follow(B)$
3. 欲求的非终结符后跟非终结符
  
  $A\rightarrow \alpha B\beta$，则 $First(\beta ) \subseteq Follow(B)$，若$\epsilon \in First(\beta )$，因为空字符不包括在 Follow 集中，因此 B 后面跟的内容就是 A 后面的内容了，则这种情况下还要加上 $Follow(A)\subseteq Follow(B)$
4. 欲求的非终结符在产生式结尾
  
  $A\rightarrow \alpha B$，则$Follow(A)\subseteq Follow(B)$
判断某文法是不是 LL(1)文法

一个文法是 LL(1)的，当且仅当 G 的任意两个不同的产生式$A\rightarrow \alpha |\beta$满足下面的条件：
1. $First(\alpha)\cap First(\beta)=\phi$
2. 当$\epsilon \in First(\beta)时，Follow(A) \cap First(\alpha)=\phi$
构造 LL(1)分析表

对文法 G 的每个产生式$A\rightarrow \alpha$做如下处理：
1. 对于$First(\alpha)$中的每个终结符号$a$，将$A\rightarrow \alpha$加入到$M[A,a]$中
2. 若$\epsilon \in First(\alpha)$，则对于每个终结符号$b\in Follow(A)$，将$A \rightarrow \alpha$加入到$M[A,b]$中；若$\epsilon \in First(\alpha)$且 $$\in Follow(A)$，则将$A\rightarrow \alpha$也加入到$M[A,@]$中
3. 完成上面的操作后，空白条目即 error

预测分析算法

//ip为输入指针，栈的初始状态为S$
令X=栈顶符号while(X!=$){
    if(X=ip指向的字符a)
      弹栈，ip+1
  else if(X是终结符) error
  else if(M[X,a]=error) error    
  else if(M[X,a]=X->Y1Y2...Yk){    
      输出产生式    
      弹出栈顶符号    
      Yk...Y2Y1入栈，Y1在栈顶    
      ip+1    
  }        
  X=栈顶符号
}

分析栈的作用：保存当前句型

消除左递归

$$
A \rightarrow A\alpha_1 |A\alpha_2 |…|A\alpha_n |\beta_1 |\beta_2 |…|\beta_m\
\Rightarrow A\rightarrow \beta_1 A’|\beta_2 A’|…|\beta_m A’\
A’ \rightarrow \alpha_1 A’|\alpha_2 A’|…|\epsilon
$$

自底向上语法分析

构造 LR(0)规范项集族
- 内核项
  
  $S\rightarrow ·S’$ 以及所有点不在最左端的项
- 非内核项
  
  除了$S\rightarrow ·S’$ 之外的所有点在最左端的项，非内核项可以通过闭包运算重新生成
  1. 增广文法
  在文法 G 中加上一个新的开始符号 S’和产生式$S\rightarrow S’$，目的是使句柄的中止状态只有一个
  1. CLOUSURE 计算
  设 I 是文法 G 的一个项集，则 CLOUSURE(I)根据以下规则计算得到：
  - 将 I 中的各项加入到 CLOUSURE(I)中
  - 若$A\rightarrow \alpha ·B \beta$在 CLOUSURE(I)中，$B\rightarrow \gamma$是一个产生式，并且$B\rightarrow ·\gamma$不在 CLOUSURE(I)中，则将其加入。不断应用该规则直到无新项加入（其实就是相同状态的集合，这两个状态都是准备识别 B 的状态）
  1. GOTO 函数
    
    反正就这么个意思。
构造 GOTO 图
构造 LR 分析表

$si$表示移入并将状态$i$压栈

$rj$表示按照编号为$j$的产生式进行归约
1. 构造增广文法 G’的规范项集族$C={ I_0,I_1,…,I_n}$
2. 根据$I_i$构造得到状态$i$，状态$i$的语法分析动作如下决定：
  - 若$[A\rightarrow \alpha ·a\beta]$在$I_i$中且$GOTO(I_i,a)=I_j$，则将$ACTION[i,a]$设置为$sj$，$a$必须是终结符
  - 若$[A\rightarrow \alpha·]$在$I_i$中，则对于所有的$a\in Follow(A)$，将$ACTION[i,a]$设置为$rj$，这里$j$为产生式$A\rightarrow \alpha$的编号，$A\ne S’$
  - 若$[S’\rightarrow S·]$在$I_i$中，则将$ACTION[i,@]$设置为 acc（接受）
3. 状态$i$对于各个非终结符号 A的 GOTO 转换根据下面的规则得到：若$GOTO(I_i,A)=I_j$，则$GOTO[i,A]=j$
4. 前两条没定义的项设置为 err
5. 语法分析器的初始状态是根据$[S\rightarrow S’]$所在项集构造得到的状态

问题：ACTION 表中有错误信息，GOTO 表中有吗？
答：GOTO 表中没有错误信息，因为 GOTO 表中是归约后的变化

LR 语法分析器的行为

  a=w$的第一个符号while(1){        
  令s为栈顶的状态       
  if(ACTION[s,a]=移入t){                
      将t压栈                
    令a为下一个输入的符号        
    }else if(ACTION[s,a]=归约A->B){                
        从栈中弹出|B|个符号                
        令t为当前栈顶状态                
        将GOTO[t,A]压栈                
        输出产生式A->B                
    }else if(ACTION[s,a]=acc) break;        
    else error();
}

判断某文法是否是 SLR 文法

若在构造语法分析表时有任何冲突动作产生，则该文法不是 SLR(1)文法

Chapter6 中间代码生成

翻译语句生成中间代码

整点薯条

编译原理复习重点

编译原理重点

Chapter4 语法分析

自顶向下语法分析

自底向上语法分析

Chapter6 中间代码生成