编译原理-第二章

第二章高级语言及其语法描述引言：关于形式语言2.1程序语言的定义1、词法规则、语法规则p12-132、语义P142.2高级语言的一般特性P14-25(关于算符的优先顺序p23、名字的左值和右值p24）2.3程序语言的语法描述p252.3程序语言的语法描述一、符号和符号串字母表：字母表Σ是符号元素的非空集合。符号：字母表中的元素。符号串：字母表中的符号所组成的任何有穷序列。例如，若有字母表Σ={a,b}则a，b是字母表Σ中的元素(符号)；a，b，aa，ab，ba…都是符号串。注意：符号串中的符号与顺序有关，ab和ba是不同的符号串特别定义:空符号串——不含任何符号的符号串，用ε表示。设有字母表Σ={a…z,A…Z,0…9,…,各种运算符和其它特殊符号，…}，则，由这些字母表中的元素(符号)可以组成不同的符号串：Programexample;Varsum,I:integer;BeginSum:=0;ForI:=1to10dosum:=sum+I;12345:=sum;End.Write(‘sum=’,sum);A={…}符号串的运算：符号串的连接（联结、乘积）：符号串x和y的连接是指x和y的符号按先后顺序排列在一起组成一个新的符号串，用xy表示。例，若字母表Σ={a,b}，符号串x=ab，y=ba则xy=abba符号串的长度：符号串中符号的个数为符号串的长度。注意:(1)连接运算不满足交换律，即xy≠yx(2)任何符号串x与空串ε的连接都等于x，即：εx=xε=x。若ab是符号串，则|ab|表示符号串的长度。|ab|=2同理：|aabb|=4注意：特别规定|ε|=0。若有两个符号串x=ab,y=cde那么，|xy|=?5符号串的前缀与后缀(头和尾)：若有符号串z=xy(x,y是符号串),我们称x为z的前缀，y为z的后缀。例z=abcd则：z的头有，ε,a,ab,abc,abcdz的尾有，ε,d,cd,bcd,abcd符号串的幂运算：设X是一个符号串，则：X0=ε，X1=X，X2=XX，…，Xn=X…X=Xn例：若有符号串x=ab，则：x0=ε,x1=ab,x2=abab,x3=ababab显然，若n0,则Xn=XXn-1=Xn-1X。即：符号串的幂运算服从结合律符号串集合的运算：符号串集合的乘积运算：设A、B为符号串集合（集合中各元素都是字母表上的字符串），两个字符串集合的乘积定义为：AB={xy|x∈A,y∈B}（笛卡儿乘积）设有字母表Σ={a,b,c,d}，令A={aa,bb}，B={cc,dd}则AB={aacc,aadd,bbcc,bbdd}，BA={ccaa,ccbb,ddaa,ddbb}。显然AB≠BA，即符号串集合乘积不满足交换律。注意：因εx=xε=x故，{ε}A=A{ε}=A特别定义：空符号串集合：{ε}空集合：φ={}Aφ=φA=φ符号串集合的幂运算：设A为符号串集合，则集合的幂运算定义如下:A0={ε}A1=AA2=AA…An=AA……An个=AAn-1=An-1A符号串集合的闭包：设A为符号串集合，则集合的闭包定义如下:A的正闭包：A+=A1∪A2∪…A的闭包：A*=A0∪A1∪A2∪…设集合A={a,b}，则A+={a,b,aa,ab,ba,bb,aaa,…}A*={ε,a,b,aa,ab,ba,bb,aaa,…}显然：A*=A0∪A+A+=AA*二、上下文无关文法(p26)文法(Grammar):是描述语言的语法结构的形式规则（即语法规则）。Thebigmonkeyateabanana.规则：规则又叫产生式(productionrule)，它是语法单位结构的一种表示，它引入了符号“::=”或“→”表示“由……组成”，上述句子的结构可以表示如下：句子→主语谓语主语→冠词形容词名词冠词→the形容词→big谓语→动词直接宾语动词→ate直接宾语→冠词名词冠词→a名词→monkey名词→banana句子的推导：用规则(产生式)按一定方式去推导或产生句子的过程。句子→主语谓语主语→冠词形容词名词冠词→the形容词→big谓语→动词直接宾语动词→ate直接宾语→冠词名词冠词→a名词→monkey名词→banana句子冠词形容词名词谓语The形容词名词谓语Thebig名词谓语Thebigmonkey谓语Thebigmonkey动词直接宾语Thebigmonkeyate直接宾语Thebigmonkeyate冠词名词Thebigmonkeyatea名词Thebigmonkeyateabanana主语谓语句子Thebigmonkeyateabanana语法树(ParseTree):句子结构的图形表示方式句子主语谓语名词形容词冠词直接宾语动词名词冠词monkeybigTheatebananaa归纳：什么是文法句子→主语谓语主语→冠词形容词名词冠词→the形容词→big谓词→动词直接宾语动词→ate直接宾语→冠词名词冠词→a名词→monkey名词→banana三、文法和语言的形式定义定义2文法是一个四元组：G[S]=(VN,VT,P,S)其中：VN为非终结符集合；VT为终结符集合；VN∩VT=Ф，一般令V=VN∪VT，V中的符号称为文法符号；(V字汇表）P为产生式集合；P中的每个产生式写为：α→β或α∷=β。S为开始符号(或称根符号，识别符号)。定义1产生式(或规则)是一有序对(A,α)，通常写为：A→α或A∷=α其中A是一个符号作为产生式左部，α为有穷符号串作为产生式的右部，“→”或“∷=”表示“定义为…”或“由…组成”。另外：G[S]也可简写为G在规则左部出现的符号称为非终结符，它们的全体形成VN在规则中只在右部出现的符号称为终结符，它们的全体形成VT例G1=({N},{0，1},{N→0N,N→1N,N→0,N→1},N）其中:非终结符VN={N}终结符VT={0，1}V={N，0，1}P={N→0N，N→1N，N→0，N→1}开始符号S为N通常情况下，文法只用产生式集合表示：G1[N]:N→0NN→1NN→0N→1定义3符号串的推导与归约：已给文法G=(VN,VT,P,S)，V=VN∪VT，令x,y,α,β∈V*，且α→β∈P，此时，由符号串xαy能够直接产生出符号串xβy，我们称：符号串xβy是符号串xαy的直接推导；符号串xαy是符号串xβy的直接归约；记作:xαyxβy对于上例中文法：G1[N]:N→0NN→1NN→0N→1存在以下直接推导：N1N11εεεεxyxyεxyxyε若有α1，α2，…，αn∈V*且α1α2…，αn-1αn则称αn是α1的推导记作：α1+αn特别约定：若在推导关系α1αn中允许α1=αn，+则称αn是α1的广义推导记作α1*αnN+11N*N引用巴科斯范式(BNF)表示文法：对于具有相同左部的那些产生式，如：U→x,U→y,…,U→z可以缩写为：U→x|y|…|z(“|”可理解为“或”)(1)无符号整数→数字串(2)数字串→数字串数字(3)数字串→数字(4)数字→0(5)数字→1(6)数字→2(7)数字→3(8)数字→4(9)数字→5(10)数字→6(11)数字→7(12)数字→8(13)数字→9(1)无符号整数→数字串(2)数字串→数字串数字|数字(3)数字→0|1|2|3|4|5|6|7|8|9|用此文法和直接推导的定义可以推导出任一无符号整数(56)无符号整数数字串数字串数字数字数字5数字56可表示为:无符号整数+56α∈V*，则称α为文法G的句型α∈VT*，则称α为文法G的句子文法G所对应的语言，记作L(G)={ω|ω∈VT*，且S+ω}例:前面提到的文法G={VN，VT，P，〈无符号整数〉}其中，VT={0，1，2，3，4，5，6，7，8，9}VN={〈无符号整数〉，〈数字串〉，〈数字〉}P：无符号整数→数字串数字串→数字串数字┃数字数字→0┃1┃2┃3┃4┃5┃6┃7┃8┃9无符号整数数字串数字串数字数字数字5数字56试给出该文法的句型、句子举例，并说明它所确定的语言。由此我们可以看出，文法和语言是密切相关的，根据文法可以推导出任一句型和句子，而所有句子的集合则为该文法所对应的语言，即语言是所有句子构成的集合，它是所有终结符号串所组成的集合VT*的子集：L(G)VT*定义4句型和句子:设G=(VN,VT,P,S)是一文法，若S*α那么，句型和句子的区别是什么?定义5规范推导(归约):对于直接推导xαyxβy，如果y只包含终结符号或为空符号串，那么就把这种直接推导称为规范(最右)推导，跟其对应的归约称为规范(最左)归约，且记作：xαyrxβy下面的推导是否规范推导：无符号整数数字串数字串数字数字数字5数字56无符号整数数字串数字串数字数字串6数字656若推导：α1+αn中的每一步直接推导都是规范的，那么我们就把推导：α1+αn称为是规范的，且记作：α1αn+r无符号整数+r56每次对符号串最右非终结符号进行替换例文法G[E]:E→E+E|E*E|(E)|i给出句子i*i+i的最右及最左推导。例2.1p30例2.2例2.3同样，可给出最左推导的定义。p30-31形式语言理论可以证明以下两点：(1)给定一个文法G，就可以从结构上唯一地确定其语言：GL(G)(2)给定一种语言L，能确定其文法，但这种文法可能不是唯一的：LG1或G2例1：有文法G[Z]:(1)Z→aZb(2)Z→ab它确定的语言是什么？用BNF表示：Z→aZb|ab由产生式(2)知：zab故ab是文法的一个句子用产生式(1)(2)：zaZba2b2故a2b2是文法的一个句子反复使用产生式(1)：zaZba2Zb2…an-1Zbn-1anbn所以，文法所确定的语言为：L(G[Z])={anbn|n1}例2：已知语言为L(G)={abna|n1}试给出其文法。G1[Z]:Z→aBaB→bB|bG2[Z]:Z→aBaB→Bb|b定义6等价文法：如果L(G1)=L(G2)，那么称G1和G2为等价文法。定义7递归产生式和递归文法：设给定文法G=(VN,VT,P,S)若x=ε且y≠ε,则称产生式A→α是左递归产生式；若x≠ε且y=ε,则称产生式A→α是右递归产生式。B→BbB→bB(1)若存在产生式A→α∈P且有AαxAy成立，则称产生式A→α是递归产生式；*若α具有xAy形式,则称产生式A→α是直接递归产生式。(2)递归文法：若文法中至少存在一条直接递归产生式则称该文法是直接递归的文法；否则若有A+xAy，或A+Ay，或A+xA则称文法为间接递归的文法。可见，对于文法中任一非终结符号，若能建立一个推导过程，在推导所得的符号串中又出现了该非终结符号本身，则文法是递归的。应当注意，一般的文法都是递归的，文法G只有递归定义，L(G)中句子才是无穷的例：有文法G[S]:S→aB|bBB→a|b是否是递归文法，确定什么语言？非递归文法，L(G[S])={aa,ab,ba,bb}例：有文法G无符号整数(1)无符号整数→数字串(2)数字串→数字串数字|数字(3)数字→0|1|2|3|4|5|6|7|8|9|该文法中有直接左递归产生式：数字串→数字串数字所以是递归文法。它是否为递归文法，确