编译原理基础试题

《编译原理基础试题》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、一、填空1．源程序中的动态错误时源程序中的逻辑错误，它们发生在程序运行的时候，也被称为（1）错误。动态语义2．设∑={0,1}上的正规集s由倒数第二个字符为0的所有字符串组成，则该正规集对应的正规式表示为（2）。（0

2、1）*0（0

3、1）3.假设G是一个文法，S是文法的开始符号，如果SÞ*x，则称x是该文法的一个（3）。句型4.文法G产生的（4）的全体是该文法描述的语言。句子5.已知文法G：S→aABeA→b

4、AbcB→d该文法的开始符号是（5），终结符号集合VT是（6），非终结符号集合VN是（7）。S，a、b、c、d、e，S、A、B6.在中间

5、代码的三元式表示式中，三元式的编号具有双重含义，既代表（8），又代表（9）。三元式，三元式所存放的结果7.自上而下语法分析的基本思想是：（10）。对任何输入序列，从文法的开始符号开始，进行最左推导，直到得到一个合法的句子或非法结构。8.规约是推导的逆过程，是一个（11）的过程。反复用产生式的左部替换产生式的右部、谋求对输入序列进行匹配9.若文法G构造的移进—规约分析表中不含多重定义的条目，则G为（12）文法。LR（k）10.文法符号的属性有两种，一种称为（13）属性，另一种称为继承属性。综合二、论述1．简述编译器和解释器的区别。P4编译器将源

6、程序的翻译和翻译后程序的运行分成两个独立的不同阶段，而解释器则把翻译和程序的运行结合在一起，翻译一段源程序，紧接着运行它。与编译器相比，解释器有以下两个优点：1.具有较好的动态特性。2.具有较好的可移植性。但是，由于解释器把源程序的翻译和目标程序的运行过程结合在一起，因此，与编译器相比，解释器在时间和空间上的损失较大，运行效率低。2．编译一般包括哪些阶段？简述各阶段的工作与作用（结合例子）。P8编译一般过程：词法分析、语法分析、语义分析、中间代码生成、代码优化、目标代码生成词法分析：词法分析根据词法规则识别出源程序的各个几号（token）语法

7、分析：语法分析根据语法规则识别出记号流中的结构（短语、句子）语义分析：语义分析根据语义规则对语法树中的语法单元进行静态语义检查中间代码生成：根据语义分析器的输出生成中间代码代码优化：使优化后的代码序列在占用的空间上和程序执行的时间上都更节省、更有效。目标代码生成：生成具体机器上可运行的代码。3．简述使用词法分析器构造LEX构造词法分析程序的过程，并写出能识别无符号常数num的LEX程序。P97正规式——NFA——DFA——最少状态DFA——词法分析器或正规式——语法树——DFA——最少状态DFA——词法分析器digit[0-9]digitsd

8、igit+numberdigits(.digits)?%%{number}{yylval.type=REAL;strcpy(yylval.lexeme,yytext);num=atof(yytext);if(num>=0)returnnum;}%%main(){yylex();}4.表达式a+b*c-(d*e)/f，如果优先级由高到低依次为*、/、+、-，且均为左结合，请画出其树形结构，写出其后缀式及四元式。P170、P165、P169三、简答1.有NFA定义如下：N=（S={0，1}，∑={a，b}，s0=0，F={0}，move={mov

9、e(0，a)=0，move(0,a)=1，move(0，b)=1，move(1，a)=0}）（1）画出N的状态转换图；（2）构造N的最小DFAD；（3）给出D所接受语言的正规式描述；（4）举出语言中的三个串，并给出D识别它们的过程。P462.对所给文法S→(L)

10、aL→L,S

11、S对下述语句建立最左推导和最右推导，并给出它们最终的分析树。（1）（a，a）（2）（a，（（a，a），（a，a）））3.文法G如下S→aAbeA→b

12、AbcB→d（1）改写G为等价的LL(1)文法（提示：消除文法中的左递归）（2）求每个非终结符的FIRST集合和FOLL

13、OW集合（3）构造预测分析表。P1374.已知文法G3：S’→EE→aA

14、bBA→cA

15、dB→cB

16、d（1）写出句型bcccB的所有短语、直接短语和句柄；（2）列出4个项目集I1、I2、I3、I4（如下图），请将这4个项目集补充完整。aI1：S’→.EE→.aAE→.bBI2：E→a.AbEI4：E→b.BI3：S'→E.