编译原理复习总结东北大学.ppt

,编译方法,2013年12月,复习.总结,第一部分 考试范围,一. 概念部分, 概念词语解释(简单明确), 概念词语填空(不求全，只求准),二. 形式语言基础, 简单文法构造, 自己总结。,如：给定一符号串集合，构造文法。, 主要语法成分的识别,给定一文法和一个符号串，证明 是句型(句子)，并画语法树求短语、简单短语和句柄。,(接上页), 简单文法变换技术,如 消除文法的直接左递归！主要是三种常用的文法变换方法 圆括号、方括号和花括号。,三. 自动机基础, 简单有限自动机的构造,如 给定一符号串集合(或正规式或正规文法)，构造有限自动机（DFA）, 求一个有限自动机所定义的语言(符号串集合)。,(接上页),四. 词法分析,1. 2个实验。,五. 语法分析, 给定文法，构造递归子程序（框图）, 判断一个文法是否是 LL(1)文法；,(1) 消除 边， NFA=DFA,(2) NFA = DFA。,5. 有限自动机的实现, 有限自动机的确定化。,4. 确定的有限自动机的最小化。,2. 会写TOKEN 序列；,3. 词法分析技术应用；,(接上页),七. 中间代码生成, 会写常用语句的中间代码(逆波兰式，四元式)；, 会构造常用语法成分的翻译文法；, 给定翻译文法和动作序列，会走翻译过程。, 给定文法，构造LL(1)分析表，, LR(0)文法的判断和相应分析表的构造。,六. 符号表组织,符号表结构以及填写。,5. 简单优先文法的判断和相应分析表的构造。,6. 语法分析器的构造。,4. 语法制导翻译技术的应用。,(接上页),九. 目标代码生成,1. 会写常用语句在单寄存器下的目标代码生成过程；,八. 优化处理,3. 基本块内四元式的优化。,1. 基本块的划分。,2. 局部优化的几种常见方法。,1. 编译程序(compiler),目标语言,词法 分析,源 语言,语法 分析,语义 分析,优化 处理,代码 生成,错 误 处 理,符 号 表 管 理,2. 编译程序结构,五个阶段,第二部分 基本概念总结,是一种语言翻译程序，它特指把,某种高级程序设计语言翻译成具体计算机上的,低级程序设计语言。,4. 文法(上下文无关文法),(接上页),3. 形式语言,所有符号串之集合；其中的每个符号串称为句子。,G(Z)=(VN, VT, S, P),VN : 非终结符集（定义的对象集，如：语法成分等)；,例：,G(E),E - E + T | E T | T,T - T * F | T / F | F,F - i | ( E ),简单算术表达式文法,其中：,VN =E,T,F;,VT=i,+,-,*,/,(,);,Z= E ;,P：,可用四元组表示：,VT : 终结符集（字母表）；,S : 开始符号（研究范畴中，最大的定义对象）；,P : 规则集（又称产生式集）；,字母表上的符号，按一定的规则组成的,是定义语言的规则集，,(接上页),5. 有限自动机(finite automata）FA,是一种数学模型，用于描述正规语言,FA=( Q,S,F, ),：变换（二元函数）：,Q(有限状态集);,F(结束状态集,F Q ）；,S(开始状态集,S Q）；,(字母表)；,或,(i,a）=j, 确定的有限自动机(DFA),特征：开始状态唯一; 变换函数单值；不带边。, 非确定的有限自动机(NFA), 带有边的非确定的有限自动机(NFA), 不带有边的非确定的有限自动机( NFA),- 不能全部具备上述特征者！,6. 有限自动机的分类,其中,可定义为五元组：,(接上页),(1)识别单词从用户的源程序中把单词分离出来; (2)翻译单词把单词转换成机内表示，便于后续处理。,7. 词法分析任务,标识符(i)，常数(c)，关键字(k)，界符(p)。,8. 单词的分类,9. 有限自动机作为单词识别器,注,滤掉回车换行、空格！,(接上页),形式上说，语法分析是指对给定的符号串（），判定其是否是某文法G(S)的句子。即,10. 语法分析,语法分析主要功能是识别短语和句型，,1. 自顶向下法（推导法）,2. 自底向上法（归约法）,11. 语法分析方法分类,12. 四种实用分析方法及相应文法,适应于自顶向下的分析法 - LL(1)文法 是指文法中，具有相同左部的各产生式，其选择集合不相交。,适应于自底向上的分析法 - LR(0)文法 是指文法的句柄识别器(有限自动机)无冲突项目。,(接上页),13. 标识符的语义信息：,名字、类型、种类、地址。,14. 语法制导翻译技术,通俗地说，所谓语法制导翻译技术，是指：,15. 优化处理,优化处理是指产生更高效的目标代码所做的工作。,或者说 为提高目标程序质量所做的工作。,第三部分 基本运算总结,1. 判定一个符号串是否是某文法的句子：,A d B b | c,B B b | ,G(S): S a A B | a A c,哪个符号串是句子？ adbb abc,如：设有文法,【解】, adbb ?,S,= adBbb,+, S = adbb,= aAB,也可以用 语法树证明：,S,a A B,d B b,B b,= adBb,= adbb,adbb 是句子, abc ?,S = aAB,= adBbB = ?,= acB = ?,又 S = aAc,= adBbc = ?,= Acc = ?, abc 不是句子。, 也可以用 语法树证明：,(接上页),2. 简单的文法构造：,设有符号串集合：,L= a,banc | n0 ,构造上下文无关文法； 构造正规文法。,解：,构造上下文无关文法；,(2) 构造正规文法。,G(S):,S - a | b A c,A - a A | ,G(S):,S - a | b A,A - a A | c,3. 求解一个句型的短语和句柄： 如： 已知文法 G(S):,A - a A c | b,试指出句型 abAb 的短语和句柄：,【解】, 首先画该句型的语法树：,S,a S A,b A,b,句柄 是一个句型的最左简单短语。,短语 是一个句型任一子树的树叶全体。,简单短语 是一个句型任一简单子树的树叶全体。, 根据语法树确认短语和句柄：,短语： abAb , bA , b,简单短语： bA , b,句柄：bA,S - b A | a S A,【解】, S - a A b | a (首符号相同), 变换后得： S - a A b ,或 S - a S ; S - A b | , A - A b | d （直接左递归）, 变换后得： A - d b ,或 A - d A ; A - b A | ,4. 简单的文法变换：,如： 有文法 G(S): S - a A b | a,A - A b | d,(1) 具有相同左部的各产生式，其首符号不相同；,试进行文法变换，使其满足以下两个条件：,(2) 消除文法的左递归 ., 变换后的文法 G(S):,S - a A b ,A - d b ,5. 有限自动机的构造：,如：已知符号串集合：,A=an,ban|n0 ,试构造有限自动机。,【解】,a,+,b,-,此集合有两种句型（还包含一个空串 ）, 分别构造之：,-,+,+,-,a, 合成为一个：,b,-,+,-,a,a,错误,b,正确,+,-,a,a,-,a,-,6. 有限自动机的确定化：,如 把下述 NFA 转换为 DFA:(消边, DFA最小化, 略),C2,3,B2,C2,3,C2,3,B2,C2,3,B2,-,B2,3,B2,3,B2,3,-,7. 正规语言的三种表示方法：,(2) 有限自动机：,+,-,a,b,c,c,设有正规语言： L= acn,bcm |n0,m0 ,(1) 正规式：,e = ac* | bc+,(3) 正规文法：,G(S):,S - a A |b B,A - c A |,B - c A,令,3,5,y,a,x,8.已知源程序片断,写出词法分析后的 TOKEN序列:,如：if ( x 5 ) y = 3 * x a ; ,KTk,PTp, 自己设定符号表：,(k,3),(p,7),(c,1),(p,8),(i,2),(p,5),(i,1),(p,2),(i,3),(p,9), TOKEN 序列：,(i,1),(p,6),(c,2),(p,3),9. 2个实验, 略,10. 词法分析技术应用,已知定点数的结构如下: 开始以数字开头, 后随一串0 或多个数字,再后随一个点“.”, 点后面一串0 或多个数字, 在点后至少有一位数字。,2.在自动机的结点处插入适当的语义动作，分别统计点“.”的前后各有几个零。,1给出该定点数的正规式和自动机 FA,例:,解:,1,2,3,4,+,d,.,d,-,d,d,0,0,0,Q2:if (ch=0)num1+;,Q3:if (ch=0)num2+;,Q1: num1=0;num2=0;,Q4:if (ch=0)num2+;,10. 给定文法会构造递归子程序(框图)：,例：,err2,NEXT(w),err1,NEXT(w),S子程序,n,n,n,y,y,b,d,NEXT(w),y,S -aASb|Bd ; A -cS| ; B -bB|d, 遇终结符，判定之；, 遇非终结符，调用之；, 遇 ，直接出口。,算法,NEXT(w),遇时,n,y,A子程序,NEXT(w),n,y,NEXT(w),err3,y,n,B子程序,11. 会判定LL(1)文法和构造LL(1)分析表,如 已知文法 G(S) ：,（1）求选择集合；证明是LL(1)文法；,select()= ,select()= ,select()= ,select()= ,select()= ,select()=,= ,【解】,（1）求选择集合,a,b,d,c,follow(A),a,b,d,b,d,（2） LL(1)分析表:, 三对选择集合两两不相交!, G(S)是 LL(1)文法!,（2）构造 LL(1)分析表。,如,12. 会判定LR(0)文法和构造LR(0)分析表,B - c9 ,Z- Z1 (0),Z - a2 B3 A4 d5 (1),A - b6 c7 (2) | c8 (3),扩展文法, LR（ ）分析表：,a2,Z1,1,A4,OK,r(1),r(1),r(1),r(1),r(1),d5,r(3),r(3),r(3),r(3),r(3),r(2),r(2),r(2),r(2),r(2),c8,b6,B3,c9,5,4,8,6,7,3,2,9,r(4),r(4),r(4),r(4),r(4),c7, 分析表中无冲突项目， 是LR(0)文法！,0,【例】,头符号集合 尾符号集合,优先矩阵,表项=空 表示两个符号不可能相临。,13. 会判定简单优先文法和构造简单优先分析表,14. 会写表达式的逆波兰式,例：求下述表达式的逆波兰式：,= pos(a+b/d) e *, pos( (a+b/d)*e ),= pos(a+b/d)pos(e) *,= pos(a)pos(b/d)+ e *,= a bd/ + e *, pos(a+b/d)*e )= a b d / + e *,(a+b/d)*e , pos( ) ?,脱括号,a,b,d,/,+,e,*,注,根据逆波兰式特点：, 运算对象顺序不变；, 运算符紧跟运算对象之后。, 可直接写出：,算术表达式四元式翻译文法：,15. 会构造常见语法成分的四元式翻译文法,【例】, 算术表达式逆波兰式翻译文法：,E T | E + T “PUSH(+)” T F | T * F “PUSH(*)” F i“PUSH(i)” | ( E ) 其中: PUSH(x) - 把 x 压入分析栈；,QUAT(+),QUAT(*),16. 会走翻译过程的动作序列：,E,=T,=T*F*,=F*F*,=aa*F*,=aa*(E)*,=aa*(E+T+)*,=ai*(T+T+)*,【例】 算术表达式逆波兰式翻译文法,abc+*, 动作序列的执行结果：, 相应的四元式动作序列：,PUSH(a) PUSH(b) PUSH(c) GEQ(+) GEQ(*),执行的 过程、结果如何?!,【例:】 给定文法如下：,(,(a,),a) 变