某级离散数学I试题.doc

《某级离散数学I试题.doc》由会员分享，可在线阅读，更多相关《某级离散数学I试题.doc（4页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、 共 4 页 第 页12012-20132012-2013 学年学年 第第 1 1 学期学期 20102010 级级编译原理编译原理期末考试试题期末考试试题(A(A 卷卷) )考试时间：考试时间：2013 年年 1 月月 7 日日班级班级 学号学号 姓名姓名 请将答案写在答题纸上，写明题号，不必抄题，字迹工整、清晰； 请在答题纸和试题纸上都写上你的班级，学号和姓名，交卷时请将试题纸、答题纸和草纸 一并交上来。 一、填空题（4 小题，共20 分，每题5 分）1. 判断布尔表达式文法GB符号间的优先关系 (、 、或 表示无关系的)。GB: B-BoT|T T-TaF|F F-nF|(B)|t|f则

2、下列符号之间的优先关系为B_#, o_B, n_n, t_a, (_(.2. 设有一个文法GS: S-V V-T|ViT T-F|T+F F-V*|句型F+Fi的短语，简单短语和句柄分别为 _,_,_。3. 设语义分析中当前层数为L，偏移量为off，试写出以下程序点的层数和偏移变化情况。 注意：约定基本类型bool,char,int,float,指针型分别分配1，2，4，8，2 个存储单元。 const int N = 10; typedef struct student char* name; intN2 mark; student a,b; bool ave(student* s, int

3、 n, float x) bool successful; int sum; void main()共 4 页 第 页24. 设一个文法GS： S-S S-BB B-aB B-b其LR(1)活前缀状态机 如下，请填写I3 和I6 状态。依据此状态机构造的LR(1)分析表当中， 相应位置的内容为ACTIONI1,#=_，ACTIONI3,b=_，GOTOI6,B=_。二、计算题（4 小题，每小题5 分，共20 分）1. 求与=a,b的正则表达式(a|b)* (aa*|b*b)(ab)*a等价的最简DFA。2. 将以下文法等价变换为不含空产生式的文法。 GS: S-aAbBc A-a| B-AA|

4、b3. 将如下文法转换为等价的自动机。 GS: S-aA S-bB A-aBc B-bAcSI0：S-.S,# S-.BB,# B-.aB,a/b B-.b,a/bI1：S-S.,#I4：B-b.,a/bI5：S-BB.I7：B-b.,#I2：S-B.B,# B-.aB,# B-.b,#I3：I9：B-aB.,#I8：B-aB.,a/bSbBabbBb BI6：Baaa共 4 页 第 页34. 求与下面NFA 等价的DFA。1a,b bb2435aaabba,b三、简答题（4 小题，每小题5 分，共20 分）1. 设计一个文法G 描述语言aibjcjdiek|i=0,j=1,k=2。2. 请用

5、正则表达式描述下面自动机所接受的语言。1b23aabb4b3. 分析LR 族四种典型分析方法的异同。4. 请给出运行时动态空间的内存存储区划分和 典型过程活动记录 内 容。四、问答题（2 小题，每小题5 分，共10 分）设高级程序设计语言中有Repeat 语句的文法如下： GS: S-RepeatMUntil(E) M-S;M|文法的语义如右图的流程图 所示。1. 请给出Repeat 语句的四元式表示。2. 采用语法制导的方式设计语义函数， 构造Repeat 语句的中间代执行 M判断 E真假共 4 页 第 页4码生成方法。五、问答题（2 小题，每小题5 分，共10 分）1. 以驻留法构造以下程

6、序段的 全局符号表（包括类型表、 标识符表以及表之间的指针） 。2. 比较说明单表结构下的驻留法管理和多表结构下的 scope 栈辅助管理方法的异同。 #include const float E=2.718; typedef struct Lnfloat base; float antilog; void main() float x; Ln X; printf(“Please input the value of x: ”); scanf( X.base=E; X.antilog=power(E,x); printf(“The antilog of the logarithms is : %f”, X.antilog); 六、问答题（2 小题，每小题5 分，共10 分）1. 通过文法等价变换消除 以下文法GS的左递归；2. 判断变换后的文法是否为LL(1)文法。 GS: S-Aa|b A-SB B-ab七、问答题（2 小题，每小题5 分，共10 分）1. 构造如下文法的NFA。 GA： A-B0 B-B0|A1|02. 产生式形为A-a 或A-Ba，A、BVn，aVt 的文法是正则文法， 称为左线性文法 。设计 构造与左线性文法 等价的NFA 算法。