编译原理知识点
- 格式：doc
- 大小：219.50 KB
- 文档页数：7
1. 解释程序：不生成目标代码
编译程序：生成目标代码
2. 编译程序组成：8个
分析< 前端 >：(词法分析程序、语法分析程序、语义分析程序、中间代码生成程序)
综合< 后端 >：（代码优化程序、目标代码生成程序）
贯穿始末：表格管理程序、出错处理程序
3. 文法四元组：
终结符号集合Vt 、非终结符号集合Vn、 产生式集合P、识别符号(开始符号)S
VT∩VN＝Φ
文法 -> 语言 （推导、规约）唯一； 语言 -> 文法 （凑规则）不唯一。
4. 文法分类：
0型文法(短语结构文法)：左侧至少含有一个非终结符
1型文法(上下文有关文法)：左侧长度 <= 右侧长度 S->ε除外， S不能出现在右侧
2型文法(上下文无关文法)：左侧只能有一个非终结符 ( 语法分析 )
3型文法(正规文法)：A-> aB A->a 右线性； ( 词法分析 )
A->Ba 或A->a 左线性（看非终结符位置）
5. A*＝ A0 ∪ A+ A0 ＝{ε} != { } ＝Φ空集
A+ ＝ AA* ＝ A*A
6. 句型：符号串x是从识别符号S推导出来的，x称为一个句型
句子：x仅由终结符号组成，仅含终结符号的句型是一个句子
短语：子树的末端（叶子）从左至右连成的串（包括整棵语法树）
简单子树：只含有单层分枝的子树
直接短语( 简单短语 )：由简单子树的叶子组成
句柄：最左边的直接短语（不一定含终结符）
素短语：至少含有一个终结符的短语，并且除它自身之外不再含任何更小的素短语
最左素短语：最左边的素短语
短语：P（相对于T、E）、 P+T（相对于E）、i（相对于P、F）、P+T+i（相对于E）
直接短语：P、i 句柄：P (最左边的直接短语)
素短语：P+T 、i （至少含有一个终结符的短语） 最左素短语：P+T
7. 二义性文法：有两个不同的最左推导或有两个不同的最右推导或能产生两棵语法树
8. 文法产生式 正规式
规则1 AxB By A = xy 规则2 AxA|y A = x*y 右线性
AAx|y A = yx* 左线性
规则3 Ax Ay
A = x|y
9. DFA 初态唯一，转换函数为单值映射
表示方式：转移矩阵、状态转换图
状态转换图上若存在一条从初态到某一终态的道路，且这条路上所有弧的标记符连成的字符串为t，则称t被DFA接受。
10. NFA初态可为多个，转换函数为多值映射
确定化：与某一NFA等价的DFA不唯一
1.状态集合I的ε-闭包
2.move函数
最小化：消除多余状态和合并等价状态
多余状态：从自动机的开始状态出发，任何输入串也不能到达的那个状态；或者从这个状态没有通路到达终态。
11. 左公因子
显式左公因子提取
若A→1|r，则将其改写为：
i. A→(1|r)
ii. 或引入新非终结符 A→A’ A’→1|r
隐式左公因子:产生式右部以非终结符开始
用该非终结符的右部以终结符开始的产生式去替换它，再提取
S→aSd|Ac A→aS|b
把A的产生式代入S中： S→aSd|aSc|bc
S→aS S’ S’ →d|c S→bc
12. 左递归
1.简单左递归：消除左递归改写为右递归
A→A|
A→A’
A’→A’|ε
2.间接左递归
非终结符号排序(出现频率高的排后面)
左部非终结符下标 > 右部时改写（替换右部）
消除直接左递归
13. 自顶向下：LL（1）
FIRST：A X1X2X3…Xn
若X1 ε X2 ε X3 !ε 后面不用管
则FIRST（A）= First（X1）-{ε} U First（X2）-{ε} First（X3）
若全能推出ε 则先求所有FIRIST（X）-{ε}并集 再并上{ε}
FOLLOW：
• (a)设S为开始符号，则#∈FOLLOW(S)
• (b)若有产生式A B， !* ε，则FIRST(β) 加至FOLLOW(B)
• (c)若 *ε (即FIRST(β)），则FIRST()-{ε}和FOLLOW(A)加至FOLLOW(B)
SELECT：
A 的可选集SELECT
* !ε，则SELECT(A)= FIRST()
*ε，则SELECT(A)= FIRST()-{ε}∪ FOLLOW(A)
一个上下文无关文法G是LL(1)文法的充要条件是：
对于G的每个非终结符号A的任何两个不同产生式 A→α，A→β满足：
SELECT(A→α)∩SELECT(A→β)=
α、β不同时推导出ε
LL（1）的含义：
第一个L：从左到右扫描输入串
第二个L：分析过程中用最左推导 1：只需向右看1个输入符号（Look ahead)便可确定选用哪个产生式进行推导
– LL(1)文法是无二义的。
– LL(1)文法不含左递归。
14. 自底向上：算符优先、LR（0）、SLR（1）、LR（1）、LALR（1）
15. 规范归约：最右推导的逆过程(最左归约）
• 最右推导是规范推导 右句型(最右推导可得的句型）是规范句型
• 规范句型的特点：句柄后（右边）不会出现非终结符
• 规范归约的中心问题是：如何寻找或确定一个句型的句柄 。
• 可归约串：
• 最左素短语(算符优先分析法）
• 句柄(LR分析法)
算符优先分析法不是规范归约方法。
16. 若文法G中不存在右部含有相邻非终结符的产生式，则G为算符文法
算符优先分析的可归约串是句型的最左素短语。
起决定作用的是相邻两个终结符的优先关系
a≡b 当且仅当G中存在产生式规则 A…ab…，或A…aBb…
ab 当且仅当G中存在产生式规则 A…aB…，且B+b…或 B+Cb…
ab 当且仅当G中存在产生式规则 A…Bb…，且B+…a或 B+…aC
不允许有a<·b、a≡b、a·>b中的两种关系同时存在
17. FIRSTVT计算如下：
若有产生式Aa…或ABa…
则aFIRSTVT(A) A左侧的终结符 < FIRSTVT(A)
若aFIRSTVT(B)且有产生式AB…(B后面没有紧跟一个终结符)
则aFIRSTVT(A)
A->a.......，即以终结符开头，该终结符入Firstvt
A->B.......，即以非终结符开头，该非终结符的Firstvt入A的Firstvt
A->Ba.....，即先以非终结符开头，紧跟终结符，则终结符入Firstvt
LASTVT计算如下：
若有产生式A…a或A…aB
则aLASTVT(A) A右侧的终结符 < LASTVT (A)
若aLASTVT(B)且有产生式A…B
则aLASTVT(A)
A->.......a，即以终结符结尾，该终结符入Lastvt
A->.......B，即以非终结符结尾，该非终结符的Lastvt入A的Lastvt
A->.....aB，即先以非终结符结尾，前面是终结符，则终结符入Lastvt
18. LR分析法的归约过程是规范推导的逆过程，所以LR分析过程是一种规范归约过程
无回溯的“移进-归约”方法
符号栈中的符号是规范句型的前缀，且不含句柄以后的任何符号(活前缀)
ACTION 移进 归约 接受 出错 ACTION[i,a]=空白 出错
ACTION[i,a]=acc 符号栈中仅有#和文法开始符号S，输入串仅为#，分析结束。
19. 一个句型的某个前缀的后缀是该句型的句柄，则这个前缀称为该句型的可归前缀。
一个规范句型的一个前缀，若不含句柄之后的任何符号，则称它为该句型的一个活前缀。
S -> a Ac. B e 项目中 .之前a Ac为活前缀
20. A a,aVT 移进项目
A B,BVN 待归约项目
A 归约项目
特别地：A 只有 A
S’S, S’S 接受项目
以上项目称作LR(0)项目。
21. LR(0) 项目集规范族（识别G的活前缀的DFA)
如果不存在移进-归约冲突，归约-归约冲突，则称它是LR(0)文法。
拓展文法的目的：使文法只有一个以识别符号作为左部的产生式，从而使构造出来的分析器有唯一的接受状态。
22. 对给定的文法，利用LR(0)方法判断符号串是否为该文法的句子：
1.扩充文法为拓广文法；
2.构造识别此文法的全部活前缀的DFA，即构造LR(0)项目集规范族；
3.判断是否为LR(0)文法；
4.是 构造LR(0)分析表 利用LR分析算法分析符号串。
5.否，做其他处理。
23. SLR（1）对所有非终结符都求出其FOLLOW集合
发生冲突时，归约项目左部终结符FOLLOW集与移进项目 .后的终结符交集为空时，才能按此规约项目的产生式进行归约。
– LR(0)分析对所有终结符均采用归约动作
– SLR(1)分析参考FOLLOW集，以确定归约动作。
24. Follow集无法解决 移进-归约冲突或归约-归约冲突，考虑后继符
25. 归约动作的选择：
a) LR(0)分析考虑所有终结符
b) SLR(1)分析参考 FOLLOW 集，为了确定归约
c) LR(1)分析仅考虑 LR(1)项目中的后继符（归约展望集，向前搜索符）
拓展文法的后继符为#，即[ S’->S , #] 为初态集的初始项目，S后first(，#) = {#}
LR（1）项目集规范族中，每个状态中添加新的产生式时，需求产生式左部字母后面的First集作为新产生式的后继符;否则后继符照抄前一个状态的
I : A->a.Bβ B->.e ，需求出First（β）作为B->.e的后继符
26. 任何二义文法决不是一个LR文法
LL(k)文法都是LR(k)文法。
27. a=b*c+b*d 逆波兰式：abc*bd*+= （算符优先的一个应用）
无括号; 运算对象顺序不变; 运算符号的位置反映运算顺序。
