编译原理总复习摘要.pdf

《编译原理总复习摘要.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、*************************************************************************************总复习*************************************************************************************引论：翻译程序和解释程序编译过程构造一个编译程序需要考虑的三个方面文法和语言：符号和符号串字母表、符号、符号串(字)ε、φ、{ε}的区别符号串的典型运算：连接：设x和y为符号串，则称xy为它们的连接

2、乘积：设A和B是符号串集，则用AB表示A和B的乘积具体定义为：AB={xy

3、x∈A,y∈B}幂：设A为符号串集0定义:A={ε}1A=Ann-1A=AA闭包和正则闭包：+123A=A∪A∪A∪„*0+A=A∪A文法的形式定义非终结符集、终结符集、产生式集、识别符号(开始符号)上下文无关文法一个上下文无关文法G是一个四元式(VT，VN，S，P)，其中：VT是一个非空有限集，它的每个元素称为终结符号；VN是一个非空有限集，它的每个元素称为非终结符号；S是一个非终结符号，称为开始符号；它至少必须在某个产生式的左部出现一次；P是一个产生式的有

4、限集合，它的每个产生式的形式是A→α，其中A∈VN，α∈*(VT∪VN)1文法的分类Chomsky0型、1型、2型、3型文法的定义及区分产生式形如：α→β0型文法：*短语结构文法其中：α,β∈(VN∪VT)，α至少含有一个非终结符1型文法：产生式形如：αAβ→αuβ上下文有关文法其中：A是非终结符，u是非空串，

5、αAβ

6、≤

7、αuβ

8、产生式形如：A→β2型文法：*上下文无关文法其中：A∈VN，β∈(VN∪VT)产生式形如：3型文法：A→a或A→bB（右线性）或A→a或A→Bb（左线性）正规文法*其中：A,B∈VN，a,b∈VT推导与归约直接推导(归

9、约)推导(归约)推导：xy（1步或若干步）星推导：xy当且仅当x=y（0步推导）或xy最左、最右推导最左推导：任何一步α=>β都是对α中的最左非终结符进行替换最右推导：任何一步α=>β都是对α中的最右非终结符进行替换规范(最右)推导和规范(最左)归约句型、句子、语言句型：如果有Zx，Z为文法的开始符，则称x为句型句子：如果有Zx，Z为文法的开始符且x中不包含非终结符语言：所有句子的集合称为语言设G是给定文法，Z是开始符，则由文法G所定义的语言L(G)为：*L(G)={x

10、Zx,x∈VT}短语、直接(简单)短语、句柄短语：假定αβ

11、δ是文法G的一个句型，S是文法的开始符，若有：SαAδ且Aβ则称β是句型αβδ相对于非终结符A的短语直接短语：在短语定义的基础上，若有A=>β，则称β是句型αβδ相对于规则A→β的直接短语句柄：一个句型的最左直接短语称为该句型的句柄2文法的二义性如果一个文法G存在某个句子，这个句子存在两棵语法树（或者说存在两个不同的最．．．．．．．．．．．左（右）推导），则称G为二义性文法排除文法二义性的两个常用方法：在语义上加限制重新构造一个无二义的文法***************************************************

12、**********************************1.写出能构造语言L(G)的文法2m+1m2mm+1L(G)={ab

13、m0}{ab

14、m0}根据语言构造文法的一般方法：①找出语言的若干典型句子②分析句子的特点③根据句子的特点凑规则④得到文法⑤检查文法：语言的所有句子是否都能由文法的开始符号推导出来？由文法开始符号推导出的所有终结符号串都是语言的句子？分析与解答：2m+1m2mm+12mm2mm将ab和ab看成：aab和abb由此构造文法：G[S]：S→aaSb

15、a

16、b********************************

17、*****************************************************2.设有如下文法，请给出句型(F+i)-T*(E-T)的短语、简单短语、句柄G[E]:E→E+T

18、E-T

19、TT→T*F

20、T/F

21、FF→(E)

22、i某句型的短语、直接短语和句柄的简易判断方法：1)构造出该句型的语法树2)该语法树中所有子树的叶子(从左至右)形成短语；3)所有两代子树的叶子(从左至右)形成直接短语；4)最左两代子树的叶子(从左至右)形成句柄；分析与解答：短语：F、i、F+i、(F+i)、E-T、(E-T)、T*(E-T)、(F+i)-T*(

23、E-T)简单短语：F、i、E-T句柄：F3*******************