第2章文法和语言的基本知识2.1-2.4

复习补充第一章37用户名/密码:compiler教材编译原理(第3版).刘铭,徐兰芳,骆婷编著.电子工业出版社.1.3编译程序的实现方法设计目标目标程序小，执行速度快。编译程序小，执行速度快。诊断能力强，可靠性强。可移植性，可扩充性。如何实现编译器？直接用可运行的代码编制——太费力！问题一：A机上有一个C语言编译器，是否可利用此编译器实现B机上的C语言编译器？解决：移植方法用C语言写一个B机上的C编译程序(P0:C→B)用A机上的C编译程序(P1:C→A)编译它(P0)，得到可在A机上运行的“B机上的C编译程序”(P2:C→B)在A机上用P2再编译P0，得到可在B机上运行的“B机上的C编译程序”(P3:C→B)Ｔ形图表示语言翻译的Ｔ形图源语言书写语言目标语言编译程序P1）交叉编译(CrossCompiling)条件：Ａ机有Ｃ语言的编译程序目的：实现Ｂ机的Ｃ语言的编译Ｃ语言Ｃ语言Ｂ机器Ｃ语言Ａ机器A机器Ｃ语言A机器Ｂ机器1.(人)用Ｃ语言编制B机的Ｃ编译程序P0(C→B)(Ａ机的C编译程序P1)编译P0，得到在A机上可运行的P2(C→B)P0P1P2交叉编译Ｃ语言Ｃ语言Ｂ机器Ｃ语言Ａ机器Ｂ机器Ｃ语言Ｂ机器Ｂ机器3.(Ａ机的P2)编译P0，得到在B机上可运行的P3(C→B)P0P2P3问题二：A机上有一个C语言编译器，现要实现一个新语言NEW的编译器？能利用交叉编译技术么？问题三：直接在一个机上实现C语言编译器，还有别的技术么？解决：用汇编语言实现一个Ｃ子集的编译程序(P0—人)用汇编程序处理该程序,得到(P2:可直接运行)用Ｃ子集编制Ｃ语言的编译程序(P3—人)用P2编译P3，得到P42)编译程序的自展技术Ｃ子集汇编语言机器语言汇编语言机器语言机器语言Ｃ子集机器语言机器语言1.用汇编语言实现一个Ｃ子集的编译程序(P0—人)2.用汇编程序(P1)处理该程序,得到(P2:可直接运行)P0P1P2编译程序的自展技术Ｃ语言Ｃ子集机器语言Ｃ子集机器语言机器语言Ｃ语言机器语言机器语言3.用Ｃ子集编制Ｃ语言的编译程序(P3—人)4.用P2编译P3，得到P4P3P2P43)利用编译程序自动生成器词法分析器的自动生成程序LEX词法规则说明词法分析程序(C程序)输入： 词法（正规表达式） 识别动作（Ｃ程序段）输出：

yylex()函数语法分析器的自动生成程序ＹＡＣＣ语法规则说明语法分析程序(C程序)输入： 语法规则（产生式） 语义动作（Ｃ程序段）输出：

yyparse()函数编译原理第二章文法和语言的基本知识第2章文法和语言的基本知识2.1.概述2.2.字母表和符号串的基本概念2.3.文法和语言的形式定义2.4.短语、直接短语和句柄2.5.语法树与文法的二义性2.6.文法和语言的分类编译原理第二章文法和语言的基本知识2.1概述语法是对语言结构的定义;语义是描述了语言的含义;语用是从使用的角度去描述语言。例：s=2*3.1416*r*(r+h)的非形式化的描述如下:语法一赋值语句由一个变量、一个后随赋值号“=”、及其后跟一个表达式构成。语义一首先计算语句右部表达式的值,然后把所得结果送入左部变量中。语用一赋值语句可用来计算和保存表达式的值。第二章文法和语言的基本知识编译原理第二章文法和语言的基本知识2.2字母表和符号串的基本概念1、字母表和符号串1)字母表是元素的非空有穷集合。例如:∑={a,b,c}

注意:

字母表中至少包含一个元素;字母表中的元素,可以是字母、数字或其他符号2)符号(字符)

字母表中的元素称为符号,或称为字符。3)符号串(字)

符号的有穷序列称为符号串。例如:上述字母表,则有符号串a,b,ab,ba,cba,abc...

不包含任何符号的符号串,称为空符号串,用ε表示,即空符号串由0个符号组成,其长度|ε|=0编译原理第二章文法和语言的基本知识2、符号串的运算1)符号串的连结例如,设x=abc,y=10a,则xy=abc10ayx=10aabc。注意:对任意一个符号串x,有εx=xε=x2)集合的乘积设A和B是符号串的集合,则A和B的乘积定义为:AB={xy|xЄA,yЄB}例如,设A={a,b},B={c,d},则AB={ac,ad,bc,bd}。对任意集合A,有{ε}A=A{ε}=A,注意ε是符号串,不是集合,而{ε}表示由空符号串ε所组成的集合,但这样的集合不是空集合Ø={}编译原理第二章文法和语言的基本知识3.符号串的幂运算设x是符号串,则x的幕运算定义为

x0=ε,x1=x,x2=xx...xn=xx…x=xxn-1(n>0)4.集合的幂运算设A是符号串的集合,则集合A的幂运算定义为:

A自身的n次（连接）积记为：An=AA…A(n个A)5.集合A的正闭包A+与闭包A*

设A是符号串的集合,则A的正闭包A+和A的闭包A*定义

A+=A1UA2U...UAn...A*=A0UA1UA2U...UAn...={ε}UA+

例如,设A={a,b}则A+={a,b,aa,ab,ba,bb,aaa,aab,...}A*={ε,a,b,aa,ab,ba,bb,aaa,aab,...}编译原理第二章文法和语言的基本知识2.3文法和语言的形式定义1、形式语言序列的集合称为形式语言。（对每个具体语言,都有语法和语义两个方面,形式语言是指不考虑语言的具体意义,即不考虑语义）2形式语言的描述1)当语言为有穷集合时,用枚举方法来表示语言。例如,设有字母表A={a,b,c},则L1={a,b,c}L2={a,aa,ab,ac}L3={c,cc}均表示字母表A上的一个形式语言。例如,设字母表∑={0,1},∑+=∑1U∑2U∑3U…...={0,1,00,10,01,11,000,100…..}无穷集合2)文法来描述无穷集合的语言。用A表示∑+,用式子A→0表示符号串0ЄA或A生成符号串0,符号“→”,读做“生成”,或“由......组成“.则集合A可表示成A→0,A→1,A→A0,A→A12、文法的形式定义(Grammar)1)规则（Production）规则也称产生式,它是一个符号与一个符号串的有序对(A,β)通常写做A→β(或A::=β)A是规则左部它是一个符号,β规则右部它是一个符号串;“→',和“::=',表示“定义为',或“生成",一组规则规定了一个语言的语法结构编译原理第二章文法和语言的基本知识符号分为两类,一类是终结符号,另一类是非终结符号。非终结符号是出现在规则左部能派生出符号或符号串的那些符号,即每个非终结符号表示一定符号串的集合,用大写字母表示或用尖括号把非终结符号括起来。上例中A终结符号是不属于非终结符号的那些符号,它是组成语言的基本符号,是一个语言的不可再分的基本符号,通常用小写字母表示。上例中0,1编译原理第二章文法和语言的基本知识2)文法文法是对语言结构的定义和描述,是规则的非空有穷集合,通常表示成四元组G=(VN,VT,P,S)。

VN是规则中非终结符号的集合。

VT是规则中终结符号的集合。VNnVT=ØVNUVT

称为文法G的字汇表。

P是文法规则的集合。(关键)

S是一个非终结符号,称为文法的开始符号或文法的识别符号(至少在一条规则的左部出现).上例描述的语言序列只可能是由0和1组成的符号串,可用G[A]=({A},{0,1},{A→0,A→1,A→A0,A→A1},A)表示对于若干个左部相同的规则,如A→a1A→a2

………A→an将它们缩写为A→a1|a2|...|an约定:1.对文法G不用四元组显式表示,而只将规则写出.2.第一条规则的左部是文法的开始符号.例:G:A→0|1|A0|A1关于语言文法的构造：一般采用“凑规则”的方法来构造语言的文法（1）找出语言的若干典型句子（2）分析句子的特点（3）根据句子的特点凑规则（4）得到文法（5）检查文法。文法应满足如下两点要求：

a.语言的所有句子都能由文法的开始符号推导得到

b.由文法开始符号推导出的所有终结符号串都是语言的句子编译原理第二章文法和语言的基本知识设字母表∑={a,b};试设计一个文法,描述语言L={a2n,b2n|n>=1}分析：当n=1L={aa,bb}

当n=2L={aaaa,bbbb}

…………..L={aa,bb,aaaa,bbbb,……}定义语言L的文法G=(VN,VT,P,S)VN={A,B,D},VT={a,b}P={A→aa|aaB|bb|bbDB→aa|aaBD→bb|bbD}S=A还可以设计文法G’

=（{A,B,D},{a,b}，P，A）P={A→B|DB→aa|aBaD→bb|bDb}G和G’是等价文法例1：文法G’’

=（{A},{a,b},P,A）P={A→aa|aaA|bb|bbA}X编译原理第二章文法和语言的基本知识试设计一个表示所有标识符的文法。I代表标识符,L代表字母,D代表数字,则定义标识符的文法为,G=(VN,VT,P,S)其中VN={I,L,D}VT={a,b,c,...,x,y,z,0,1,2,...,9}P={I→L|IL|IDL→a|b|c|...|x|y|zD→0|1|2|3|...|9}S=I字母字母数字标识符例2：字母或以字母开头的字母数字串现若将定义标识符的文法设计成G’

=(VN,VT,P,S),P={I→LlIDL→a|b|c|...|x|y|zD→0|1|2|3|...|9}X编译原理第二章文法和语言的基本知识1）直接推导3、语言的形式定义G是一文法,我们从xAy直接推出xay,即xAyxay,仅A→a是G的一个规则且x,yЄ(VNUVT)*.例如,设有文法G[S]=({S},{0,1},P,S)其中,P为S→01|0S1有如下直接推导:S01使用规则S→01,此时x=ε,y=εS0S1,使用规则S→0S1此时x=ε,y=ε0S10011使用规则S→01,此时x=0,y=100S11000S111使用规则S→0S1,此时x=00,y=11编译原理第二章文法和语言的基本知识2)、推导

如果存在一个直接推导序列:ao=〉a1=〉a2=〉..·=〉an则称这个序列是一个从aO至an的长度为n的推导,记为ao

an。表示从ao出发,经一步或若干步或使用若干次规则可推导出an。例如,设有文法G[E]=({E,T,F},{i,+,*,(,)},P,E)其中,P为E→E+T|TT→T*F|FF→(E)|i

对i+i*i有如下直接推导E=〉E+T=〉T+T=〉F+T=〉i+T=〉i+T*F=〉i+F*F=〉i+i*F=〉i+i*i记为Ei+i*i++编译原理第二章文法和语言的基本知识3).广义推导a0

an表示从ao出发,经0步或若干步,可推导出an。对上例,有EEEi+i*i显然,直接推导的长度为1,推导的长度大于等于1,而广义推导的长度大于等于0.4)、句型和句子设有文法G[S]，如果S

x,xЄ(VNUVT)*,则称符号串x为文法G[S]的句型。S

x,xЄVT*,则称x是文法G[S]的句子。例设有文法G[S]:S→01|0S1S

01,s

0S1,S

00S11,s

000111显然,符号串01,0S1,00S11和000111都是文法G[S]的句型,而01和000111又是文法G[S]的句子。*********编译原理第二章文法和语言的基本知识5).语言G[S]产生的所有句子的集合称为文法G所定义的语言,记为L(G[S]):L(G[S])={x|S

x且xЄVT*}由语言定义可知:(1)当文法给定,语言也就确定。(2)L(G)是VT*的子集。即属于VT*的符号串x不一定属于L(G)。例：设有文法G[S]:S→0S|1S|ε

求该文法所定义的语言求该文法所确定的语言为L(G[S])={ε

，0,1，00，01，10，11,……}={x|xЄ{0,1}*}+编译原理第二章文法和语言的基本知识从已知文法确定语言的中心思想：从文法的开始符号出发，反复连续地使用规则，对非终结符施行替换和展开，找出句子的规律，用式子或自然语言描述出来。形式语言理论可以证明如下两点：(1)给定一个文法，就能从结构上唯一确定其语言，即G→L(G)(2)给定一种语言，能确定其文法，但不是唯一的，即L→G1或G2或…或Gn编译原理第二章文法和语言的基本知识4.规范推导和规范归约例如,设有文法G[N1]:N1→NN→ND|DD→0|1|2符号串12是该文法的一个句子,