编译原理复习五

这是我参与更文挑战的第24天，活动详情查看： 更文挑战

第五章、自底向上优先分析

5.1、常用方法：移进-规约分析

四个动作：移进、规约、接受、出错

5.2、简单优先分析 vs 算符优先分析 vs LR分析（考判断题）

• **简单优先分析：**按句柄进行规约，是规范规约
• **算符优先分析：**按照其他可规约串进行规约，不是规范规约
• **LR分析：**按句柄进行规约，是规范规约

5.3、优先关系定义（考判断题）

• 若X和Y的优先性相等，表示为：X=Y（中间有点）
• 若X和Y的优先性比Y的优先性大，表示为X>Y（中间有点）
• 若X和Y的优先性比Y的优先性小，表示为X<Y（中间有点）

需要注意的是：X>Y，不能推出Y<X

5.4、**算符优先分析

只考虑终结符之间的优先关系

5.5、**算符文法（OG） vs 算符优先文法（OPG）

• 算符优先文法：设有文法G，如果G中没有形如A->…BC…的产生式，其中B和C为非终结符，则称G为算符文法，也称OG文法

  任何句型都不包含两个相邻的非终结符

• 算符优先文法：不含$\epsilon$产生式的算符文法，如果任一终结符对(a,b)之间至多有>,<,=三种关系中的一种成立，则称G是一个算符优先文法，也称OPG文法。

  1. 不含空产生式
  2. 算符文法
  3. 任一终结符对至多只有一种对应关系

5.6、算符优先关系

• a=b，当且仅当G中含有：A->…ab.. 或 A->…aBb…
• a<b，当且仅当G中含有：A->…aB…且B=>b…(上面有+号)或者B=>Cb…(上面有+号)
• a>b，当且仅当G中含有：A->…Bb…且B=>…a(上面有+号)或者B=>…aC(上面有+号)

5.7、算符优先关系表的构造

• $FirstVT(B)$：表示B能推出的第一个终结符
• $LastVT(B)$：表示B能推出的最后一个终结符

5.8、最左素短语

设有文法G[S]，其句型的素短语是一个短语，它至少包含一个终结符，并出自身外不包含其他素短语，最左边的素短语称最左素短语

第六章、LR分析

6.1、**LR(0)分析步骤与相关例题（考大题）

1. 构造LR(0)项目集规范族
2. 构造LR(0)分析表
3. 对输入串进行LR(0)分析

组成部分：状态栈、符号栈、ACTION表、GOTO表

需要注意：

• 状态表示为活前缀的项目集编号

• Action[A,a]=Sj，a为终结符，则：把a移入符号栈，S移入状态栈

• Action[A,a]=rj，a为终结符或#号，则：利用第j个产生式（j表示产生式编号）进行归约

• Action[S,a]=acc，则为接受

• Goto[S,A]=j，A为非终结符，表名前一动作是用关于A的产生式归约的。A移入符号栈，j移入状态栈

6.2、项目类型

• 移进项目：圆点后为终结符的项目
• 规约项目：圆点在产生式右部最后的项目
• 待约项目：圆点后为非终结符的项目
• **接受项目：**当规约项目为S’->S点 时

6.3、项目冲突

• 移进-归约冲突
• 归约-归约冲突

$SLR(1)$分析用来解决此类问题