编译原理及实现doc81.doc

此文档收集于网络，如有侵权，请联系网站删除第1章 编译原理及实现1.1 程序设计语言1.2 翻译程序图1-1 生成机器语言目标程序的编译方式图1-2 生成汇编语言目标程序的编译方式图1-3 高级语言的解释方式1.3 编译程序的组成图1-4 典型的编译程序模型1.3.1 词法分析1.3.2 语法分析图1-5 句子“猴子吃香蕉”的语法分析树图1-6 表达式a=10+c*20的语法树1.3.3 语义分析及中间代码生成1.3.4 代码优化1.3.5 目标代码生成1.3.6 符号表管理1.3.7 错误处理1.4 编译程序的结构1.4.1 单遍编译程序图1-7 单遍编译程序结构1.4.2 多遍编译程序图1-8 典型的多遍编译程序结构1.4.3 编译程序分遍的优缺点1.4.4 “端”的概念 1.5 编译程序的前后处理器图1-9 从框架源程序到可运行程序1.5.1 预处理器1.5.2 汇编程序1.5.3 连接加载程序1.6 TEST语言与编译器1.6.1 TEST语言1.6.2 TEST编译器1.6.3 TEST机 习题1. 高级程序设计语言有哪些特点？2. 典型的编译程序可划分为几部分？各部分的主要功能是什么？每部分都是必不可少的吗？3. 解释方式和编译方式的区别是什么？4. 论述多遍扫描编译程序的优缺点。第2章 文法和语言2.1 字母表和符号串2.1.1 字母表2.1.2 符号串2.1.3 符号串及其集合的运算2.2 文法2.2.1 文法形式定义2.2.2 文法的EBNF表示2.3 推导2.3.1 直接推导定义2.3.2 推导定义2.3.3 规范推导2.4 句型和句子2.5 语言2.6 递归规则与递归文法2.6.1 递归规则2.6.2 递归文法2.7 短语、简单短语和句柄2.8 语法树图2-1 语法树2.9 子树与短语2.10 由树构造推导过程2.11 文法的二义性图 2-2(a) 语法树1图 2-2(b) 语法树2图 2-3(a) if语句语法树1图 2-3(b) if语句语法树2图2-4 语法树2.12 有关文法的实用限制2.13 文法和语言分类1. 0型文法2. 1型文法3. 2型文法4. 3型文法习题1 设字母表A=a，符号串x=aaa，写出下列符号串及其长度：x0，xx,x5以及A+和A*。2 令=a，b，c，又令x=abc，y=b，z=aab，写出如下符号串及它们的长度：xy，xyz，(xy)3。3 设有文法GS：S=SS*|SS+|a，写出符号串aa+a*规范推导，并构造语法树。4 已知文法GZ：Z=U0|V1，U=Z1|1，V=Z0|0 ，请写出全部由此文法描述的只含有4个符号的句子。5 已知文法GS：S=ABA=aAB=bBcbc 写出该文法描述的语言。6 已知文法E=TE+TE-TT=FT*FT/FF=(E)i写出该文法的开始符号、终结符号集合Vt、非终结符号集合Vn。7 对第6题的文法，写出句型T+T*F+i的短语、简单短语以及句柄。8 设有文法GS：S=S*S|S+S|(S)|a，该文法是二义性文法吗？9 写一文法，使其语言是奇正整数集合。10 给出语言anbm|n，m1的文法。第3章 词法分析3.1 词法分析的功能图3-1 词法分析单独作为一遍图3-2 词法分析作为语法分析子程序3.2 程序语言的单词符号种类及词法分析输出图3-3 词法分析程序的3.3 正则文法及状态图3.3.1 状态图图3-4 状态图3.3.2 状态图的用法图 3-53.4 词法分析程序的设计与实现3.4.1 TEST语言的词法规则及状态图图3-6 各条词法规则的状态图图3-7 单词符号的状态图3.4.2 TEST语言词法分析程序的构造图3-8 词法分析程序流程图3.4.3 TEST语言的词法分析程序实现1. 输出形式2. 词法分析程序3.5 正则表达式3.5.1 正则表达式定义3.5.2 正则文法到正则表达式的转换3.6 有穷自动机3.6.1 确定的有穷自动机1. 确定的有穷自动机定义2. 确定的有穷自动机状态图3. 确定的有穷自动机状态转换矩阵图3-9 状态图图3-10 状态转换矩阵4. 确定的有穷自动机接受的语言图 3-113.6.2 不确定的有穷自动机1. 不确定的有穷自动机定义2. 不确定的有穷自动机接受的语言图 3-123.6.3 NFA到DFA 的转化1. 状态集P的 闭包图3-13 例3-11的NFA M状态图2. 状态集P的 a弧转换集3. 根据NFA构造DFA图3-14 NFA M的状态图图 3-153.6.4 正则表达式与有穷自动机的等价性1. 根据正则表达式构造有穷自动机图3-16 、和a的状态转换图图3-17 R1R2的状态转换图图3-18 R1|R2的状态转换图图3-19 R的状态转换图图3-20 正则表达式到NFA转换图1图3-21 正则表达式到NFA转换图2图3-22 正则表达式到NFA转换图3图3-23 正则表达式到NFA转换图4图3-24 NFA状态图2. 将NFA转换成正则表达式图3-25 由NFA构造正则表达式R1R2图3-26 由NFA构造正则表达式R1|R2图3-27 由NFA构造正则表达式R3.6.5 确定的有穷自动机的化简1. 等价状态与不等价状态图3-28 有等价状态的状态图2. 多余状态图 3-293. DFA化简算法图3-30 等待化简的有穷自动机图3-31 化简后的有穷自动机3.6.6 根据DFA构造词法分析程序1. 直接编程的词法分析器2. 表驱动的词法分析程序图3-32 表驱动的词法分析程序的模型图3-33 分析表3.7 词法分析程序的自动生成器LEX图3-34 LEX使用流程3.7.1 用LEX语言表达正则表达式3.7.2 LEX源程序结构3.7.3 使用LEX生成TEST语言的词法分析程序习题1. 有正则文法GZ：Z=Ua|VbU=Zb|bV=Za|a画出该文法的状态图，并检查句子abba是否合法。2. 状态图如图3-35所示，S为开始状态，Z为终止状态。写出相应的正则文法以及V，Vn和Vt。3. 构造下列正则表达式相应的DFA：1(1|0)*|0 ，1(1010*|1(010)*1)*04. 将图3-36的NFA确定化。图3-35状态图图3-36状态图5. 将图3-37的DFA化简。图3-37DFA状态图6. 修改附录B的词法分析程序，添加保留字do、双分界符&和|以及单分界符!的处理。 7. 修改3.7.3小节TEST的LEX源程序，添加保留字do、双分界符&和|以及单分界符！的处理。第4章语法分析自顶向下分析4.1自顶向下分析方法4.2FIRST集合和FOLLOW集合4.2.1FIRST集合定义及构造方法4.2.2FOLLOW集合定义及构造方法 4.3递归下降分析4.3.1递归下降分析的基本方法图4-1（a） 非终结符号Z的分析程序图4-1（b） 非终结符号U的分析程序4.3.2递归下降分析中存在的问题及解决方法1. 左递归问题图4-2E和T的分析程序流程图2. 解决局部二义性问题3. 右部候选式的第一个符号是非终结符号图4-34.3.3TEST语言的递归下降分析实现4.4LL(1)分析方法图4-4LL(1)分析器模型图4-5分析开始时状况图4-6分析进行中的状况图4-7UVW反序入栈4.4.3LL(1)分析的主要问题及解决方法1. 左递归转成右递归2. 解决分析表多重定义问题习题1. 对下面文法，设计递归下降分析程序。SaAS|(A)AAb|c2. 设有文法GZ：Z=(A)A=a|BbB=Aab若采用递归下降分析方法，对此文法来说，在分析过程中，能否避免回溯？为什么？3. 若有文法如下，设计递归下降分析程序。|ID=|+|-|*|/ID|NUM|()4. 有文法GA：A=aABe|，B=Bb|b(1) 求每个非终结符号的FOLLOW集。(2) 该文法是LL(1)文法吗？(3) 构造LL(1)分析表。5. 若有文法A(A)A|(1) 为非终结符A构造FIRST集合和FOLLOW集合。(2) 说明该文法是LL(1)的文法。6. 利用分析表4-1，识别以下算术表达式，请写出分析过程。（1） i+i*i-i （2） i*(i-i+i)7. 考虑下面简化了的C声明文法：；int|float|charID,|ID（1） 在该文法中提取左因子。（2） 为所得的文法的非终结符构造FIRST集合和FOLLOW集合。（3） 说明所得的文法是LL(1)文法。（4） 为所得的文法构造LL(1)分析表。（5） 假设有输入串为char x,y,z；，写出相对应的LL(1)分析过程。8. 修改语法分析程序，使该程序能分析do语句和逻辑表达式,有关文法规则如下： = if_stat| |=do while = ID=|=(& | | |)|!|其中，&、|、!为逻辑运算符。第5章 语法分析自底向上分析5.1 规范推导、规范句型和规范归约图5-1 归约过程5.2 自底向上分析方法的一般过程5.3 LR分析方法5.3.1 LR分析器逻辑结构图5-2 LR分析器的模型 5.3.2 LR分析表构成5.3.3 LR分析过程图5-3 LR的分析流程5.4 LR(0)分析器5.4.1 活前缀和可归前缀图5-4 语法树5.4.2 LR（0）项目1. 项目的定义2. 项目有效性5.4.3 构造识别活前缀的有穷自动机1. 项目集的闭包运算2. 项目集之间的转换函数GO图 5-5图 5-63. 举例说明识别活前缀的有穷自动机的构造方法图5-7 构造状态图图5-8 识别活前缀的有穷自动机4. 识别活前缀的有穷自动机构造算法5.4.5 LR（0）分析器的工作过程5.4.6 LR（0）文法5.5 SLR（1）分析器5.5.1 SLR解决方法的基本思想5.5.2 SLR（1）分析表的构造5.6 LR(1)分析器图5-9 识别活前缀的自动机5.6.1 LR（1）项目5.6.2 LR（1）项目集规范族构造算法1. LR（1）项目集的闭包运算2. LR（1）项目集转换函数GO3. LR（1）项目集规范族图5-10 基本项目的闭包运算树5.6.3 LR（1）分析表的构造5.7 LALR(1)分析器5.8 语法分析程序的自动生成工具YACC图5-11 YACC使用流程5.8.1 YACC源程序结构5.8.2 YACC源程序说明部分的组成5.8.3 YACC源程序的语法规则部分的组成5.8.4 YACC源程序的程序部分组成5.8.5 二义性文法的处理5.8.6 YACC示例运行习题1. 考虑以下的文法SS；T|TTa(1） 为这个文法构造LR（ 0 ）的项目集规范族。(2） 这个文法是不是LR（ 0 ）文法？如果是，则构造LR（0）分析表。(3） 对输入串a；a进行分析。2. 证明下面文法是SLR（1）文法，但不是LR（0）文法。SAAAb|bBaBaAc|a|aAb3. 证明下面文法是LR（1）文法，但不是SLR（1）文法。SAaAb|BbBaAB4. 考虑以下的文法：EEE+EEE*Ea(1） 为这个文法构造LR（1） 的项目集规范族。(2） 构造LR（1）分析表。(3） 为这个文法构造LALR（1） 的项目集规范族。(4） 构造LALR（1）分析表。(5） 对输入符号串aa*a+进行LR（1）和LALR（1）分析。5. 说明以下的文法是LR（1）文法,但不是LALR（1）文法。SaAd|bBd|aBe|bAeAcBc第6章 语法制导翻译技术6.1 翻译文法6.2 语法制导翻译6.3.1 递归下降翻译图 6-16.3.2 LL(1)翻译器图6-2 栈顶的动作符号出栈并执行6.4 属性翻译文法6.4.1 综合属性图 6-3 6.4.2 继承属性图6-4 其TYPEintIDaIDb的语法树6.4.3 属性翻译文法定义6.4.4 属性翻译文法举例算术表达式的翻译图6-5 表达式a+a*b的属性语法树6.5 属性文法的自顶向下翻译6.5.1 L-属性翻译文法6.5.2 L-属性翻译文法的翻译实现递归下降翻译6.5.3 L-属性翻译文法的翻译实现LL(1)法图6-6 分析栈1.栈符号设计图6-7 栈符号2. 语义动作设计图6-8 LL(1)的工作过程6.6 自底向上语法制导翻译6.6.1 波兰翻译6.6.2 S-属性文法6.6.3 S-属性波兰翻译文法的翻译实现习题1. 构造符号串翻译文法，它接受由0和1组成的任意符号串，并产生下面的输出符号串：（1） 输入符号串的倒置（2） 符号串0m1n2. 根据上题得到的翻译文法，设计递归下降翻译，并用C程序实现翻译。3. 输入文法为：SaASSbAcASbA翻译文法为：SaAxSSbzAcyASvbAw设计递归下降翻译。4. 为上题的输入文法设计LL(1)翻译。5. 属性翻译文法如下：SdTpr p=r TuwaygzTpr z=r,p=u+r,w=r+1Tuwby w=y对输入符号串da2a1b5构造属性计算语法树。6. 对下面的L-属性符号串翻译文法，设计递归下降翻译和LL(1)翻译。S=aiAjdk,lBn k=i, l,n=jS=bmBxgy x,y=52AQ4=apAQ1dQ2,Q3AN Q4,Q3,Q2=Q1AR2=bT1 qT2aR1 T2=T1,R2=R17. 设有文法如下：（0） S LS1（1） LS1ES2，LS1xI1 S1=S2+S1,I1=S1（2） LS1ES2yI2S1=S2,I2=S2（3） ES2avxqyI3S2=v+I3, q=v,I3=q（4） ES2btyIxrS2,I=t,r=I+t该文法是S-属性文法吗？设计LR翻译，并说明每个归约的动作。8. 表达式属性翻译文法如下：EtTpEpt , Ept+Tr ADDp,r,t0 Et0t|-Tr SUBp,r,t0 Et0t t0=NEWTEpt t=pTtFpTpt Tpt*Fr MULTp,r,t0 Tt0t|/Fr DIVp,r,t0 Tt0tt0=NEWTTpt t=pFp (Ep) | ip 编程实现该文法的递归下降翻译。第7章符号表管理技术7.1何时建立和访问符号表7.2符号表的组织和内容图7.1集中存储方法符号表7.3符号表上的操作1. 强类型语言2. 弱类型语言7.4非块程序结构语言的符号表结构1. 无序表2. 有序表3. 散列符号表图7.2散列符号表7.5块程序结构语言的符号表组织7.5.1块程序结构语言的概念7.5.2栈式符号表图7.3栈式符号表习题1. 给出编译下面程序的有序符号表。main()int m,n5;real x;char name;2. 按“质数除余法”，给出上题程序的散列符号表。3. 给出编译到下面程序a、b、c处的栈式符号表。real x,y;char str;/ aint fun1(int ind)int x;/ bx=m2(ind+1);main()char y;/ cx=2;y=5;printf(%d,fun1(x/y);第8章 程序运行时的存储组织及管理8.1程序运行时的存储组织8.2静态存储分配图8.1静态存储分配的典型数据区格局8.3栈式动态存储分配图8.2栈式存储分配的运行栈图8.3典型的活动记录8.3.1活动记录1. 参数区2. display区图8.4栈中活动记录的内容运行8.3.2运行时的地址计算8.3.3递归过程的处理图8.5递归程序的运行栈8.4堆式动态存储分配8.4.1堆分配方式8.4.2堆式存储管理技术图8.6图8.7堆式存储管理的可利用空间表1. 定长块的管理图8.8定长块可利用空间链表2. 变长块的管理图8.93. 释放方法习题1. 什么是静态存储分配？什么是动态存储分配？它们之间有什么不同？2. 活动记录由哪几部分组成？display的作用是什么？3. 静态存储分配对语言有何要求？4. 只有采用动态存储分配的程序设计语言允许有过程递归调用，为什么？5. 画出下段程序运行到a点和b点时的运行栈内容。main()int a;/ a a=f(5); printf(%d,a);int f(int b)int c;c=10; int d;d=10;b=c+d;/ breturn(b);第9章 语义分析和代码生成9.1语义分析的概念9.2中间代码9.2.1波兰后缀表示9.2.2N 元表示1. 三元式2. 四元式3. 抽象机代码9.2.3栈式抽象机及其汇编指令9.3声明的处理9.3.1符号常量9.3.2简单变量9.3.3数组1. 数组模板内容图9.1数组的存储方式2. 数组元素的地址计算图9.2数组模板3. 数组属性翻译文法9.4表达式语句9.5 if语句9.6 while语句9.7 for循环语句9.8write语句9.9 read语句9.10过程调用和返回9.10.1参数的基本传递形式1. 值传递2. 引用传递9.10.2过程调用9.10.3过程定义的处理9.10.4返回语句和过程终止语句9.11语义分析及代码生成实现9.12错误处理习题1. 扩充TEST语言属性文法，加入，其属性文法如下：=do (| ) while () ;=do SETlabellabel1 (| )while () ;BRFla