编译原理简答题.doc

1、简述典型编译程序在各个工作阶段所完成的任务？ 词法分析：对构成源程序的字符串进行扫描和分解，识别出一个个具有独立意义的单词。 语法分析：根据语言的语法规则对单词符号串(符号序列)进行语法分析,识别出各类语法短语(可表示成语法树的语法单位),判断输入串在语法上是否正确 语义分析：按语义规则对语法分析得到的语法单位进行语义分析，审查源程序有无语义错误，为代码生成阶段收集类型信息，并进行类型审查金和违背语言规范的报错处理 中间代码生成：将语义分析得到的源程序变成一种结构简单、含义明确、容易生成、容易翻译成目标代码的内在代码形式 代码优化：对中间代码或目标代码进行变换改造等优化处理，使生成的代码更高效 目标代码生成：将中间代码变换成特定目标机器上的绝对指令代码或可重定向的指令代码或汇编指令代码 2、mian（）{ int x=10，y；} 保留字：main 界符：（、）、{ 保留字：int 标识符：x 运算符：= 常数：10 标识符：y 界符：；、} 3、文法、句型、句子和语言的形式定义？（注意下标） 文法G定义为四元组（VN，VT，P，S） VN ：非终结符（语法实体、变量）集。 VT ：终结符集。 P：规则（α → β）集合，α∈(VN∪VT)*且至少包含一个非终结符，β∈(VN∪VT)* 。 S：开始符（识别符），它是一个非终结符，至少要在一条规则中作为左部出现 设G[S]是一文法，如果符号串x是从文法的识别符号推导出来的，既有Sx，则称x是文法G[S]的句型。若符号串x还满足仅由终结符号组成的条件，既S x（其中x∈VT*）则称x为G[S]的句子。 语言：文法G[S]的语言是G[S]的所有句子构成的集合。即L(G)={x｜Sx，且x∈VT* } 4、确定的有穷自动机(DFA)和不确定的有穷自动机(NFA)的五元组定义？ 确定的有穷自动机(DFA) (1) K是一有穷状态集； (2) S是一有穷字母表，称输入符号字母表； (3) f是转换函数，是在KS′→K上的映射。如f(ki,a)=kj； (4) S是唯一的一个初态（是一个元素）； (5) ZìK，是一终态集，终态也称结束态或可接受态或可识别态。 不确定的有穷自动机(NFA) 1)K是一有穷状态集； (2)S是一有穷字母表，称输入符号字母表； (3)f是转换函数，是在K′S*→K的子集上的映射； (4)S ìK，是非空初态集（是一个集合）； (5)ZìK，是一个终态集，终态也称结束态或可接受态。 5、左素短语的定义和由给定句型寻找最左素短语的方法，并举例说明寻找方法？ 最左素短语：设有文法G[S]，其句型的素短语是一个短语，它至少包含一个终结符，并除自身外不包含其他素短语，最左边的素短语称最左素短语。最左素短语时应该满足的条件：ai-1ai=ai+1=ai+2 … = ajaj+1。例如：在句型AaBbdDefGg中，如果最左素短语为BbdDe，则其中的终结符应满足如下优先关系：a≮b、b≡d≡e和e≯f 6、简述LR(0)、SLR(1)、LR(1)、LALR(1)四类文法的相互关系？ 一个LR(0) 文法肯定是SLR(1)、LR(1)、LALR(1) 文法 一个SLR(1) 文法肯定是LR(1)、LALR(1) 文法，不一定是LR(0) 文法 一个LALR(1) 文法肯定是LR(1) 文法，不一定是LR(0) 文法和SLR(1) 文法 一个LR(1) 文法不一定是LALR(1) 文法，不一定是LR(0) 文法和SLR(1) 文法 7、简述语法制导翻译和属性文法的概念？ 从概念上讲，基于属性文法的语义处理过程即语法制翻译通常是这样的：对单词符号串进行语法分析，构造语法分析树，然后根据需要构造属性依赖图，遍历语法树并在语法树的各结 点处按语义规则进行计算。 一个属性文法是一个三元组A＝（G，V，F）：其中G表示一个上下文无关文法；V表示一个属性的有穷集；F表示关于属性的断言或谓词的有穷集；每个属性与文法的某个非终结符或终结符相联系；谓词与文法规则相联系。 8、简述符号表的3个主要功能？ 符号表的作用和地位：收集符号属性、上下文语义的合法性检查的依据、作为目标代码生成阶段地址分配的依据。 9、简述与通用标识符的存储 位置或格式相关的标识符的主要属性及作用？ 符号表中的标示符一般设置的属性：符号名、符号的类型、符号的存储类别、符号的作用域及可视性、符号变量的存储分配信息、其他属性。 10、分程序结构的语言，为其符号表建立重名动态下推链的目的是什么？概述编译过程中重名动态下推链的工作原理？ 重名动态下推链的目的是保证在合法重名定义情况下，提供完整确切的符号表项，从而保证引用变量的上下文合法性检查和非法重名定义检查。其工作原理：当发生合法重名定义时，