编译原理总复习

1、2021/3/1712021/3/172选择题（10小题,共20分,每题2分）1.编译程序必须完成的工作有 。词法分析 语法分析语义分析中间代码生成中间代码优化目标代码生成A. B. C. D. 2.下列关于编译和解释的说法,正确的是 。解释方式和编译方式的区别在于解释程序对源程序并没有进行真正翻译。编译方式与解释方式的根本区别在于是否生成目标代码。解释程序和编译程序都是语言处理程序。与编译系统相比，解释系统比较简单，可移植性好，执行速度慢。编译程序是将高级语言程序翻译成汇编语言程序或机器语言程序解释程序是将汇编语言程序翻译成机器语言程序A.B. C. D.CD2021/3/1733. 这样一

2、些语言,它们能被确定有限自动机识别,但不能用正则表达式表示。A存在 B.不存在 C.无法判定是否存在4.已知文法GS:S SaS | SbS | ScS | dSe | f,下列句型中, 是规范句型。AfafbS B.faSbS C.SaSbf. D.faS BCSaSSSbSffSaSSSbSfSaSSS b SSaSSff2021/3/1745.下列文法中不是二义性文法的是 。AS +SS | -SS | aB. S S(S)S | C. S aSbS | bSaS | D. S a | S + S | SS | S* | (S) B.句型句型:( ) ( )(SSS)S(SS)SA(SS

3、S)S(SS)S2021/3/1755.下列文法中不是二义性文法的是 。AS +SS | -SS | aB. S S(S)S | C. S aSbS | bSaS | D. S a | S + S | SS | S* | (S) C.句型句型:ababSSbSaSbSaSSbSaSaSbA2021/3/1765.下列文法中不是二义性文法的是 。AS +SS | -SS | aB. S S(S)S | C. S aSbS | bSaS | D. S a | S + S | SS | S* | (S)D.句型句型:a+a*S + SS S * a a S *SS + SaaA2021/3/1776

4、.后缀表达式ab+c*de*+ 的中缀形式是 。Aa*(b+c)+d*eB(a+b)*c+d*eCa+b*c*d+eDa+b*c+d*e B2021/3/178后缀式后缀式(逆波兰式逆波兰式 )n例例:pos(A*B+C*D)=AB*CD*+n逆波兰式的特点逆波兰式的特点:逆波兰式中的变量的次序与中缀式中的变逆波兰式中的变量的次序与中缀式中的变量的次序完全一致。量的次序完全一致。逆波兰式中无括号。逆波兰式中无括号。逆波兰式中的运算符已按计算顺序排列。逆波兰式中的运算符已按计算顺序排列。2021/3/1797.合并无冲突的合并无冲突的LR（1）状态机得到的）状态机得到的LALR（1）状态机中一定

5、不会出现）状态机中一定不会出现 冲突。冲突。A. 移入移入/移入冲突移入冲突B. 移入移入/归约冲突归约冲突C. 归约归约/归约冲突归约冲突 B2021/3/1710例如例如,假定假定Si、Sj是某一是某一LR(1)状态机的两个状态状态机的两个状态,其中其中,u1、u2、v1、v2、t1、t2分别为归约展望符集分别为归约展望符集 , a VT。 在在Si中有中有: u1 v1=、u1 a=、v1 a=;在在Sj中有中有: u2 v2=、u2 a=、v2 a=。显然显然Si和和Sj是同心状态，合并后得到新状态是同心状态，合并后得到新状态Sij :ABCau1v1t1SiABCau2v2t2SjA

6、BCau1 u2v1 v2 t1 t2Si因因:(u1 u2 ) a=(v1 v2 ) a=所以不可能产生移所以不可能产生移入入归约冲突。归约冲突。因因:(u1 u2 ) (v1 v2 ) =?所以可能产生归约所以可能产生归约归归约冲突。约冲突。2021/3/17118.编译程序使用 区别标识符的作用域。A.声明标识符的过程或函数名B. 声明标识符的过程或函数的静态层数C.声明标识符的过程或函数的动态层数D.标识符的行号 B2021/3/17129.适合采用静态存储分配策略的程序设计语言的限制有适合采用静态存储分配策略的程序设计语言的限制有 。 数据实体所需空间在编译时能确定数据实体所需空间在

7、编译时能确定 过程调用不允许递归过程调用不允许递归 不能动态建立数据实体不能动态建立数据实体 运行时每个数据对象只能有一个实例运行时每个数据对象只能有一个实例 数组的上下界是常量数组的上下界是常量A. B.C. D.10.目标代码生成器的输出可以是目标代码生成器的输出可以是 。绝对机器代码绝对机器代码可重定位机器代码可重定位机器代码汇编代码汇编代码 虚拟机代码虚拟机代码抽象语法树抽象语法树三地址代码三地址代码AB. C. D. AD2021/3/1713二、简答题（5小题小题,共共30分分,每个每个6分）分）1.对于文法对于文法GS:S aAbB A c | AcB d | dB请画出句型请画

8、出句型aAcbdd的语法树的语法树,并求出该句并求出该句型的所有短语、简单短语和句柄。型的所有短语、简单短语和句柄。2021/3/1714定义定义1 1: :由某一结点及其所有分支组成的部分树由某一结点及其所有分支组成的部分树称为原树的一棵子树。称为原树的一棵子树。定义定义2 2: :只有单层分支的子树称为简单子树。只有单层分支的子树称为简单子树。定义定义3 3: :最左简单子树的叶称为句柄。最左简单子树的叶称为句柄。定理：定理： 1.1.每个句型都有一棵语法树每个句型都有一棵语法树, ,每个语法树每个语法树的叶组成该句型。的叶组成该句型。 2.2.每棵子树的叶组成短语每棵子树的叶组成短语,

9、,每棵简单子树每棵简单子树的叶组成简单短语。的叶组成简单短语。 3.3.最左简单子树的叶组成句柄。最左简单子树的叶组成句柄。2021/3/1715GS:S aAbB A c | AcB d | dB 句型句型aAcbddSaAbBAcdBdaAcbddAcddd短语短语:简单短语简单短语:Acd 句柄句柄:Ac2021/3/1716二、二、2.写出类型写出类型Grade07的内部表示的内部表示,其中每个其中每个int、char类型类型数据各占数据各占1个内存单元。个内存单元。typedef struct char name20; int num;student;typedef student

10、Grade07400;2021/3/1717ElemTypeSizeKindSubSizeArrayTyLow Up其中各个域的含义如下其中各个域的含义如下:ZSize表示数组类型所占空间的大小表示数组类型所占空间的大小,是数组所有成分数据是数组所有成分数据占用空间的和占用空间的和,需要通过计算得到需要通过计算得到,Size = (Up-Low+1)*sizeof(ElemType), 其中其中sizeof是一个辅助函数是一个辅助函数，用于计算每种类型的，用于计算每种类型的size;ZKind = arrayTy, 表示是数组类型表示是数组类型;ZLow表示数组下标的下界，在表示数组下标的下界

11、，在C语言中语言中Low = 0;ZUp表示数组下标的上界；表示数组下标的上界；ZElemType 表示数组成分类型的内部表示指针。表示数组成分类型的内部表示指针。 数组类型数组类型: :2021/3/1718FieldListKindSize结构体与共用体类型结构体与共用体类型其中各个域的含义如下其中各个域的含义如下:Size表示该类型数据所占空间的大小表示该类型数据所占空间的大小,结构体是所有域占结构体是所有域占用空间的和用空间的和,共用体类型则是所有域中占用空间的最大者共用体类型则是所有域中占用空间的最大者的值。的值。Kind = structTy, 表示是结构体或共用体类型表示是结构体

12、或共用体类型;FieldList 是域名表的表头指针。是域名表的表头指针。2021/3/1719其中各个域的含义如下其中各个域的含义如下:Name表示标识符的名字表示标识符的名字;Type = TypePtr,TypePtr是域名标识符类型的内部表是域名标识符类型的内部表示指针示指针;Off表示域名标识符相对于记录类型分配的内存块起始表示域名标识符相对于记录类型分配的内存块起始地址的偏移量地址的偏移量,对于联合类型而言对于联合类型而言,所有的域名标识符的起所有的域名标识符的起始偏移都是相同的，所以可以省略始偏移都是相同的，所以可以省略;OffTypeName域名标识符的内部表示如下域名标识符的

13、内部表示如下: 结构体与共用体类型结构体与共用体类型-域名表域名表2021/3/1720charPtr 20 ArrayTy 019typedef struct char name20; int num;student;typedef student Grade07400;structTy0name20intPtrnum ArrayTy03998400212021/3/1721二、3. 请给出下面文法GA的LL(1)分析表。A aABe 1 | Bc 2B dB 3 | 42021/3/1722vFirst集集 First( ) = a VT | * a. (if * then else )

14、vFollow集集 Follow(A) = a VT | S+ .Aa. (if S*.A then # # else )vPredict集集(Select集集) Predict(A ) First( ) 当当 First( ) = First( )- Follow(A) 当当 First( ) 2021/3/1723v 若若X VT : First(X)=Xv若若X VN : 对每一个产生式进行如下处理对每一个产生式进行如下处理:uStep1.形如形如: X , 则则: First(X)uStep2.形如形如:X a , a VT则则 : a First(X)2021/3/1724uStep

15、3.对对每一个形如下的产生式每一个形如下的产生式: XY1Y2Yi-1YiYn若若:Y1,Y2, ,Yi VN且且Y1,Y2, ,Yi-1* 则则: First(Y1)- , First(Y2)- , , First(Yi-1)- , First(Yi)都包含在都包含在First(X)中。中。若若: Yi VN且且Yi * (i=1,2,n), 则则: First(Y1) , First(Y2), , First(Yn) 都包含在都包含在First(X)中。中。重复重复Step3 ,直至对所有直至对所有A VN,First(A)收敛为止。收敛为止。2021/3/1725若符号串若符号串 =X1

16、X2Xn,v当当X1,X2, , Xi-1* ,Xi 不能不能 * ,则则: First( )= 1i-1(First(Xj)- ) First(Xi)v若所有若所有Xi 都能都能* ，则则: First( )= 1n First(Xj)2021/3/17261: 对所有对所有A VN 且且 A非非开始符开始符 : 令令Follow(A):= ; 对开始符对开始符 S : 令令Follow(S)= # # ; 2: 若有产生式若有产生式AxBy: 如果如果 First(y) 则则: Follow(B) = Follow(B) (First(y) Follow(A) 否则否则: Follow(B

17、)= Follow(B) First(y) 3: 重复重复2和和3,直至对所有直至对所有A VN,Follow(A)收收 敛为止。敛为止。2021/3/1727lPredict(A ) First( ) ,当当First( )不含不含 = First( )- Follow(A) , ,当当First( )含含2021/3/1728vLL(1)分析表的定义分析表的定义: T T: :V VN N V VT T P P Error Error T(A,t)=AT(A,t)=A 若若t t Predict( APredict( A ) ) T(A,t)=Error T(A,t)=Error 否则否则

18、 其中其中P表示所有产生式的集合。表示所有产生式的集合。2021/3/1729vLL(1)分析表的构造方法分析表的构造方法:对文法的每一个产生式求其对文法的每一个产生式求其predict集集;对文法的每一个产生式对文法的每一个产生式AA 进行如下进行如下处理处理: Predict( APredict( A )= )=（a a1 1,a,a2 2,.,a,.,an n);); 则令则令: : T(A,aT(A,ai i)=A)=A ,i=1,2,3,n ,i=1,2,3,n LL(1)分析表的其它元素为分析表的其它元素为error。2021/3/1730文法GA的LL(1)分析表。A aABe

19、1 | Bc 2B dB 3 | 4 #,d, e,c（1）求每个产生式的）求每个产生式的Predict集集:Predict（ A aABe ）= aPredict（ A Bc ）= d,cPredict（ B dB ）= dPredict（ B ）= c,ee a ,d ,d ,c2021/3/1731每个产生式的每个产生式的Predict集集:Predict（ A aABe 11 ）= aPredict（ A Bc 22 ）= d,cPredict（ B dB 33 ）= dPredict（ B 44 ）= c,eA aABeA BcA BcB dBB B 2021/3/1732二、二、4

20、. 过程活动记录过程活动记录(AR)一般应包含哪些信息一般应包含哪些信息?答答:动态链指针动态链指针;返回地址返回地址;返回值返回值;过程层数过程层数;size;寄存器状态寄存器状态;变量访问环境变量访问环境;形参形参;局部变量局部变量;临时变量临时变量.2021/3/1733二、二、5. 假定当前函数的层数为假定当前函数的层数为L,偏移量是偏移量是off,每个函数的每个函数的局部数据区的起始偏移为局部数据区的起始偏移为InitOff,每个每个int类型数据占类型数据占1个单元。请给出个单元。请给出A至至F位置的层数和偏移量信息。位置的层数和偏移量信息。（L,offL,off）int time

21、 = 100;int time = 100;A Aint fac(int fac(B B int x) int x)C Cif (x0) return -1;if (x0) return -1;if (x = 0)| (x = 1) return 1;if (x = 0)| (x = 1) return 1;else return xelse return x* *fac(x-1);fac(x-1); D Dvoid main()void main()int i = 1;int i = 1;E Ewhile (i=time)while (i=time)fac(i);fac(i);i+;i+;

22、F F2021/3/1734I.I.处理声明部分处理声明部分: :处理前可用的处理前可用的 处理内容处理内容 处理后可用的处理后可用的抽象地址抽象地址 抽象地址抽象地址（, ,offoff） LabelDec LabelDec （, ,offoff） （, ,offoff） ConstDec ConstDec （，offoff）（，offoff） TypeDec TypeDec （，offoff） （，offoff） Var id:T Var id:T （，off+noff+nT T）（，offoff） ProcDec ProcDec （，offoff） （，offoff） FuncDec F

23、uncDec （，offoff）2021/3/1735II.处理完函数首部处理完函数首部:处理前可用的处理前可用的 处理内容处理内容 处理后可用的处理后可用的抽象地址抽象地址 抽象地址抽象地址(,off） Proc p() （+1,off1）(,off） Func f():T （+1，off1）(，off） Proc P() （，off+2）(，off） Func F():T （，off+2）2021/3/1736III. III. 处理形式参数处理形式参数: :( (, ,offoff） Var ID:T Var ID:T （, ,off+1off+1）( (, ,offoff） ID:T

24、ID:T （， off+ noff+ nT T ）IV.IV.处理过程名及左括号之后处理过程名及左括号之后: : ( (，offoff） Proc p( Proc p( （+1+1，offoff0 0）( (，offoff） Func f( Func f( （+1+1，offoff0 0）( (，offoff） Proc P( Proc P( （+1+1，offoff0 0）( (，offoff） Fucn F( Fucn F( （+1+1，offoff0 0）注注: :小写字母的标识符表示实在标识符，大写字母的标识符则表示形参小写字母的标识符表示实在标识符，大写字母的标识符则表示形参标识符。

25、标识符。n nT T 表示类型表示类型T T的长度，的长度，offoff1 1表示处理完形参部分（实在过程表示处理完形参部分（实在过程首部）时的偏移值，首部）时的偏移值，offoff0 0表示形参的开始偏移量。表示形参的开始偏移量。 2021/3/1737（L,offL,off）int time = 100;int time = 100;A Aint fac(int fac(B B int x) int x)C Cif (x0) return -1;if (x0) return -1;if (x = 0)| (x = 1) return 1;if (x = 0)| (x = 1) return

26、 1;else return xelse return x* *fac(x-1);fac(x-1); D Dvoid main()void main()int i = 1;int i = 1;E Ewhile (i=time)while (i+A，则，则称称A是是左递归的左递归的。 对文法中的某个非终极符对文法中的某个非终极符A，若有：，若有：A=+ A ，则，则称称A是是右递归的右递归的。 对文法中的某个非终极符对文法中的某个非终极符A，若有：，若有：A=+ A ，则称则称A是是递归的递归的。2021/3/1757v左递归情形左递归情形,一定使得自顶向下的语法分析分析条一定使得自顶向下的语法

27、分析分析条件不成立。件不成立。 v消除直接左递归的简单情形消除直接左递归的简单情形: A A | 即有即有A=（至少有一个（至少有一个）。可用下面非）。可用下面非直接左递归的产生式定义直接左递归的产生式定义:A AA A | 2021/3/1758（2）去除左递归）去除左递归:A bA 4A aA 5 | 6S aS 1S SAb 2 | 3A Aa | bS aS 1S SAb 2 | 3A bA 4A aA 5 | 62021/3/1759#,bbb,b（3）求每个产生式的）求每个产生式的Predict集集:Predict（S aS）= aPredict（S SAb）= aPredict（

28、S ）= b,#Predict（A bA）= bPredict（A aA）= aPredict（A ）= b S aS 1S SAb 2 | 3A bA 4A aA 5 | 62021/3/1760v递归下降法递归下降法(Recur(Recursive-Descent Parsing)-Descent Parsing) 对对每个非终极符每个非终极符构造相应的一个子程构造相应的一个子程序序( (称为语法分析子程序称为语法分析子程序) ), ,其功能是识别、其功能是识别、分析该分析该非终极符所能推导出的字符串。非终极符所能推导出的字符串。 2021/3/1761一、递归下降法语法分析程序的构造一、

29、递归下降法语法分析程序的构造引进下面两个基本动作引进下面两个基本动作: vReadToken:从输入流把下一个从输入流把下一个TOKEN码码读到变量读到变量token中。中。vMatch(a):检查检查token=a? 若是若是,则执行则执行ReadToken,否则报错并作相应的处理。否则报错并作相应的处理。其中其中a是终极符。是终极符。2021/3/1762v 对每一个非终极符对每一个非终极符A构造构造子程子程: : 当产生式中形如当产生式中形如: A : A 1 1| | 2 2| | | | n n 则按下面的方法编写子程序则按下面的方法编写子程序A A: : procedure A(

30、)procedure A( ) begin begin if token if token Predict(APredict(A1 1) then ) then ( ( 1 1) else) else if token if token Predict(APredict(A2 2) then ) then ( ( 2 2) else) else if token if token Predict(APredict(An) then n) then ( ( n n) else) else err( ) err( ) end end 语法分析主程序语法分析主程序:Begin ReadToken;

31、S ; Match(#) end2021/3/1763终极符产生匹配命令终极符产生匹配命令,而非终极符则产生调用命令。而非终极符则产生调用命令。因为文法递归相应子程序也递归因为文法递归相应子程序也递归,所以称这种方法所以称这种方法为递归子程序方法或递归下降法。为递归子程序方法或递归下降法。其中其中: :令令 i=X0X1X2Xn,则则: ( i) = (X0); (X1); (X2); ; (Xn); 如果如果X V VN N, , (X)= X 如果如果X V VT T, , (X)= Match(X) 如果如果X= , ( ) = skip(空语句空语句)2021/3/1764（4）各个递

32、归子程序如下）各个递归子程序如下:S( ) if (ch = a) match(a); S(); else error( );S( ) if (ch =a) S( );A( );match(b); else if (ch = b or #) ; else error( );A( ) if (ch = b) match(b); A( ); else error( );A( ) if (ch = a) match(a); A( ); else if （ch = b）; else error( );Predict（S aS ）= aPredict（S SAb）= aPredict（S ）= b,#P

33、redict（A bA）= bPredict（A aA）= aPredict（A ）= bmain ( ) ReadToken; S ; Match(#) ;2021/3/1765v五、给出如下程序段的四元式序列五、给出如下程序段的四元式序列:（14分）int time = 100;int fac(int x)if (x0) return -1;if (x = 0) return 1;if (x = 1) return 1;else return x*fac(x-1); void main() int i = 1;while (i=time)fac(i);i+; 2021/3/1766Whil

34、eWhile语句的中间代码结构语句的中间代码结构: : ( WHILE ,-,-,- )( WHILE ,-,-,- ) E E 的中间代码的中间代码( DO ,E.FORM ,-,-)( DO ,E.FORM ,-,-) S S的中间代码的中间代码(ENDWHILE ,-,-,- )(ENDWHILE ,-,-,- )if E then S1 else S2if E then S1 else S2中间代码结构中间代码结构: : E E 的中间代码的中间代码( THEN , E.FORM , , )( THEN , E.FORM , , )S1 S1 的中间代码的中间代码(ELSE , , ,

35、 )(ELSE , , , )S2 S2 的中间代码的中间代码(ENDIF , , , (ENDIF , , , ) ) 2021/3/1767v对应过程对应过程函数声明的中间代码有函数声明的中间代码有: : ( ENTRY , Label ( ENTRY , LabelQ Q , Size , SizeQ Q , Level , LevelQ Q ) ) ( ENDPROC , , , ) ( ENDPROC , , , ) 或或 ( ENDFUNC , , , )( ENDFUNC , , , ) 其中其中: Label: LabelQ Q 是给过程是给过程Q Q分配的代码入口标号分配的代

36、码入口标号; ; SizeSizeQ Q 是过程是过程( (函数函数)Q)Q的的ARAR空间大小空间大小, ,该空间暂时不包该空间暂时不包括临时变量部分括临时变量部分, ,此时此时SizeSizeQ Q实际是临时变量的初始实际是临时变量的初始Offset Offset , ,在代码生成阶段处理完临时变量时才可完全确定在代码生成阶段处理完临时变量时才可完全确定; ; LevelLevelQ Q是过程是过程Q Q的层数的层数; ; ENTRYENTRY和和ENDPROCENDPROC（或（或ENDFUNCENDFUNC）分别表示子程序的入口）分别表示子程序的入口和出口。和出口。2021/3/176

37、8 E E1 1 的中间代码的中间代码.E En n 的中间代码的中间代码( VarACT / ValACT , t( VarACT / ValACT , t1 1 , Offset , Offset1 1 , Size , Size1 1 ) ).(VarACT / ValACT , t(VarACT / ValACT , tn n , Offset , Offsetn n , Size , Sizen n) )(CALL , (CALL , Labelf , true/false , , true/false , Result ) Result )2021/3/1769（ASSIG, 10

38、0, 1, time）（Entry, Lfac, , 0）（LT, x, 0, t1）（THEN, t1,_,_）（RETURN, _, _, -1）（ENDIF, _, _, _）（EQ, x, 0, t2）（THEN, t2, _, _）（RETURN, _, _, 1）（ENDIF, _, _, _）（EQ, x, 1, t3）（THEN, t3, -,-）（RETURN, _, _, 1）（ ELSE, _, _, _）int time = 100;int fac(int x)if (x0) return -1;if (x = 0) return 1;if (x = 1) return

39、 1;else return x*fac(x-1); （SUBI, x, 1, t4）（ValAct, t4, initoff, 1）（CALL, Lfac,true,t5）（MULTI, x, t5, t6）（RETURN, _, _, t6）（ENDIF, _, _, _）（ENDFUNC, _, _, _） InitOff+7或设第一个形参的区距为或设第一个形参的区距为IntOff。设每个函数的局部数据区的起始偏移为设每个函数的局部数据区的起始偏移为InitOff。2021/3/1770void main() int i = 1;while (i=time)fac(i);i+; （Ent

40、ry, Lmain, , 0）（ASSIG, 1, 1, i）（WHILE, _, _, _）（LE, i, time, t1）（DO, t1, _, _）（VALACT,i,initoff,1 ）（Call, Lfac, true, t2）（ADDI, i, 1, t3）（ASSIG, t3, 1, i）（ENDWHILE, _, _, _）（ENDFUNC, _, _, _）InitOff+42021/3/1771六、判断下面文法是否是六、判断下面文法是否是LR（1）文法）文法,并说明并说明理由。（理由。（12分）分）S Aa | bAc | Bc | bBaA dB d2021/3/1772vLR(1)LR(1)项目项目: :AA, a , a 。LR(0)LR(0)项目及一个项目及一个V VT T #的展望符的展望符。vIS:IS:LR(1)LR(1)项目集项目集vISIS(X)(X): : IS IS(X)(X) = A = A X X,a | A,a | AX X ,a,a IS IS 2021/3/1773v