下载文档原格式
《编译原理》教学大纲大纲说明课程代码： 3225003总学时： 64 学时（讲课 48 学时，实验16 学时）总学分： 4课程类别：学科基础课适用专业 : 计算机科学与技术（专业）预修要求： C 语言程序设计、 C++ 程序设计、数据结构课程的性质、任务及地位：《编译原理》是计算机科学与技术专业的一门重要基础课。
通过对该课程的学习，使学生掌握编译过程中的相关原理和编译技术，让学生能初步进行编译程序的开发和维护，同时促进提高学生开发软件的能力。
教学目的与基本要求：本课程的目的，通过向学生讲述编译系统的结构、工作流程及编译程序各部分的设计原理和实现技术，使学生既掌握编译技术理论的基础与基本知识，也具有设计、实现、分析和维护编译程序等方面的初步能力。
本课程理论性较强。
因授课对象为工科学生，所以在强调编译系统的构造原理和实现方法的同时，为培养学生的实际工作能力，通过上机实践进一步加深学生对课堂教学内容的理解。
目的是要使学生牢固掌握相关的基本理论和基本方法，并能初步利用上述理论和方法解决简单实际问题。
教学方法和教学手段的建议：在教学方法上，贯彻理论联系实际、“精讲、多练”的原则，进行案例式、启发式的教学，对于一些实际性较强的问题要多采用课堂讨论等方式，以提高学生的思辨能力和学习的主动性；引导学生读书、理解、体悟、运用相结合；提高学生的学习兴趣与热情，培养与发挥学生的提出、分析及解决问题的能力。
教学手段：运用多媒体教学手段 +黑板 +上机实验的手段。
采取课堂讲授、课堂讨论、课后练习与自学等形式。
大纲的使用说明：大纲对课程性质、目的等作简单说明，同时列出各章节要学习的知识点、重点、难点，便于教学时教授重点的安排和学生自学安排。
大纲正文第一章引论学时： 4 学时（讲课 4 学时，实验 0 学时）了解编译的概念；理解编译程序的各组成部分及功能。
本章讲授要点：介绍程序设计语言与编译程序间的关系，主要内容包括：各级程序设计语言的定义、源程序的执行、编译程序的构造、编译程序的分类、形式语言理论与编译实现技术的联系。
第五章语法分析—自下而上分析本章要点1. 自下而上语法分析法的基本概念：2. 算符优先分析法；3. LR分析法分析过程；4. 语法分析器自动产生工具Y ACC；5. LR分析过程中的出错处理。
本章目标掌握和理解自下而上分析的基本问题、算符优先分析、LR分析法及语法分析器的自动产生工具YACC等内容。
本章重点1．自下而上语法分析的基本概念：归约、句柄、最左素短语；2．算符优先分析方法：FirstVT, LastVT集的计算，算符优先表的构造，工作原理；3．LR分析器：（1）LR(0)项目集族，LR(1)项目集簇；（2）LR(0)、SLR、LR(1)和LALR(1)分析表的构造；（3）LR分析的基本原理，分析过程；4．LR方法如何用于二义文法；本章难点1. 句柄的概念；2. 算符优先分析法；3. LR分析器基本；作业题一、单项选择题：1. LR语法分析栈中存放的状态是识别________的DFA状态。
a. 前缀；b. 可归前缀；c. 项目；d. 句柄；2. 算符优先分析法每次都是对________进行归约：(a)句柄（b）最左素短语(c)素短语(d)简单短语3. 有文法G＝（｛S｝，｛a｝，｛S→SaS，S→ε｝，S），该文法是________。
a. LL(1)文法；b.二义性文法；c.算符优先文法；d.SLR(1)文法；4. 在编译程序中，语法分析分为自顶向下分析和自底向上分析两类，和LL(1)分析法属于自顶向下分析；a. 深度分析法b. 宽度优先分析法c. 算符优先分析法d. 递归下降子程序分析法5. 自底向上语法分析采用分析法，常用的是自底向上语法分析有算符优先分析法和LR分析法。
a. 递归b. 回溯c. 枚举d. 移进－归约6. 一个LR(k)文法，无论k取多大，。
a. 都是无二义性的；b. 都是二义性的；c. 一部分是二义性的；d. 无法判定二义性；7. 在编译程序中，语法分析分为自顶向下分析和自底向上分析两类，和LR分析法属于自底向上分析。
第五章自底向上优先分析法自底向上优先分析法，其基本思想是采用自左向右扫描，向下而上分析。
该类分析方法是从输入符号串开始，查找句柄，并使用规则把它归约成相应的非终结符号。
任何自底向上分析的关键，就是要找出这种句柄。
本章首先介绍自底向上分析一般过程，然后介绍算符优先分析法。
本章重点：句柄、算符优先分析法第一节自底向上分析一般过程。
先举例说明例1有一文法G[S]S→aAcBeA→bA→AbB→d对输入串abbcde#进行分析，检查该符号串是否是G[S]的句子。
它的最右推导是：S⇒aAcBe⇒aAcde⇒aAbcde⇒abbcde 由此我们可以构造它的逆过程即归约过程。
先设一个先进后出符号栈，并且把句子左括号“#”号放入栈底，其分析过程如下所示上述归约过程，是从输入符号串开始，自底向上地通过归约当前句型的句柄来建立语法树的。
我们不难画出上述分析过程的语法树，下图。
在图中，我们仅画出与生成语法树有关的几步。
从所建立的语法树，可以清楚看出，上述每一步确实都是归约当前句型的句柄。
且句柄出现在符号栈栈顶，不会在栈中间，其实上述分析过程并未真正解决句柄的识别问题。
例如，对于上面的例子，分析进行到第（5）步，当时栈内符号串为aAb。
根据该符号串，我们有规则A→Ab。
和规则A→b。
那么，符号串Ab和b都是某条规则的右部，故都有可能被判别是句型的句柄。
假如我们选择b作为句柄，并把b归约为A，那么，最终就达不到归约到S的目的。
因而，我们也就无从得知输入串abbcde是一个句子了。
在自底向上分析中，如何寻找确定一个句型的句柄是构造一个自左向右扫描，自底向上分析方法必须要解决的一个问题。
第二节算符优先分析法众所周知，作算术式的四则运算时，为了保证计算过程和结果的唯一性，必须要规定一个统一四则运算法则。
这种法则的主要方面，就是规定运算之间的优先顺序。
现在人们所遵循的统一法则是：乘除运算优先于加减运算，故在算术中要先作乘除运算后作加减运算；同优先级的运算符是先左后右（即左结合），先作左边的运算符的运算，后作右边运算符的运算。
编译原理系列之五⾃底向上优先分析（1）-简单优先分析法简单优先分析法1.基本概念通过语法树来理解这三个概念更加简单：⽂法G1[S]：S→ABA→bBA→AaB→aB→Sb语法树1. 短语：若S=*=>αAδ且A=+=>β，则称β是相对于⾮终结符A的句型αβδ的短语。
即：语法树中以⾮终结符的作为根的⼦树的叶⼦所组成的字符串。
如：ba是相对于⾮终结符A的句型AB的短语。
句型baSb的短语有ba，a，Sb，baSb。
2. 直接短语：若S=*=>αAδ且A=>β，则称β是相对于⾮终结符A的句型αβδ的直接短语。
即：语法树中以⾮终结符的作为根的⼦树，它的孩⼦都是叶⼦，没有其他⼦树。
如：Sb是相对于⾮终结符B的句型AB的短语。
句型baSb的短语有a，Sb。
3. 句柄：位于句型最左边的直接短语称为该句型的句柄。
即：位于语法树中最左边的直接短语。
如：句型baSb的句柄是a。
2.优先关系定义1. X和Y优先级相等，表⽰为X=·Y，当且仅当G中存在产⽣式规则A=>···XY···。
解读：X、Y的优先级相同，当XY存在⼀个句柄之中，它们将同时被归约。
表现在语法树中S=·b。
优先级相等在语法树中1. X优先级⼩于Y，表⽰为X<·Y，当且仅当G中存在产⽣式规则A=>···XB···，B=+=>Y···。
解读：X优先级⼩于Y，当XY存在⼀个句型中时，它们将不可能出现在同⼀个句柄中，Y⼀定⽐X先被规约。
表现在语法树中b<·a。
优先级⼩于语法树中1. X优先级⼤于Y，表⽰为X>·Y，当且仅当G中存在产⽣式规则A=>··BD···，B=+=>···X，D=*=>Y···。
第五章语法分析——自下而上分析要紧内容:[1]自下而上分析的大体问题[2]算符优先分析法[3]算符优先分析表和优先函数的构造[4]LR分析器的大体原理大体要求:[1]明白得自下而上分析法的大体思想[2]明白得有关归约、短语、句柄、标准归约等概念[3]把握算符优先分析法[4]了解算符优先表和优先函数的构造技术[5]了解LR 分析器大体原理和工作方式教学要点：本章介绍自下而上语法分析方式。
所谓自下而上分析法确实是从输入串开始，慢慢进行“归约”，直至归约到文法的开始符号；或说，从语法树的结尾开始，步步向上“归约”，直到根结。
讲义摘要：5.1 自下而上分析大体问题自下而上分析法的大体思想：从输入串开始，慢慢进行“归约”，直到文法的开始符号。
即从树结尾开始，构造语法树。
所谓归约，是指依照文法的产生式规那么，把产生式的右部替换成左部符号。
自上而下分析的核心问题是：如何判定符号串的可归约性，和如何归约。
即，识别可归约串的问题。
归约自下而上分析法事实上确实是一种“移进－归约”法，即，采纳“移进－归约”思想进行。
实现思想是：对输入符号串自左向右进行扫描，并将输入符逐个移入一个后进先出栈中，边移入边分析，一旦栈顶符号串形成某个句型的句柄时，（该句型对应某产生式的右部，即栈顶生成了某产生式的右部的文法符号串），就将栈顶的这一部份替换成 (归约为) 该产生式的左部符号，这称为归约。
重复这一进程直到归约到栈中只剩文法的开始符号时那么为分析成功，也就确认输入串是文法的句子。
现举例说明。
例1：设文法G[S]为：(1) S→aAcBe(2) A→b(3) A→Ab(4) B→d试对abbcde进行“移进－归约”分析。
步骤: 1 2 3 4 5 6 7 8 9 10解：动作: 进a 进b 归(2) 进b 归(3) 进c 进d 归(4) 进e 归(1)表1符合栈的转变进程自下而上语法分析的进程也可看成自底向上构造语法树的进程，每步归约都是构造一棵子树，最后当输入串终止时恰好构造出整个语法树，如图1所示。
第六章自底向上优先分析方法•教学要求：了解简单优先分折法，掌握算符优先分析法的关系表的构造以及分析过程。
•教学重点：算符优先表构造及算符优先分析法。
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、最左素短语在算符优先分析中，可归约的短语不再称为句柄，而称为最左素短语。
