编译原理作业集
1 第二章 词法分析
1. C或Java语言的标示符是字母和数字组成的序列，第一个字符必须是字母，下划线视为字母，且大小写字母不同。请写出匹配C或Java语言标示符的正规表达式。 2. 为下边所描述的串写正规式，字母表是 {0, 1}. a) 以11 结尾的所有串 b) 只包含一个1的所有串
2 第三章 上下文无关文法
1. ________是描述程序设计语言语法结构的形式工具。 2. 设G=(VN，VT，P，S)是一文法，且 V= VN∪VT，若S =>*α，α∈V，则称α为文法G的 ，若S=>*α，α∈VT，则称α为文法G的 。
3. 给出语言L={ab|j>i>=1}的上下文无关文法。 4. 文法G[S]的产生式如下： S?SaS | SbS | cS | Sd | t 对于输入串 tbctat: (1) 给出一个推导；
(2) 画出(1)中推导对应的分析树；
ij
*
*
(3) 文法G是否是二义性的，请证明你的结论。
3 第四章 语法分析
1. 考虑文法G[S]:
S-> A︱B A->a|b B->(C) C->CS|S 1) 消除上述文法的左递归，重写该文法。
2) 求消除左递归后的文法的非终结符构造First集合和Follow集合。
3) 为消除左递归后的文法构造LL(1)分析表。 4) 并写出对句子 (ab) 的LL(1)分析过程。 2. 给定文法G[S]: S->SaSb︱c
给出句子 cacbacb 的规范推导，画出该句子的语法推导树，指出该句子的句柄。 3. 给定文法G[S]:
S->S b A︱A A->a 1) 造文法G[S]的LR(1)项目的DFA。 2) 上述文法构造LR(1)分析表。 3) 写出句子 ababa的分析过程。
4 第五章 语义分析
1.通过下面文法给出的十进制数的浮点数值，写出一个属性文法(提示：使用一个属性count计算小数点右面数字的个数)。 dnum→num.num num→num digit |digit digit→0|1|2|3|4|5|6|7|8|9
2.考虑下面简单的类Pascal 说明的文法：
? decl →var-list: type
? var- list → var- list, id | id ? type → integer | real ? 写出变量类型的一个属性文法。
3.文法符号的属性有 和 两种。
4.文法符号属性的计算方法有 和 两类。
5 第六章 中间代码生成
1. 根据本章讲解的翻译技术，写出语句（a[i+1]=2)+a[j]相应的三地址码序列：
2.
根据本章讲解的翻译技术，写出语句 while (true) if (false) a[i+1]=2 else x=x-z+3 相应的三地址码序列。
6 第七章 运行时环境
1. 什么是活动记录？请给出C语言活动记录的内容。 2. 设有c语言程序:
main() {
printf(“%d\\n”,f(3)); } f(int x) {
if(x==1) return 1; else
return x*f(x-1); }
试给出运行该程序在返回主函数之前运行栈的活动 记录示意图。
3. 论述C语言函数活动记录中的fp(frame point)（对应于x86系统的bp或ebp寄存器存储的值）指针的作用；
4. 根据C语言运行时内存组织和管理，分析下列程序中存在的问题，并提出改正的方法。