编译原理期末考试复习整理(详细列出考试重点+重点例题)

词法分析：分析源程序的结构，判断它是否是相应程序设计语言的合法程序

语义法分析 的任务是根据语言的语义规则对语法分析得到的语法结构进行静态的语义检查（确定类型、类型与运算合法性检查、识别含义等），并且转换成另一种内部形式（语义树）表示出来或者直接用目标语言表示出来。

中间代码是一种结构简单、含义明确的记号系统，这种记号系统可以设计为多种多样的形式，重要的设计原则为两点：一是容易生成；二是便于优化、移值；三是容易将它翻译成目标代码

第二章

     文法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

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）

最右推导常被称为规范推导。由规范推导所得的句型称为规范句型。

语法树是对句型的推导给出的一个图形表示

其语法树为：

2-7.解：

aacb是文法G[S]中的句子，相应语法树是：

最右推导：S=>aAcB=>aAcb=>aacb

最左推导：S=>aAcB=>aacB=>aacb

（2）aabacbadcd不是文法G[S]中的句子

因为文法中的句子不可能以非终结符d结尾

（3）aacbccb不是文法G[S]中的句子

可知，aacbccb仅是文法G[S]的一个句型的一部分，而不是一个句子。

（4）aacabcbcccaacdca不是文法G[S]中的句子

因为终结符d后必然要跟终结符a，所以不可能出现…dc…这样的句子。

（5）aacabcbcccaacbca不是文法G[S]中的句子

由（1）可知：aacb可归约为S，由文法的产生式规则可知，终结符c后不可能跟非终结符S，所以不可能出现…caacb…这样的句子。

2-11.解：

(1) S→AB S→c A→bA A→a B→aSb B→c   bbaacb

上面推导中，下划线部分为当前句型的句柄。对应的语法树为：

全部的短语：

第一个a (a1)是句子bbaacb相对于非终结符A (A1) (产生式A?a）的短语（直接短语）；

b1a1是句子bbaacb相对于非终结符A2的短语；

b2b1a1是句子bbaacb相对于非终结符A3的短语；

c是句子bbaacb相对于非终结符S1（产生式S?c）的短语（直接短语）；

a2cb3是句子bbaacb相对于非终结符B的短语；

b2b1a1a2cb3是句子bbaacb相对于非终结符S2的短语；

注：符号的下标是为了描述方便加上去的。

（2）句子（（（b）a（a））（b））的最右推导：

S→（AS）→（A（b））→（（SaA）（b））→（（Sa（a））（b））

→（（（b）a（a））（b））

相应的语法树是：

（3）解：iii*i+↑对应的语法树略。

最右推导：E →→=>F=>FP↑→ FE↑→ FE→+↑→ FEF+↑→ FEP+↑→ FEi+↑

→F→i+↑→ F→F*i+↑→F→P*i+↑→ F→i*i+↑→FFi*i+↑→ FPi*i+↑

→Fii*i+↑→ Pii*i+↑→iii*i+↑

四类文法在描述语法的能力上是依次减弱的.因而有:

第三章

1.给出一个正规文法 (左线性、右线性方法），写出其状态转换图(必考)

1.1右线性文法写出状态转换图 (必考) 

1.2状态转换图写出右线性文法G

对应的右线性文法为：

       S→aB

　　　 B→bC

       C→bC|aF

       F→cF|ε

对应的右线性文法为：

       S→Ab|bC

　　　 B→bC|a

       C→bC|a

1.3左线性文法写出状态转换图 (必考)

例1：文法G（E）为：

       E→Ea|Ba

　　　 B→a|Bb

  画出该文法对应的状态转换图。

例2：(课堂练习)文法G（Z）为：

       Z→U0|V1

　　　 U→Z1|1

       V→Z0|0

画出该文法对应的状态转换图。

2.非确定自动机的确定化

NFA N

第四章

第五章

属性文法与属性翻译文法

文法符号的语义性质称为该文法符号的语义属性（Attributes），简称为属性。

属性文法AG是一个四元组：AG=(G,A,R,B), 其中,G是已简化的CFG; 

   A=∪X∈VA(X)是属性的有限集合;

   R= ∪p∈PR(p)是属性定义规则的有限集;

   B=∪p∈PB(p)是条件的有限集合，B(p)用于描述使规则R(p)有效的条件

属性文法实际上就是对前后文无关文法的一种拓广

逆波兰式（大题）

例1:写出条件语句IF a>0 THEN x:=x+1 ELSE x :=4*(x-1)的逆波兰表示

解:假设BZ表示假(0)转,BR表示无条件转;再假设该条件语句的逆波兰形式的首地址为21,则得该语句的逆波兰表示为:

例2:写出当型语句子  [课堂练习]

WHILE x+y>3 DO

          BEGIN 

            a:=a+3*b; b:=a+e-f*e

          END;   的逆波兰表示.

解: 假设BZ,表示假(0)转,BR表示无条件转,再假设该语句的逆波兰形式的首地址为1,该语句的逆波兰表示为:

四元式（大题）

当op为一元运算符时，对应的四元式为：

         (op,arg1,-,result)

当op为跳转语句时，对应的四元式为：

     (jrop,arg1, arg2 ,地址)

    如：当a>b时跳转到100，表示为：

(j>,a, b ,地址)

无条件转移语句， 对应的四元式为：     

      (j,-,-,地址) 。

例：写出a:=b*c+b*d的四元式表示。

解：四元式如下：

     （*，b,c,t1)

       (*,b,d,t2)

       (+,t1,t2,t3)

       (:=,t3,-,a)

例如，对于条件语句

　　　if A∨B经翻译后，可得四元式序列：

1　　(jnz,A,-,5)

    　2　　(j,- ,-,3)

    　3　　(j<,B,C,5)

    　4　　(j,-,-,p+1)

    　5　　S1相应的四元式序列

    　p　　(j,-,-,q)

    　p+1　S2相应的四元式序列

    　q　    …