编译原理重点题型简答综合选择填空

乔姆斯基把文法分成4种类型：0型也叫（短语文法）；1型也叫（上下文有关文法）；2型也叫（上下文无关文法）；3型也叫（正则文法）。

自上而下分析方法一般需要消除（左递归）和回溯。 一般而言，编译器的分析部分包括（词法分析），（语法分析），（语义分析）二综合部分包括（中间代码生成），（代码优化），（代码生成）。以上六个阶段都涉及到（符号表）管理和（出错）管理。

任何NFA都存在一个与之等价的（DFA）。

假设G是一个文法，S是文法开始符，若S x,则称x是 文法G产生的的全体是该文法描述的语言。

LL(1)分析法中，第一个L的含义是，第二个L的含义是“1”的含义是 向前看一个符号 。

自下而上语法分析法的基本思想是：从待输入的符号串开始，利用文法的产生式步步向

上进行 归约 ，直至文法的 开始符 。

算符优先分析法定义的可归约串叫做， LR分析中定义的可归约串称为

LR(1)分析法的名字中，“R”指的是 最右推导逆过程 。

高级语言编译程序常用的语法分析方法中，递归下降分析法属于SLR分析法属于 自下而上 分析方法。

LR分析法中，语法分析栈中存放的状态是识别规范句型DFA的状态。 编译过程中，每当扫描器识别出一个新名字，就将它填进 确定的有穷自动机是一个五元组，通常表示为 （S,Σ,δ,s0,F) 。 已知文法G[S]：S→eT|RT

T→DR|ε R→dR|ε D→a|bd

则FIRST(S)= {a,b,d,e, ε} ，FOLLOW(R)= {a,b,#}

在编译过程中：词法分析的常用方法有

自顶向下匹配和自底向上归约 中间代码生成的常用方法有 语法制导翻译方法 ；

一个句型中的最左直接(简单)短语称为该句型的句柄。 短语：假定αβδ是文法G的一个句型，S是文法的开始符，若有： S=*>αAδ且A=+>β ,则称β是句型αβδ相对于非终结符A的短语

直接短语：在短语定义的基础上，若有A=>β，则称β是句型αβδ相对于规则A→β的直接短语

句柄：一个句型的最左直接短语称为该句型的句柄 自上而下分析的主要分析方法： 预测分析法 自下而上语法分析： (2)主要问题：

怎样判断栈顶符号串的可归约性，以及如何进行归约

不同的自下而上分析法主要区别自可归约串的不同定义 (3)主要分析方法：算符优先分析法、LR(k)分析法 三种LR文法的判别方法：

1) LR(0)文法是所有的LR(0)项目集中没有移进－归约冲突或归约－归约冲突(或LR(0)分析表中不含多重定义)

2) SLR(1)文法是LR(0)项目集中所有含冲突的项目集都能用SLR规则解决冲突(或SLR(1)分

析表中不含多重定义)

3) LR(1)文法是所有的LR(1)项目集中没有移进－归约冲突或归约－归约冲突(或LR(1)分析表中不含多重定义)

LR(0)项目集中可能的各种项目： 归约项目、 接受项目、 移进项目、待约项目

1、 语法分析通常采用语法制导翻译方法 2、 语法制导翻译的基本思想是：

文法中的每个符号都有一些编译程序关心的信息，称为文法符号的属性； 为文法中的每个产生式给定一组计算相关属性的动作——语义动作

所谓语法制导翻译，是指在语法规则的制导下，通过计算语义规则，完成对输入符号串的翻译。 3、 属性文法：为每个文法符号引进一组属性，且让该文法中的重写规则附加以语义规则时，称该上下文无关文法为属性文法

4、 文法符号的属性有继承属性和综合属性两种

属性之间存在依赖关系，因而属性的计算有一定的顺序要求

若要一遍扫描完成翻译工作，则必须对文法进行修改，使得在计算每个属性之前，它所依赖的属性已全部计算出来

5、 语义分析通常生成中间代码形式，常见的中间代码有逆波兰、四元式、三元式、三地址代码、抽象语法树等

6、 语法制导翻译法和翻译方案（或称翻译模式）是属性文法的两种不同形式

语法制导翻译法：是在语法分析的过程中，依随分析的过程，在使用语法规则进行推导或归约的同时，根据每个产生式添加的语义动作进行翻译的方法。即：在语法规则的制导下，通过对语义规则的计算，完成对输入符号串的翻译

翻译方案/翻译模式：将属性文法中的语义规则用括号对{}括住，插在规则右部的任何地方，指明语义规则的计算次序，陈述一些实现细节，得到一种语义动作与语法分析交错的表示方法，以表达语义动作在语法分析过程中的执行时刻 1、 编译过程中需要使用源程序中各种名字的相关信息，这些信息通常用一张或几张符号表保存起来。不同的名字需要保存在符号表中的信息各不相同

2、 编译过程中，每当扫描器识别出一个名字后，就查看符号表，看该名字是否在其中。若是一个新名字就将它填进符号表。符号表的信息将在词法分析、语法分析-语义分析过程中陆续填入

3、 符号表在整个编译期间的作用主要有两条： 辅助语义的正确性检查、辅助代码生成 4、 符号表的组织

每一表项包含两个部分：名字栏和信息栏，分别存放标识符的名字和相关属性 可按名字的不同种属使用不同的符号表，如：常量表、变量表、过程名表等等 5、 …… 此处隐藏：3960字，全部文档内容请下载后查看。喜欢就下载吧 ……