编译原理第三版名词解释和简单

时间:2022-02-10 00:24:40

1.什么是编译程序?

  如果源语言是高级语言,目标语言是诸如汇编语言或机器语言之类的低级语言,那么这样的翻译程序为编译程序。

 

 

编译过程的5个阶段是什么?

  词法分析 语法分析 语义及中间代码生成  代码优化 目标代码生成

 编译原理第三版名词解释和简单

请给出编译程序的结构框图

字母表:元素的非空有穷集和

符号:字母表中的元素称为符号

符号串:符号的有穷序列称为符号串

 

句子:S0步到多步推导出xx属于VT*,则x是该文法的一个句子。句子是一种句型

语言:文法G[S]产生的所有句子的集合称为文法G所定义的语言,记为LG[S]

 

上下文无关文法:若文法G=VN,VT,PS)中的每一条规则形式为A->β,其中AVN,

β∈(VNVT)*,则称为G是上下文无关文法。

 

右线性文法:若文法G=VN,VT,PS)中的每一条规则形式为A->aBA->a,

其中A,BVN,aVT*,则称G是右线性文法。

 

右线性文法:若文法G=VN,VT,PS)中的每一条规则形式为A->BaA->a,

其中A,BVN,aVT*,则称G是左线性文法。

 

 

正规文法:右线性文法和左线性文法都称为正规文法

句柄:一个句型的最左直接短语

规范推导(最右推导):每步推导都坚持替换当前句型最右边的非终结符。

文法二义性:如果一个文法存在某个句子对应两棵不同的语法树(或最左推导或最右推导) 则说这个文法是二义性的。

确定有穷自动机:

一个确定的有限自动机M是一个五元组M =Q,Σ, f, S, Z),其中:

(1)Q是一个有限状态集,它的每一个元素称为一个状态;

(2)(2)Σ是一个有穷输入字母表,它的每一个元素称为一个输入字符;

(3)f是一个从Q×Σ到Q的单值映射,即f (qi , a)=qj且有qiqjQa∈Σ;               (4) SQ,是惟一的一个初态;

(5) ZQ,是一个终态集。

 

非确定有穷自动机: 一个非确定有限自动机M是一个五元组Mn=(Q,Σ,f,S,Z),其中:  

(1) Q、Σ、Z的意义与DFA相同;       

(2) 状态转换函数f不是单值函数,它是一个多值函数。是一个从S×Σ*S的子集映射;       (3) S Q,是一个非空初态集。

 

正规集:正规语言(正规文法描述的语言)的集合

 

正规式:正规集的形式化描述,只能出现“.”连接、“|”或、“*”闭包三种运算。多数程序语言的单词都可用正规文法或正规式来描述。

 

素短语:所谓句型的素短语是指这样的一种短语,它至少包含一个终结符,并且除自身之外,不再包含其他的素短语。

 

规范句型活前缀:

1)字符串的前缀是指字符串的任意首部。如,字符串abc的前缀有空串、aababc。(2)规范句型活前缀是指规范句型的前缀,这种前缀不包含句柄右边的任何符号。

 

LR(0)项目集规范族:构成识别一个文法活前缀的DFA的状态(项目集)的全体。

 

冲突项目:“移进——规约”“规约——规约”冲突

 编译原理第三版名词解释和简单

同心集:所谓同心的LR(1)项目集是指在两个LR(1)项目集中,除搜索符不同之外,核心部分是相同的。

 

什么是属性文法?

  一个属性文法是在上下文无关文法的基础上,允许每个文法符号X(终结符或非 终结符)根据处理的需要,定义与X相关联的属性。  文法符号的属性可分为继承属性与综合属性两类。综合属性用于“自下而上”传递信息,继承属性用于“自上而下”传递信息。

 

语法制导翻译的基本思想是什么?

  文法中的每个符号都有一些编译程序关心的信息,称为文法符号

文法中的每个符号都有一些编译程序关心的信息,称为文法符号的属性;

为文法中的每个产生式给定一组计算相关属性的动作——语义动作   

所谓语法制导翻译,是指在语法规则的制导下,通过计算语义规则,完成对输入符号串的翻译。

为文法中的每个产生式给定一组计算相关属性的动作——语义动作   

所谓语法制导翻译,是指在语法规则的制导下,通过计算语义规则,完成对输入符号串的翻译。

 

什么是代码优化?代码优化通常在什么基础上进行?

  提高代码质量的技术常称为代码优化。根据是否与具体机器有关,分为两类:一 类与机器有关,在目标代码上进行;一类与机器无关,在中间代码上进行。根据优化对象不同,可分为局部优化、循环优化、全局优化。

 

常用的优化技术有哪些?

删除多余运算、复写传播、代码外提、强度削弱,合并已知量。

 

 

目标代码的形式有哪些?

(1)能够立即执行的机器语言代码   (2)待装配的机器语言模块  (3)汇编语 言程序