编译原理复习提纲2

1.给出语言{a n b n a m b m | n,m≥0}的一个上下文无关文法。

(6分)解：G[S]：S—>ABA—>aAb |εB—>aBb |ε2.给出语言{1 n 0 m 1 m0 n | n,m≥0}的一个上下文无关文法。

解：G[S]：S—>1S0 | AA—>0A1 |ε3.P48 第6题（5）、（6）.画语法树6、已知文法G：<表达式>::=<项>｜<表达式>＋<项><项>::=<因子>｜<项>*<因子><因子>::=（<表达式>）｜i（５）i+(i+i) （６）i+i*i解：(5)语法树：（6）语法树：4.P48第13题直接短语等13、一个上下文无关文法生成句子abbaa的推导树如下：(3)求直接短语解：直接短语有：a ε bP102例题6.1及其分析.( 后加画语法树)例6.1 设文法G[S]为：(1)S—>aAcBe(2)A—>b(3)A—>Ab(4)B—>d对输入串abbcde#进行分析，检查该符号串是否是G[S]的句子。

步骤符号栈输入符号串动作（1）# abbcde# 移进（2）#a bbcde# 移进（3）#ab bcde# 归约（A—>b）（4）#aA bcde#移进（5）#aAb cde# 归约（A—>Ab）（6）#aA cde# 移进（7）#aAc de# 移进（8）#aAcd e# 归约（B—>d）（9）#aAcB e# 移进（10）#aAcBe # 归约（S—>aAcBe）（11）#S # 接受一、计算分析题（60%）1、正规式→ NFA→ DFA→最简DFAP72第1题（1）、（4）；第一题1、构造下列正规式相应的DFA.（1）1(0|1)*101解：先构造NFA0 1S AA A ABAB AC ABAC A ABZABZ AC AB除S，A外，重新命名其他状态，令AB为B、AC为C、ABZ为D，因为D含有Z（NFA的终态），所以0 1S AA A BB C BC A DD C B(4) b((ab)*|bb)*ab解：先构造NFA得到DFA如下所示：P72第4题（a）4、把下图确定化和最小化解：确定化：a b0 01 101 01 11 0、{1}，其中A为初态，A，B为终态，因此有：a bA B CB B CC A最小化：：初始分划得终态组{A,B}，非终态组{C}Π0：{A,B}，{C}，对终态组进行审查，判断A和B是等价的，故这是最后的划分。

a+b=5 a=7 x=5 y=3 b=3 z=7
(4) 所谓传名是在进入调用段之前不对实在参数预先进行计值，而 是过程中每当使用到相应的形参时才对它实行计值。因序),每当过程体中使用到相应 形参时就调用这个子程序。 因此，过程体执行y:=y+1;语句，实现时处理成为： a=a+1; 过程体执行z:=z+x;语句，实现时处理成为： a=a+(a+b); 执行上述两语句后，a的值是 9。因此，程序执行后输出 a的值是 9。 综上所述程序执行时a的输出： (1)传值：2 (2)传地址：8 (3)得结果：7 (4)传名：9 5、几个基本概念 考虑一个有穷字母表∑字符集,其中每一个元素称为一个符号,∑上的
程序是由函数或过程构成的，程序的任务是通过函数或过程之间的 协作（相互调用）l来完成的，函数或过程的调用有以下4种方式：传地 址（call-by-reference）、得结果（call by result）、传值（call-byvalue）和传名（call by name）。 定义函数Swap，其中M、N是形式参数，简称形参。 Void Swap(int M，int N) { int t; t=N; N=M; M=t; } 函数调用： Swap（I,J）；其中I和J是实在参数，简称实参。下面我们以下面的 程序为例分别讨论4种参数传递的方式。
（2）这种类型的数据对象可以具有的值； （3）可以作用于这种类型的数据对象的操作。 一个程序语言必须提供一定的初等数据类型，包括这些数据类型上能 进行的运算的定义。不同的语言含有不同的初等数据成分。常见的初等 数据类型有： （1）数值类型：整型、实型、复数、双精度， 运算：+，-，*，/等 （2）逻辑类型：布尔运算：∨，∧，┑ （3）字符类型：符号处理 （4）指针类型：指针式把内存地址作为其值的数据类型，通过指针可 以操作内存空间。 程序语言中的各种名字都是用标识符表示的。标识符是指由字母、 下划线和数字组成的，以字母或下划线为开头的一个字符串。名字和标 识符在形式上难于区别，标识符是一个没有意义的的字符序列，而名字 则有明确的意义和属性。用计算机术语来说，每个名字可看成是代表一 个抽象的存储单元，这个单元可含有一位、一字节或相继的多个字节。 该单元的内容则被认为是名字的值。仅把名字看成代表一定的存储单元 还是不够的，我们还必须同时指出它的属性（数据类型）。只有指定了 属性的存储单元，其值才是可以理解的。 一个名字的属性包括类型和作用域。名字的类型决定了它能具有什 么样的值， 值在计算机内部的表示方式，以及对它能施加什么运算。 名字的作用域规定了它的值的存在范围。 除了初等数据类型外，有些语言还提供了由初等数据构造复杂数据 的手段。常见的复杂数据类型有： （1）数组。一个数组是由同一类型数据所组成的某种n维矩形结 构。数组在内存中占有一块连续的空间，系统采用基地址加偏移量的方 式来访问数组元素。 （2）记录。从逻辑上讲，记录是由已知的数据组合起来的一种结 构。一个记录通常含有若干个分量，每个分量称为记录的一个栏（或域 field）。每个分量都是一个确定类型的数据，不同的分量的数据类型可 以不同。 （3）字符串、表格、栈和队列。 （4）抽象数据类型。抽象数据类型封装了数据和操作，在面向对象 程序设计语言中，Ada通过程序包（package）提供了数据封装的支持， Smalltalk、C++和Java语言则通过类（class）对抽象数据类型提供支 持。 4、函数调用的方式

编译原理复习范文编译原理是计算机科学中的一门重要课程，它涉及将高级程序代码翻译成低级可执行代码的理论和技术。

下面将对编译原理的基本概念、各个阶段和常见算法进行复习。

1.编译原理的基本概念编译原理研究的是编译程序的设计、实现和理论问题。

编译器是将源程序转换为目标程序的程序，包括编译器前端和后端两个部分。

编译器前端主要完成词法分析、语法分析和语义分析等功能；编译器后端主要完成中间代码生成、代码优化和代码生成等功能。

2.编译原理的各个阶段编译原理的各个阶段包括词法分析、语法分析、语义分析、中间代码生成、代码优化和代码生成。

（1）词法分析：将源代码分解成一个个的单词或记号，例如标识符、关键字、运算符等，生成一个词法单元序列。

（2）语法分析：根据给定的语法规则，将词法单元序列进行分析，构造语法树。

常用的语法分析算法包括递归下降法和LR分析法等。

（3）语义分析：对语法树进行语义检查，包括类型检查、作用域检查等。

在语义分析阶段还可以生成中间代码。

（4）中间代码生成：将源代码转化为一个中间表示，一般是三地址码、四地址码或虚拟机代码。

中间代码是高级语言和机器语言之间的过渡形式。

（5）代码优化：对中间代码进行优化，以改进程序的执行效率。

常用的优化技术包括公共子表达式消除、死代码消除、循环优化等。

（6）代码生成：将优化后的中间代码转化成目标代码。

代码生成的目标可以是汇编语言、机器代码或其他可执行代码。

3.常见的编译原理算法（1）递归下降算法：递归下降算法是一种自顶向下分析的方法，它通过递归地调用与语法规则相对应的子过程来分析输入的源程序。

递归下降算法的实现简单直观，但对左递归和回溯有一定的限制。

（2）LL分析法：LL分析法是自顶向下的一种语法分析方法，它通过查找输入串的前缀和产生式的右部来构造语法树。

LL分析法包括LL(1)和LL(k)两种变体，其中LL(1)分析法是指使用一个符号后看一个输入符号来进行分析。

（3）LR分析法：LR分析法是自底向上的一种语法分析方法，它通过维护一个状态栈和一个符号栈，依据预定义的语法规则进行规约和移进操作来构造语法树。

翻译程序把某一种语言程序(称为源语言程序)等价地转换成另一种语言程序(称为目标语言程序)的程序•编译程序(Complier)将某种高级语言（如FORTRAN、Pascal、C等）程序翻译为对应的低级语言（如汇编语言或机器语言）程序。

要在某一台机器上为某种语言构造一个编译程序，必须掌握下述三方面的内容：1、源语言，对被编译的源语言，要深刻理解其结构（语法）和含义（语义）；2、目标语言，假定目标语言是机器语言，那么，就必须搞清楚硬件的系统结构和操作系统的功能；3、编译方法，把一种语言程序翻译为另一种语言程序方法很多，但必须准确地掌握一二。

0型文法(短语文法，图灵机) ：对文法G，如果它的每个产生式α→β是这样的一种结构：α∈(V N∪V T)* 且至少含有一个非终结符β∈(V N ∪V T)*0型文法相应的语言为0型语言，或称递归可枚举集，它的识别系统是图灵（Turing）机。

如文法G，其中V N={A,B,S} V T={0,1}P={ S→0AB 1B→0B→SA|01 A1→SB1 A0→S0B }1型文法(上下文有关)：它是0型文法的特例，对P中的任一产生式α→β，都|β|≥|α|，仅仅S→ε除外,但S不得出现在任何产生式的右部。

1型文法相应的语言称为1型语言或上下文有关语言，它的识别系统是线性有界自动机。

例文法G[S]：S→aSBE S→aBE EB→BEaB→ab bB→bb bE→be eE→ee❑2型文法（上下文无关文法）：它是1型文法的特例，对任一产生式α→β，都有α∈V N，β∈(V N∪V T)*❑2型文法相应的语言称为2型语言或上下文无关语言。

它的识别系统是下推自动机。

❑例文法G[S]：S→AB A→BS|0 B→SA|1 2型文法产生式的一般形式是: A→β，它表示不管A 的上下文如何都可把A替换成β，因此被称为上下文无关文法。

3型文法(正规文法)：它是2型文法的特例，任一产生式α→β的形式都为A→aB 或A→a，其中A ，B∈V N ，a∈V T这种形式的3型文法也叫右线性文法。