语法树。这棵树具有下列特征： (1)根节点的标记是开始符号S。
(2)每个节点的标记都是V中的一个符号。
(3)若一棵子树的根节点为A，且其所有直接子孙的标记从左向右的排列
次序为A1A2…，那么AA1A2…一定是P中的一条产生式。 (4)若一标记为A的节点至少有一个除它以外的子孙，则?。 (5)若树的所有叶节点上的标记从左到右排列为字符串w，则w是文法G
的句型；若w中仅含终结符号，则w为文法G所产生的句子。 4．(0)分析器
所谓(0)分析，是指从左至右扫描和自底向上的语法分析，且在分析的
每一步，只须根据分析栈当前已移进和归约出的全部文法符号，并至多再
向前查看0个输入符号，就能确定相对于某一产生式左部符号的句柄是否
已在分析栈的顶部形成，从而也就可以确定当前所应采取的分析动作 (是
移进还是按某一产生式进行归约等)。
5．语言和文法
46 / 81
文法就是语言结构的定义和描述，是有穷非空的产生式集合。 文法G定义为四元组的形式：
(，，P，S)
其中： 是非空有穷集合，称为非终结符号集合； 是非空有穷集合，
称为终结符号集合；P是产生式的集合(非空)；S是开始符号(或识别符号)。 这里，∩，?。∪，称为文法G的字母表，它是出现 文法产生式中的一切符号的集合。
文法G所描述的语言用L(G)表示，它由文法G所产生的全部句子组成，即
L(G)={ ST*x，其中S为文法开始符号，且x?VT? } 简单的说，文法描述的语言是该文法一切句子的集合。
四、简答题(共4小题，每小题5分，共20分) 1．编译程序和高级语言有什么区别?
用汇编语言或高级语言编写的程序，必须先送入计算机，经过转换成用机器
语言表示的目标程序（这个过程即编译），才能由计算机执行。执行转换过程
的程序叫编译程序。汇编程序是指没有编译过的汇编语言源文件。编译程序转
47 / 81
换过的叫目标程序，也就是机器语言。
编译程序的工作情况有三种：汇编型、解释型和编译型。汇编型编译程序用来
将汇编语言编写的程序，按照一一对应的关系，转换成用机器语言表示的程序。
解释型编译程序将高级语言程序的一个语句，先解释成为一组机器语言的指令，
然后立即执行，执行完了，取下一组语句解释和执行，如此继续到完成一个程序
止。用解释型编译程序，执行速度很慢，但可以进行人和计算机的\对话\，随时
可以修改高级语言的程序。语言就是解释型高级语言。编译型编译程序将
级语言编写的程序，一次就会部翻译成机器语言表示的程序，而且过程进行很快，
在过程中，不能进行人机对话修改。语言就是编译型高级语言。 2．编译程序的工作分为那几个阶段?
词法分析、语法分析和语义分析是对源程序进行的分析(称为编译程序的前端)，
而中间代码生成、代码优化和代码生成三个阶段合称为对源程序进行综合(称为
编译程序的后端)，它们从源程序的中间表示建立起和源程序等
48 / 81
价的目标程序。
3．简述自下而上的分析方法。
所谓自下而上分析法就是从输入串开始，逐步进行“归约”，直至归约到文法的
开始符号；或者说从语法树的末端开始，步步向上“归约”，直到根节点。
4．简述代码优化的目的和意义。
代码优化是尽量生成“好”的代码的编译阶段。也就是要对程序代码进行
一种等价变换，在保证变换前后代码执行结果相同的前提下，尽量使目
标程序运行时所需要的时间短，同时所占用的存储空间少。
五、综合应用题(共3小题，每小题10分，共30分) 1．证明下述文法G：
S
是二义性文法。 解：
一个文法，如果存在某个句子有不只一棵语法分析树与之对应，那么称这个
文法是二义性文法。
49 / 81
句子有两棵语法树。如下图：
S a S S a S b S a
S d
a
S b
S d
d d
(1) (2)
由此可知，S定义的文法是二义性文法。 2．对于文法G[S]：S，A
，S B求句型的全部短语、直接短语和句柄？
句型的语法树如图五(2)A 所示。 B b
B S
b
a
50 / 81
相关推荐：
loading