编译原理( 陈火旺)第2章 高级语言及其语法描述

2011年考研，离散数学和编译原理怎么复习2010-06-23 10:37离散数学和编译原理前阵子很多人在议论说2010年如果加考离散数学怎么办。

其实，在本科阶段，这两门课是典型的学起来很难而考试出题比较简单的科目。

就算2010年添了离散数学，也肯定占不了太多的分，认真把定义搞懂搞熟，拿个七八成的分不是多大问题。

离散数学蛮多的内容出题和解题的思路都是死的，不像高数有那么多的定理和公式，遇到难题还要拆来凑去啥的。

尤其要注意的一点是——紧扣定义！！打个易懂的比喻，高等数学是求值，线性代数是求解的个数，那么离散数学的一个核心要素就是求元素以及集合之间的相互关系。

不要抱着一种求具体值的思想来解离散数学题。

离散数学和编译原理是学好了很有用的两门课，要钻进去，而不是逃避，因为你当初义无反顾地选择了计算机科学与技术这个振奋人心的专业。

离散数学中的集合论思想对我们思考问题的方式有着巨大帮助，而编译原理是要写出高效能软件所必须掌握的课程。

中国科学技术大学2009年计算机学院考研复试就以笔试形式考了这两门课，100分，占了复试的半壁江山了，可见它们的重要性。

\计算机基础综合的大纲到8月初左右公布，如果真要考的话，我推荐下参考书：<<离散数学>>——方世昌编著西安电子科技大学出版社配套有本绿色的习题解答，写的很详细。

我本科是西电计算机学院的，做过这2本书，感觉不错。

而它更是被指定为这次中科大复试的参考书目，多少具备了一定的权威性。

方世昌老师是个不折不扣的牛人，国内第一本外文算法书教材就是他翻译过来的，我读过一本<<算法设计技巧与分析>>也是他翻译的。

编译原理有些学校复试可能会考，认真研究一下陈意云老师的<<编译原理>>和配套那本薄薄的习题精选（高等教育出版社），就没啥问题了。

关于政治改革和报辅导班听说2010年政治变动蛮大，也不必惊慌，第一次改革一般出题都不会很难。

教学内容• 2.0 语言概述• 2.1 程序语言的定义• 2.2 文法的直观概念与语言的关系--- 重点• 2.3 程序设计语言的语法描述--- 重点难点1• 对于高级程序设计语言及其编译程序来说，语言的语法定义是很重要的。

• 本章主要介绍语法结构的形式描述问题，并讨论上下文无关文法、正规文法。

• 编译原理主要内容也可以归结为应用形式语言理论，并将它贯穿于词法分析和语法分析两个阶段。

232.0 语言概述Ø 语言是某一字母表上符号串 (句子)的集合。

ü -- ü --语法 语义4Ø ？2.0 语言概述• • • ü ü “ ” “ ”52.1 程序语言的定义 P12 • 62.1.1 语法ü ü • ={ + }– 0.5*x1+c– 0.5 x1 c * +– 0.5*x1+c72.1.1 语法• ü • ü • 82.1.2 语义 P13• ： ü ü – A=B– A B C– A B P– 92.1.3 程序 P14数据引用 算符 函数调用10 • ü ü Σ V2.1.4 有关定义和记号及运算 P25 • ü • ü ü ( ): ( ), ε ü ü abc 3 |abc|=3 |ε|=011• ü 2.1.4 有关定义和记号及运算(P25) • ü (a,b,c …) (α,β,γ…) (A,B,C …)ε {ε} { }ε{} εΦ { }122.1.4 有关定义和记号及运算(P25) • ü A={α1,α2,…} B={β1,β2,…} AB={αβ|α∈A and β∈B}ü A n-1n A n1 ε A A2 AB BA3 A 0={ε}4 A n A n132.1.4 有关定义和记号及运算 – A {a}– A 0={ε} A 1=A={a}……– A n =AA n-1(n>0)={a …a}– A={a,b}; B={c,e,d}– AB={ }n 个aac, ae, ad, bc, be, bd14• ü A B A B A+B ( A ∪B)ü A+B={α|α∈A 或 α∈B}ü A+B A B A={a,b,c} B={00,11}A+B={ } AB={ }2.1.4 有关定义和记号及运算 a,b,c,00,11a00,a11,b00,b11,c00,c11152.1.4 有关定义和记号及运算 • A A *A *=A 0∪A 1∪A 2∪… ü A {ε } • A A +A += A 1 ∪A 2∪ …=A *-{ε}ü A {ε}16Ø 当我们表述一种语言时，无非是说明这种语言的句子，如果语言只含有有穷多个句子，则只需列出句子的有穷集就行了，但对于含有无穷句子的语言来讲，存在着如何给出它的有穷表示的问题。

第二章 高级语言及其语法描述4．令+、*和↑代表加，乘和乘幂，按如下的非标准优先级和结合性质的约定，计算1+1*2↑2*1↑2的值：（1） 优先顺序（从高至低）为+，*和↑，同级优先采用左结合。

（2） 优先顺序为↑，+，*，同级优先采用右结合。

解：（1）1+1*2↑2*1↑2=2*2↑1*1↑2=4↑1↑2=4↑2=16 （2）1+1*2↑2*1↑2=1+1*2*1=2*2*1=2*2=46．令文法G6为 N →D|NDD →0|1|2|3|4|5|6|7|8|9 （1） G6 的语言L （G6）是什么？（2） 给出句子0127、34和568的最左推导和最右推导。

解：（1）L （G6）=｛a|a ∈∑+,∑=﹛0,1,2,3,4,5,6,7,8,9｝｝（2）N ＝＞ND ＝＞ NDD ＝＞ NDDD ＝＞ DDDD ＝＞ 0DDD ＝＞ 01DD ＝＞ 012D ＝＞ 0127 N ＝＞ ND ＝＞ N7＝＞ ND7＝＞ N27＝＞ ND27＝＞ N127＝＞ D127＝＞ 0127 N ＝＞ ND ＝＞ DD ＝＞ 3D ＝＞ 34 N ＝＞ ND ＝＞ N4＝＞ D4 ＝＞34N ＝＞ ND ＝＞ NDD ＝＞ DDD ＝＞ 5DD ＝＞ 56D ＝＞ 568 N ＝＞ ND ＝＞ N8＝＞ ND8＝＞ N68＝＞ D68＝＞ 5687．写一个文法，使其语言是奇数集，且每个奇数不以0开头。

解：A →SN, S →+|-|∑, N →D|MDD →1|3|5|7|9, M →MB|1|2|3|4|5|6|7|8|9 B →0|1|2|3|4|5|6|7|8|9 8. 文法：E T E T E T TF T F T F F E i→+-→→|||*|/()| 最左推导:E E T T TF T i T i T F i F F i i F i i i E T T F F F i F i E i E T i T T i F T i i T i i F i i i ⇒+⇒+⇒+⇒+⇒+⇒+⇒+⇒+⇒⇒⇒⇒⇒⇒+⇒+⇒+⇒+⇒+⇒+********()*()*()*()*()*()*()最右推导:E E T E TF E T i E F i E i i T i i F i i i i i E T F T F F F E F E T F E F F E i F T i F F i F i i i i i ⇒+⇒+⇒+⇒+⇒+⇒+⇒+⇒+⇒⇒⇒⇒⇒+⇒+⇒+⇒+⇒+⇒+⇒+**********()*()*()*()*()*()*()*()语法树：/********************************EE FTE +T F F T +iiiEEFTE-T F F T -iiiEEFT+T F FTiii*i+i+ii-i-ii+i*i*****************/9．证明下面的文法是二义的：S → iSeS|iS|I解：因为iiiiei 有两种最左推导，所以此文法是二义的。

第二章高级语言及其语法描述1、设有文法G[S]：S→NN→D|NDD→0|1|2|…|9试写出028和4321的最左推导和最右推导过程。

2、证明文法G[S]是二义性文法：S→if E then S else S |if E then S |sE→0|13、设有文法G[E]：E→E-T|TT→T/F|FF→i|(E)（1）试写出i/(i-i-i)的推导树。

（2）试写出（F-i）/F的短语、简单短语和句柄。

4、设∑={0,1}，请给出∑上下列语言的文法（1）所有以0开头的串（2）所有以0开头，以1结尾的串5、证明文法G1和G2等价G1：S→0S1，S→01G2：A→0R，A→01，R→A1第三章有限状态自动机和词法分析1、请用中文描述下列正规式表示的正规集（1）0(0|1)*0（2）0*10*10*10*2、试写出∑＝{0，1}上下列集合的正则表达式：（1）所有以1开始和结束的符号串。

（2）恰含有3个1的所有符号所组成的集合。

（3）集合{01，1}。

（4）所有以111结束的符号串。

3、试写出∑＝{0，1}上下述集合的正则表达式： （1）试写出非负整数集的正则表达式。

（2）试写出以非5数字为头的所有非负整数集的正则表达式。

4、试将图3.1中所示的有限状态自动机M 最小化。

图3.1 M 的状态转换图5、设∑＝{a,b}，试构造下述正则表达式的确定性有限状态自动机： （1）a(a|b)*baa （2）(a|b)*bbb *6、对于下列的状态转换矩阵：（1）分别画出相应的状态转换图。

（2）用自然语言分别描述它们所识别的输入串的特征 7、将图3.2所示的非确定的有限状态自动机确定化和最小化。

图3.2 非确定的有限状态自动机M第四章 自顶向下语法分析 1、从下列文法中消去左递归。

（1）S→Aa|bA→Ac|Sd（2）A→A∨B|BB→B∧C|CC→⌝D|DD→(A)|i2、请消去下面文法G[S]中的回溯G[S]：S→aBc|aB→bB|ε3、有文法G[S]：S→ABA→a|εB→b|ε（1）验证该文法是LL(1)文法；（2）请构造预测分析表4、考虑文法G[A]：A→aABc|d|εB→Bb|b（1）改写为LL(1)文法；（2）请构造预测分析表（3）给出句子adbc的分析过程第五章自底向上语法分析1、请对下列文法G[S]构造算符优先分析表S→bAbA→(B|aB→A a)2、文法G[S]：S→S(SaS→b该文法是LR(0)还是SLR(1)文法？3、文法G[A]：A→(A)|a构造该文法的LR(0)分析表，并请描述((a))的分析过程。

第二章 高级语言及其语法描述4．令+、*和↑代表加，乘和乘幂，按如下的非标准优先级和结合性质的约定，计算1+1*2↑2*1↑2的值：（1） 优先顺序（从高至低）为+，*和↑，同级优先采用左结合。

（2） 优先顺序为↑，+，*，同级优先采用右结合。

解：（1）1+1*2↑2*1↑2=2*2↑1*1↑2=4↑1↑2=4↑2=16 （2）1+1*2↑2*1↑2=1+1*2*1=2*2*1=2*2=46．令文法G6为 N →D|NDD →0|1|2|3|4|5|6|7|8|9 （1） G6 的语言L （G6）是什么？（2） 给出句子0127、34和568的最左推导和最右推导。

解：（1）L （G6）=｛a|a ∈∑+,∑=﹛0,1,2,3,4,5,6,7,8,9｝｝（2）N ＝＞ND ＝＞ NDD ＝＞ NDDD ＝＞ DDDD ＝＞ 0DDD ＝＞ 01DD ＝＞ 012D ＝＞ 0127 N ＝＞ ND ＝＞ N7＝＞ ND7＝＞ N27＝＞ ND27＝＞ N127＝＞ D127＝＞ 0127 N ＝＞ ND ＝＞ DD ＝＞ 3D ＝＞ 34 N ＝＞ ND ＝＞ N4＝＞ D4 ＝＞34N ＝＞ ND ＝＞ NDD ＝＞ DDD ＝＞ 5DD ＝＞ 56D ＝＞ 568 N ＝＞ ND ＝＞ N8＝＞ ND8＝＞ N68＝＞ D68＝＞ 5687．写一个文法，使其语言是奇数集，且每个奇数不以0开头。

解：A →SN, S →+|-|∑, N →D|MDD →1|3|5|7|9, M →MB|1|2|3|4|5|6|7|8|9 B →0|1|2|3|4|5|6|7|8|9 8. 文法：E T E T E T TF T F T F F E i→+-→→|||*|/()| 最左推导:E E T T TF T i T i T F i F F i i F i i i E T T F F F i F i E i E T i T T i F T i i T i i F i i i ⇒+⇒+⇒+⇒+⇒+⇒+⇒+⇒+⇒⇒⇒⇒⇒⇒+⇒+⇒+⇒+⇒+⇒+********()*()*()*()*()*()*()最右推导:E E T E TF E T i E F i E i i T i i F i i i i i E T F T F F F E F E T F E F F E i F T i F F i F i i i i i ⇒+⇒+⇒+⇒+⇒+⇒+⇒+⇒+⇒⇒⇒⇒⇒+⇒+⇒+⇒+⇒+⇒+⇒+**********()*()*()*()*()*()*()*()语法树：/********************************EE FTE +T F F T +iiiEEFTE-T F F T -iiiE EFT+T F FTiii*i+i+ii-i-ii+i*i*****************/9．证明下面的文法是二义的：S → iSeS|iS|I解：因为iiiiei 有两种最左推导，所以此文法是二义的。

第二章 高级语言及其语法描述4．令+、*和↑代表加，乘和乘幂，按如下的非标准优先级和结合性质的约定，计算1+1*2↑2*1↑2的值：（1） 优先顺序（从高至低）为+，*和↑，同级优先采用左结合。

（2） 优先顺序为↑，+，*，同级优先采用右结合。

解：（1）1+1*2↑2*1↑2=2*2↑1*1↑2=4↑1↑2=4↑2=16 （2）1+1*2↑2*1↑2=1+1*2*1=2*2*1=2*2=46．令文法G6为 N →D|NDD →0|1|2|3|4|5|6|7|8|9 （1） G6 的语言L （G6）是什么？（2） 给出句子0127、34和568的最左推导和最右推导。

解：（1）L （G6）=｛a|a ∈∑+,∑=﹛0,1,2,3,4,5,6,7,8,9｝｝（2）N ＝＞ND ＝＞ NDD ＝＞ NDDD ＝＞ DDDD ＝＞ 0DDD ＝＞ 01DD ＝＞ 012D ＝＞ 0127 N ＝＞ ND ＝＞ N7＝＞ ND7＝＞ N27＝＞ ND27＝＞ N127＝＞ D127＝＞ 0127 N ＝＞ ND ＝＞ DD ＝＞ 3D ＝＞ 34 N ＝＞ ND ＝＞ N4＝＞ D4 ＝＞34N ＝＞ ND ＝＞ NDD ＝＞ DDD ＝＞ 5DD ＝＞ 56D ＝＞ 568 N ＝＞ ND ＝＞ N8＝＞ ND8＝＞ N68＝＞ D68＝＞ 5687．写一个文法，使其语言是奇数集，且每个奇数不以0开头。

解：A →SN, S →+|-|∑, N →D|MDD →1|3|5|7|9, M →MB|1|2|3|4|5|6|7|8|9 B →0|1|2|3|4|5|6|7|8|9 8. 文法：E T E T E T TF T F T F F E i→+-→→|||*|/()| 最左推导:E E T T TF T i T i T F i F F i i F i i i E T T F F F i F i E i E T i T T i F T i i T i i F i i i ⇒+⇒+⇒+⇒+⇒+⇒+⇒+⇒+⇒⇒⇒⇒⇒⇒+⇒+⇒+⇒+⇒+⇒+********()*()*()*()*()*()*()最右推导:E E T E TF E T i E F i E i i T i i F i i i i i E T F T F F F E F E T F E F F E i F T i F F i F i i i i i ⇒+⇒+⇒+⇒+⇒+⇒+⇒+⇒+⇒⇒⇒⇒⇒+⇒+⇒+⇒+⇒+⇒+⇒+**********()*()*()*()*()*()*()*()语法树：/********************************EE FTE +T F F T +iiiEEFTE-T F F T -iiiE EFT+T F FTiii*i+i+ii-i-ii+i*i*****************/9．证明下面的文法是二义的：S → iSeS|iS|I解：因为iiiiei 有两种最左推导，所以此文法是二义的。

作业参考答案第二章 高级语言及其语法描述6、（1）L （G 6）={0,1,2,......,9}+（2）最左推导：N=>ND=>NDD=>NDDD=>DDDD=>0DDD=>01DD=>012D=>0127 N=>ND=>DD=>3D=>34N=>ND=>NDD=>DDD=>5DD=>56D=>568 最右推导：N=>ND =>N7=>ND7=>N27=>ND27=>N127=>D127=>0127 N=>ND=>N4=>D4=>34N=>ND=>N8=>ND8=>N68=>D68=>568 7、Ｇ：S →ABC | AC | CA →1|2|3|4|5|6|7|8|9B →BB|0|1|2|3|4|5|6|7|8|9C →1|3|5|7|98、（1）最左推导：E=>E+T=>T+T=>F+T=>i+T=>i+T*F=>i+F*F=>i+i*F=>i+i*iE=>T=>T*F=>F*F=>i*F=>i*(E)=>i*(E+T)=>i*(T+T)=>i*(F+T)=>i*(i+T)=>i*(i+F)=>i*(i+i) 最右推导：E=>E+T=>E+T*F=>E+T*i=>E+F*i=>E+i*i=>T+i*i=>F+i*i=>i+i*iE=>T=>T*F=>T*(E)=>T*(E+T)=>T*(E+F)=>T*(E+i)=>T*(T+i)=>T*(F+i)=>T*(i+i)=>F*(i+i)=>i*(i+i) (2)9、证明：该文法存在一个句子iiiei 有两棵不同语法分析树，如下所示，因此该文法是二义的。