一、 填空题（每空2分，共30分） B→bc
1、编译程序的整个过程可以从逻辑上划分为词法分析、 语法分析 、语义分析、中间代码生成、 证明该文法具有二义性（本题6分）
证明：因为该文法的句型abc存在如下两棵语法树：
代码优化 和目标代码生成等几个阶段，另外还有两个重要的工 作是 表格管理 和出错处理 2、规范规约中的可归约串是 句柄 ，算符优先分析中的可归约串是 最左素短语 。 3、语法分析方法主要可分为 自顶向下 和 自底向上 两大类。 4、LR（0）文法的项目集中不会出现 移进-归约 冲突和 归约-归约 冲突。 5、数据空间的动态存储分配方式可分为 栈式 和 堆式 两种。 6、编译程序是指能将 源语言 程序翻译成 目标语言 程序的程序。 7、确定有穷自动机DFA是 NFA 的一个特例。
1．编译过程一般分为 词法分析 、 语法分析 、中间代码生成、 代码优化和目标代码生成五个阶段。
3．确定的有穷自动机是一个五元组，通常表示为 DFA=(K ,∑, M, S, Z)。 4．所谓最右推导是指 任何一步都是对中最右非终结符进行替换 5．语法分析器的任务是分析一个文法的句子结
6．如果一个文法的任何产生式的右部都不含有相邻 的非终结符，则这种文法称为算符 文法。
7．进行确定的自上而下语法分析要求语言的文法是无 左递归 和 公
所以，该文法具有二义性
1、简述栈式存储管理策略； 2、何谓DAG； 3、何谓文法的二义性； 四、 给出下述文法对应的正规式 （7分）
S→ 0A| 1B A→1S | 1 B→0S | 0
解：首先得正规式方程组： S=0A+1B A=1S+1 B=0S+0 求解该方程组得：
S=(01|10)(01|10)* （8分）
三．应用题
1）消除下列文法G[A]的左递归。
8．LR分析法是一种 的语法分析方法。 E→E-T∣T；T→T/F∣F；F→( E )∣i
解答：消除文法G[E]的左递归后得到：
9．根据优化对象所涉及的程序范围，代码优化分为 局部优化、循环优化、全局优化
E→TE′；E’→-T E′∣ε；T→FT′；T’→/FT′∣ε；F→( E )∣i
10．常用的优化技术包括： 删除公共子表达式、代码外提、变换循环控制条件、合并已知量、删二、 消除下列文法G[A]的左递归。
A→AaB∣B；B→BbC∣C；C→eD∣D；D→(A)∣d
除无用赋值、强度削弱、复写传播。
解答：消除文法G[A]的左递归后得到：
4、设有文法G[S]：S→b|bB B→bS ，则该文法所描述的语言是 C 。 A →BAˊ；Aˊ→aBAˊ∣ε；B →CBˊ；Bˊ→bcBˊ∣ε；C→eD∣D；D→(A)∣d
2-20.已知文法G[E]为：E→T|E+T|E-T；T→F|T*F|T/F；F→（E）|i A、L（G）={bi|i≥0} B、L（G）={b2i|i≥0}
① 该文法的开始符号（识别符号）是什么？②请给出该文法的终结符号集合VT和非终结符号C、L（G）={b2i+1|i≥0} D、L（G）={b2i+1|i≥1}
集合VN。③ 找出句型T+T*F+i的所有短语、简单短语和句柄。
三、简答题（3小题，共30分） 解：① 该文法的开始符号（识别符号）是E。②该文法的终结符号集合VT={+、-、*、/、（、）、
i}。非终结符号集合VN={E、T、F}。③句型T+T*F+I的短语为i、T*F、第一个T、T+T*F+i。1、已知文法G[S]：S→Ac|aB
简单短语为i、T*F、第一个T;句柄为第一个T。 A→ab
共左因子 的。
- 1 -
相关推荐：
loading