发布时间 : 星期三 文章编译原理期末考试复习整理(详细列出考试重点+重点例题)更新完毕开始阅读72bc7437e109581b6bd97f19227916888586b988
.
目录
第一章 ....................................................................................................................................... 2
词法分析： ....................................................................................................................... 2 语义法分析 ....................................................................................................................... 2 中间代码 ........................................................................................................................... 2 第二章 ....................................................................................................................................... 2 1.根据语言写出文法 ............................................................................................................ 2 2.根据文法写语，描述其特点(必考大题2-3类型) .......................................................... 3 3.文法的规范推导、语法树、短语、句柄（必考大题，2-7，2-11） ............................ 4 第三章 ..................................................................................................................................... 10 1.给出一个正规文法 (左线性、右线性方法），写出其状态转换图(必考) ................ 10 1.1右线性文法写出状态转换图 (必考)....................................................................... 10 1.2状态转换图写出右线性文法G ............................................................................... 11 1.3左线性文法写出状态转换图 (必考)....................................................................... 12 2.非确定自动机的确定化 .................................................................................................. 13 第四章 ..................................................................................................................................... 14 第五章 ..................................................................................................................................... 14 属性文法与属性翻译文法 ................................................................................................. 14 逆波兰式（大题） ............................................................................................................. 14 四元式（大题） ................................................................................................................. 15
.
.
第一章
词法分析：分析源程序的结构，判断它是否是相应程序设计语言的合法程序 语义法分析 的任务是根据语言的语义规则对语法分析得到的语法结构进行
静态的语义检查（确定类型、类型与运算合法性检查、识别含义等），并且转换成另一种内部形式（语义树）表示出来或者直接用目标语言表示出来。
中间代码是一种结构简单、含义明确的记号系统，这种记号系统可以设计为
多种多样的形式，重要的设计原则为两点：一是容易生成；二是便于优化、移值；三是容易将它翻译成目标代码
第二章
文法G定义为四元组(VN，V→，P，S )其中VN为非终结符号(或语法实体，或变量)集；V→为终结符号集；P为产生式(也称规则)的集合； VN，V→和P是非空有穷集。 S称作识别符号或开始符号，它是一个非终结符，至少要在一条产生式中作为左部出现。 VN和V→不含公共的元素，即VN ∩ V→ = φ,通常用V表示VN∪ V→ ，V称为文法G的字母表或字汇表。
一个文法的有如下几种写法
① G=({S,A}，{a,b}，P，S) 其中P：S→aAb A→ab A→aAb A→ε ② G：S→aAb A→ab A→aAb A→ε
③ G[S]： A→ab A→aAb A→ε S →aAb ④ G[S]： A→ab |aAb |ε S→aAb
1.根据语言写出文法
2.构造产生下列语言的文法
（1）{ an bn |n≥0}
.
.
解：对应文法为G(S) = ({S},{a,b},{ S→ε| aSb },S) （2）{anbmcp|n,m,p≥0}
解：对应文法为G(S) = ({S,X,Y},{a,b,c},{S→aS|X,X→bX|Y,Y→cY|ε},S)
（3）{an#bn,|n≥0}∪{cn#dn |n≥0 }
解：对应文法为G(S) = ({S,X,Y},{a,b,c,d,#}, {S→X, S→Y,X→aXb|#,Y→cYd|# },S)或者 G[S]： S→X|Y X→aXb|# Y→cYd|#
（4）{w#wr# | w?{0,1}*,wr是w的逆序排列}
解：G(S) = ({S,W,R},{0,1,#}, {S→W#, W→0W0|1W1|# },S) （5）任何不是以0打头的所有奇整数所组成的集合
解：G(S) = ({S,A,B,I,J},{-,0,1,2,3,4,5,6,7,8,9},{S→J|IBJ,B→0B|IB|e, I→J|2|4|6|8, Jà1|3|5|7|9},S)
（6）所有偶数个0和偶数个1所组成的符号串集合
解：对应文法为 S→0A|1B|e，A→0S|1C B→0C|1S C→1A|0B
2.根据文法写语，描述其特点(必考大题2-3类型)
例3 写出文法G：
(1) S→aSBE（2) S→aBE (3) EB→BE (4) aB→ab (5) bB→bb (6) bE→be
(7) eE→ee 所产生的语言。
S =>aSBE =>aaSBEBE => aaaBEBEBE=>aaaBBEEBE=>aaaBBEBEE aaaBBBEEE =>aaabBBEEE =>aaabbBEEE =>aaabbbEEE =>aaabbbeEE aaabbbeeE=>aaabbbeee ，即 a3b3e3
.
.
2-3.描述语言特点
（1）S→10S0 S→aA A→bA A→a
解：本文法构成的语言集为：L(G)={(10)nabma0n|n, m≥0}。 （2）S→SS S→1A0A→1A0A→ε
解：L(G)={1n10n11n20n2 … 1nm0nm |n1,n2,…,nm≥0；且n1,n2,…nm不全为零}该语言特点是：产生的句子中，0、1个数相同，并且若干相接的1后必然紧接数量相同连续的0。
（3）S→1AS→B0A→1AA→CB→B0B→CC→1C0C→ε
解：本文法构成的语言集为：L(G)={1p1n0n|p≥1,n≥0}∪{1n0n0q|q≥1,n≥0}，特点是具有1p1n0n 或1n0n0q形式，进一步，可知其具有形式1n0mn,m≥0,且n+m>0。
（4）S→bAdcA→AGSG→εA→a 解：可知，S=>…=>baSndc n≥0
该语言特点是：产生的句子中，是以ba开头dc结尾的串,且ba、dc个数相同。
（5）S→aSS S→a
解：L(G)={a(2n-1)|n≥1}可知：奇数个a
3.文法的规范推导、语法树、短语、句柄（必考大题，2-7，2-11）
最右推导常被称为规范推导。由规范推导所得的句型称为规范句型。 语法树是对句型的推导给出的一个图形表示
.