下载文档原格式
《编译原理》教学大纲大纲说明课程代码： 3225003总学时： 64 学时（讲课 48 学时，实验16 学时）总学分： 4课程类别：学科基础课适用专业 : 计算机科学与技术（专业）预修要求： C 语言程序设计、 C++ 程序设计、数据结构课程的性质、任务及地位：《编译原理》是计算机科学与技术专业的一门重要基础课。
通过对该课程的学习，使学生掌握编译过程中的相关原理和编译技术，让学生能初步进行编译程序的开发和维护，同时促进提高学生开发软件的能力。
教学目的与基本要求：本课程的目的，通过向学生讲述编译系统的结构、工作流程及编译程序各部分的设计原理和实现技术，使学生既掌握编译技术理论的基础与基本知识，也具有设计、实现、分析和维护编译程序等方面的初步能力。
本课程理论性较强。
因授课对象为工科学生，所以在强调编译系统的构造原理和实现方法的同时，为培养学生的实际工作能力，通过上机实践进一步加深学生对课堂教学内容的理解。
目的是要使学生牢固掌握相关的基本理论和基本方法，并能初步利用上述理论和方法解决简单实际问题。
教学方法和教学手段的建议：在教学方法上，贯彻理论联系实际、“精讲、多练”的原则，进行案例式、启发式的教学，对于一些实际性较强的问题要多采用课堂讨论等方式，以提高学生的思辨能力和学习的主动性；引导学生读书、理解、体悟、运用相结合；提高学生的学习兴趣与热情，培养与发挥学生的提出、分析及解决问题的能力。
教学手段：运用多媒体教学手段 +黑板 +上机实验的手段。
采取课堂讲授、课堂讨论、课后练习与自学等形式。
大纲的使用说明：大纲对课程性质、目的等作简单说明，同时列出各章节要学习的知识点、重点、难点，便于教学时教授重点的安排和学生自学安排。
大纲正文第一章引论学时： 4 学时（讲课 4 学时，实验 0 学时）了解编译的概念；理解编译程序的各组成部分及功能。
本章讲授要点：介绍程序设计语言与编译程序间的关系，主要内容包括：各级程序设计语言的定义、源程序的执行、编译程序的构造、编译程序的分类、形式语言理论与编译实现技术的联系。
第六章自底向上优先分析方法•教学要求：了解简单优先分折法，掌握算符优先分析法的关系表的构造以及分析过程。
•教学重点：算符优先表构造及算符优先分析法。
1自底向上分析法的基本思想•从输入串开始，朝着文法的开始符号进行最左归约，直到到达文法的开始符号为止。
•工作方式：“移进－归约”方式。
2分析程序模型1）初态时栈内仅有栈底符“＃”，读头指针在最左单词符号上。
2）语法分析程序执行的动作：a）移进读入一个单词并压入栈内，读头后移；b）归约检查栈顶若干个符号能否进行归约，若能，就以产生式左部替代该符号串，同时输出产生式编号；c）识别成功移进－归约的结局是栈内只剩下栈底符号和文法开始符号，读头也指向语句的结束符；d）识别失败语法分析程序语法表a+b……#输出带#3例如：有文法如下（1）S→aAcBe（2）A→b（3）A→Ab（4）B→d问：语句abbcde是不是该文法的合法语句？4•例：设文法G(S)：(1) S aAcBe(2) A b(3) A Ab(4) B d 试对abbcde进行“移进－归约”分析。
bbcde bbcde b cde de deabbcde eB cA a SB A a 5成功11接受2,3,4,1＃＃S 10归约＃＃aAcBe 9移进2,3,4e ＃＃aAcB 8归约e ＃＃aAc d 7移进de ＃＃aAc 6移进2,3cde ＃＃aA 5归约cde ＃＃a Ab 4移进2bcde ＃＃aA 3归约bcde ＃＃a b 2移进bbcde ＃＃a 1移进abbcde ＃＃0动作输出带输入串栈步骤移进归约的分析过程G[S]:（1）S →aAcBe（2）A →b（3）A →Ab（4）B →d 6遇到的问题：（1）如何找出进行直接归约的简单短语？（2）找出的简单短语应直接归约到哪一个非终结符？关键：确定句柄.常用的分析方法:（1）优先分析法（2）LR分析法7b db ac eSA B A d b a c e S A B A d a c eSA B a c e A B S 没有语法树如何确定句柄？86.1 自底向上优先分析法概述•基本思想：利用文法符号中相邻符号之间的优先关系（谁先规约的优先关系）找出句柄。
•分类:1、简单优先分析：对一个文法按一定原则求出所有符号即终结符号和非终结符号之间的优先关系,按照这种关系确定归约过程中的句柄.特点:准确、规范，但分析效率底，使用价值不大.2、算符优先分析：只规定算符（终结符号）之间的优先关系，不考虑非终结符号之间的优先关系，只要找到句柄就归约，不考虑归约到那个非终结符号。
特点：不是规范归约，分析速度快，特别适合于表达式的分析.96.2 简单优先分析法•基本思想：按照文法符号（终结符号和非终结符号）的优先关系（谁先规约）确定句柄（1）相等关系XY ：当且仅当G 中存在规则A→…XY…（2）小于关系X Y ：当且仅当G 中存在规则A→…XB…，且B Y…=+>（3）大于关系X Y ：当且仅当G 中存在规则A→…BD…，且B …X 和D Y…＞·=+>=*>10•优先关系的形式定义：注意：优先关系是有位置属性的例：构造文法G[S]的简单优先关系表G[S]：S→bAb ，A→（B|a ，B→Aa ）11（1）求关系：b A , A b , ( B , A a , a )（2）求关系：观察每个非终结符和它左边的符号由S→bAb,且A (B , A a , 得b ( , b a 由A→(B , 且B A…,B (B… , B a…得( A , ( ( , ( a =+>=+>=+>=+>=+>（3）求关系：观察每个非终结符和它右边的符号由S→bAb, 且A a, A (B , A …)得a b , B b , ) b 由B→Aa) , 且A a, A (B , A …) 得a a , B a , ) a ＞·=+>=+>=+>=+>=+>=+>＞·＞·＞·＞·＞·＞·简单优先文法的定义：（1）在文法符号集V中，任意两个符号之间最多只有一种优先关系成立。
（2）在文法中任意两个产生式没有相同的右部。
第一条必须满足是显然的，第二条若不满足则会出现规约不唯一13简单优先分析法算法根据给定的简单优先文法构造出相应的简单优先关系表，设置分析栈S ，再根据如下算符步骤进行分析：（1）将输入符号串a 1a 2…a n #依次逐个存入分析栈S 中，直到遇到栈顶符号a i 的优先性下一个待输入符号a j 时为止。
（2）栈顶当前符号ai 为句柄尾，由此向左在栈中找句柄的头符号a k ，即找到a k-1a k ，为止。
（3）由句柄ak …a i 在文法的产生式中查找右部为a k …a i 的产生式，若找到则用相应左部代替句柄，若找不到则为出错。
（4）重复上述三个步骤直到规约完输入符号串，栈中只剩文法的开始符号或出错为止。
＞·14S ## S 移进## bAb Ab ## bA Bb ## b (B 移进b ## b(Aa)移进)b ## b(Aa Aa)b ## b(A a)b ## b(a 规约符输入串关系分析栈接受#b(aa)b #移进# b (aa)b #移进# b(aa)b #移进例：根据下面文法分析输入串b(aa)b # 是否是句子G[S]：S→bAb ，A→（B | a ，B→Aa ）156.3 算符优先分析法一、基本思想1、自下而上归约2、规定算符(更一般地说，指终结符)的优先级及结合规则，以使得分析过程唯一3、比较相邻两个算符而决定动作注：1)关键是对所有算符定义某种优先关系（实际上是谁先规约的关系）2)算符优先分析法是仿效四则运算的计算过程而构造的一种语法分析方法16例：E E+E|E-E|E*E|E/E|(E)|ii+i-i*(i+i)归约过程如下：i+i-i*(i+i) 算量i级别最高，最先归约；E+i-i*(i+i)E+E-i*(i+i) ＋，－同级，先归约左边“＋”E-i*(i+i)E-E*(i+i) －，*不同级，先归约右边“*”E-E*(E+i) 先括号内，后括号外E-E*(E+E) 归约括号内E-E*(E) 归约括号对E-E*E 先归约“*”E-E 后归约“-”E 结束（接受）17一、算符文法的定义1、给定上下文无关文法G，若G中所有产生式右部都不包含两个相继的非终结符，则G为算符文法。
注：算符文法保证了两个运算符之间最多只有一个操作数。
或者说两个操作数之间必有算符（终结符）隔开182)a b 当且仅当G 中含有形如P …aR …的产生式，其中Rb …, 或R Qb …;2、算符优先文法定义设G 是一个不包含ε产生式的算符文法，并设a ,b V T ; P ,Q ,R V N ,定义关系：1)a b 当且仅当G 中含有形如P …ab…产生式，或者P …aQb…产生式；若G 中任一终结符对（a,b ）之间至多满足上述关系之一，则称G 为算符优先文法。
=+>=+>3)a b 当且仅当G 中有形如P …Rb …产生式，其中R …a ，或R …aQ.=+>=+>＞·19•用语法树来理解更直观a b…a B … b …A P… B b…A P …aa b a b …a b…A为非终结符或ε20注意E E * EE + E E * E EE + E+*•表达式文法：E E+E|E*E| (E)|i 是算符文法，但不是算符优先文法。
•两个算符之间的优先关系是有序的，允许有• a b, b a 同时存在，而不允许有a b ，• a b,a b 三种情况之两种同时存在。
+ *＞·＞·＞·211、各非终结符P 的首算符集和尾算符集定义：三、算符优先文法及优先表的构造FIRSTVT P a P a P Qa a V Q V TN(){|,,}或而},,|{)(N T V Q V a aQ P a P a P LASTVT而或 222、构造首算符集和尾算符集算法1)构造集合FIRSTVT(P)的算法根据FIRSTVT(P)的定义，按下面的规则来构造：(1)若有产生式P→a…或P→Qa…，则a FIRSTVT(P)(2)若a FIRSTVT(Q)，且有产生式P→Q…，则a FIRSTVT(P)2)构造LASTVT(P)的算法根据LASTVT (P)的定义，按下面的规则来构造：(1)若有产生式P→…a或P→…aQ，则a LASTVT(P)(2)若a LASTVT(Q)，且有产生式P→…Q ，则a LASTVT(P)233)构造算符优先关系表的计算方法注:如果文法G按此算法构造出的优先表没有重定义项，则文法G是个算符优先文法。
24（1）求关系对如下形式的产生式，A …ab…或A …aQb…有a b 成立（2）求关系对每个非终结符B，观察如下形式的产生式A …aB…有a FIRSTVT （B ）成立（3）求关系对每个非终结符B，观察如下形式的产生式A …Bb…有LASTVT （B ） b 成立0. E’→#E# 为考虑括号#增加的产生式1. E→E+T|T2. T→T*F|F3. F→P F|P4. P→(E)|i构造优先关系表•解：1）计算每个非终结符的FIRSTVT和LASTVT集合FIRSTVT(E’)={#}FIRSTVT(E)={+}∪FIRSTVT(T) FIRSTVT(T)={*}∪FIRSTVT(F) FIRSTVT(F)={ }∪FIRSTVT(P) FIRSTVT(P)={（，i}={+，*， ，（，i}={*， ，（，i}={ ，（，i}250. E ’→#E# 为考虑括号#增加的产生式1. E →E+T|T 2. T →T*F|F 3. F →P F|P 4. P →(E)|i 构造优先关系表•解：1）计算每个非终结符的FIRSTVT 和LASTVT 集合={+，*， ，)，i}={*， ，)，i}={ ，)，i}LASTVT(E’)={#}LASTVT(E)={+}∪LASTVT(T)LASTVT(T)={*} ∪LASTVT(F)LASTVT(F)={ } ∪LASTVT(P)LASTVT(P)={)，i}26LASTVT(E’)={#}LASTVT(E)={+，*， ，)，i }LASTVT(T)={*， ，)，i }LASTVT(F)={ ，)，i }LASTVT(P)={)，i }3)求关系：对表达式文法中终结符在前，非终结符在后的相邻符号对有：#E，+T, *F, F,(E 终结符FIRSTVT (非终结符)4)求关系：对表达式文法中终结符在后，非终结符在前的相邻符号对有：E# ，E+, T*, P ,E)LASTVT(非终结符) 终结符FIRSTVT(E’)={#}FIRSTVT(E)={+，*， ，（，i}FIRSTVT(T)= {*， ，（，i}FIRSTVT(F)= { ，（，i}FIRSTVT(P)= {（，i}0. E ’ #E#1. E E+T|T 2. T T*F|F 3. F P F|P 4. P (E)|i2)求关系：# # ，（）27四、算符优先分析方法1、最左素短语在算符优先分析中，可归约的短语不再称为句柄，而称为最左素短语。
