川大编译原理复习要点

《川大编译原理复习要点》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、1.编译的各个阶段扫描程序(scanner)在这个阶段编译器实际阅读源程序(通常以字符流的形式表示)。扫描程序执行词法分析(Lexicalanalysis):它将字符序列收集到称作记号(token)的有意义单元中，记号同自然语言，如英语中的字词相似。语法分析程序(parser)语法分析程序从扫描程序中获取记号形式的源代码，并完成定义程序结构的语法分析(syntaxanalysis),这与自然语言中句子的语法分析类似。语法分析定义了程序的结构元素及其关系。通常将语法分析的结果表示为分析树(parsetree)或语法树(syntaxtree)。语义分析程序(s

2、emanticanalyzer)分析程序的静态语义，包括包括声明和类型检查。源代码优化程序(sourcecodeoptimizer),代码生成器(codegenerator)，目标代码优化程序(targetcodeoptimizer)o2.编译器的前端(frontend)，后端(backend)，遍(passes)扫描程序、分析程序和语义分析程序是前端，代码生成器是后端。编译器发现，在生成代码之前多次处理整个源程序很方便。这些重复就是遍(pass)3.编译器，汇编器和解释器之间的区别解释程序是如同编译器的一种语言翻译程序。它与编译器的不同之处在于：它立即执

3、行源程序而不是生成在翻译完成之后才执行的目标代码。汇编程序是用于特定计算机上的汇编语言的翻译程序。有时，编译器会生成汇编语言以作为其目标语言，然后再由一个汇编程序将它翻译成目标代码。4.扫描，分析(语法，词法)的任务扫描的任务是将源程序读作字符文件并将其分为若干个记号扫描程序的任务是从源代码中读取字符并形成由编译器的以后部分(通常是分析程序)处理的逻辑单元。由扫描程序生成的逻辑单元称作记号(token)分析的任务是确定程序的语法，或称作结构分析程序的任务是从由扫描程序产生的记号中确定程序的语法结构，以及或隐式或显式地构造出表示该结构的分析树或语法树5.上下

4、文无关文法，最左推导，BNF，EBNF,乔姆斯基文法层次上下文无关文法说明程序设计语言的语法结构，利用了与正则表达式中极为类似的命名惯例和运算。二者的主要区别在于上下文无关文法的规则是递归的(recursive)最左推导(leftmostderivation)是指它的每一步中最左的非终结符都要被替换的推导最右推导(rightmostderivation)则是指它的每一步中最右的非终结符都要被替换的推导。最左推导和与其相关的分析树的内部节点的前序编号相对应；而最右推导则和后序编号相对应最右推导的一个例子:文法规则：exp-►expopexp(exp)u

5、mberop+

6、-

7、*[exp—>expopexp][exp—>auaiher][op->*][exp->(exp)][exp—>expopexp][exp—>number】[叩一>-][exp—>number](1)exp=>expopexp(2)玲expopaunber(3)=>exp*number(4)=>(exp)*number(5)=>{expopexp)*number(6)=>(expopnumber)*nuab^r(7)=>{exp垂number}*number⑻=>(Aunbez*-number)*nuxabBr图3-1算术表达式（34-3

8、）*42的推导相关题目：3.3EBNF中注意重复和可选的表示方法，语法图1.句子，句型，文法所定义的语言，分析树，抽象语法树2.自顶向下，自底向上语法分析自顶向下（top-down）的分析算法通过在最左推导中描述出各个步骤来分析记号串输入。之所以称这样的算法为自顶向下是由于分析树隐含的编号是一个前序编号，而且其顺序是由根到叶。分为两类：回溯分析程序（backtrackingparser）和预测分析程序（predictiveparser）自底向上的分析程序有两种可能的动作（除“接受”之外）：1）将终结符从输入的开头移进到栈的顶部。2）假设有BNF选择将栈顶部

9、的串a归约为非终结符儿3.为什么要解决公因子，左递归当有公因子存在时，不能立即区分出文法规则右边的选择当有左递归时，将导致一个无限循环。4.写正则表达式，构造NFA，DFA，最小化（按照算法做）构造NFA（使用Thompson结构）：1）基本正则表达式基本正则表达式格式a或£，其中a表示字母表中单个字符的匹配，£表示空串的匹配。与正则表达式a等同的NFA（即在其语言中准确接受）的是：与e等同的NFA是:2）并置我们希望构造一个与正则表达式rA•等同的NFA，其中/•和5都是正则表达式。可将与对应的NFA构造如下：厂>1厂0丄O—-0s-03）在各选项中选择

10、我们希望在与前面相同的假设下构造一个与相对应的NFA。如下进行：4