编译原理—第2章前后文无关文法和语言

编译原理—第2章前后文无关文法和语言计算机与软件学院陆克中18098923437,[e-mail]1第2章前后文无关文法和语言2本章讨论与编译实现相关的形式语言理论基本概念，主要内容有：文法及语言的表示文法和语言的定义句型的分析文法的化简和改造文法和语言的Chomsky分类文法与语言一个程序设计语言的确切定义是构造编译程序的重要前提。文法被用来精确而无歧义地描述语言的构成方式。文法描述语言的时候不考虑语言的含义。2.1文法及语言的表示3程序设计语言的定义语言是一个记号系统汉语—符合汉语语法的句子的全体。英语—符合英语语法的句子的全体。程序设计语言—该语言的程序的全体。程序设计语言由语法和语义定义：语法：定义每个程序构成的规则。语义：定义每个程序的意义。2.1文法及语言的表示4程序设计语言的定义语法定义：是一组规则，用它可以形成和产生一个合适的程序。描述工具：文法。作用：定义什么样的符号序列是合法的，与符号的含义无关。语义分类：静态语义：一系列限定规则，确定哪些合乎语法的程序是合适的。动态语义：表明程序要做什么。描述工具：指称语义，操作语义等。作用：检查类型匹配，变量作用域等。2.1文法及语言的表示5文法的直观概念如何来描述一种语言？如果语言是有穷的（只含有有穷多个句子），可以将句子逐一列出来表示。如果语言是无穷的，要找出语言的有穷表示，有两个途经：生成方式（文法）：语言中的每个句子可以用严格定义的规则来构造识别方式（自动机）：用一个过程，当输入的一任意串属于语言时，该过程经有限次计算后就会停止并回答“是”，若不属于，要么能停止并回答“不是”，要么永远继续下去。文法是描述语言的语法结构的形式规则。2.2文法和语言的定义6基本概念和术语形式语言和编译理论中的最基本概念—符号串和符号串集合基本定义它们的运算2.2.1基本概念和术语7字母表定义：元素的非空有穷集合。例：∑={0‚1}，Α={a‚b,c}元素也称为符号，字母表也称符号集。程序语言的字母表由字母数字和若干专用符号组成。2.2.1基本概念和术语8符号串定义：由字母表中的符号组成的任何有穷序列。例：0,00,10是字母表∑={0‚1}上的符号串。a,ab,aaca是Α={a‚b‚c}上的符号串。在符号串中，符号是有顺序的，顺序不同，代表不同的符号串，如：ab和ba不同。不含任何符号的符号串称为空串，用ε表示。注意：{ε}并不等于空集合{}。符号串长度：符号串中含有符号的个数。如：|abc|=3，|ε|=0。约定：常用a,b,c,…及S,T,U,…,X,Y,Z等表示符号；用t,u,…,x,y,z等表示符号串，用A,B,C等给符号串集合命名。2.2.1基本概念和术语9子串设有非空符号串u=xvy，则称v为符号串u的子串。例如：符号串x=a+b*(c+d)，则ε、a、a+b*与(c+d)等都是x的子符号串，且其长度分别为|a|=1、|a+b*|=4、|(c+d)|=5。前缀和后缀如果z=xy是一个符号串，则x是z的前缀，而y是z的后缀。如果y非空，则x是z的真前缀；如果x非空，则y是z的真后缀。例：字母表A={a,b,c}上的符号串x=abc,则x的前缀：ε,a,ab,abc；后缀：ε,c,bc,abc；真前缀：ε,a,ab；真后缀：ε,c,bc。2.2.1基本概念和术语10符号串的运算符号串的连接：设x、y是符号串，它们的连接是把y的符号写在x的符号之后得到的符号串xy。例：x=ST，y=abu，则xy=STabu。显然，εx=xε=x。符号串的方幂：把符号串a自身连接n次得到的符号串an=aa…aa例：a1=a，a2=aa，a0=ε。2.2.1基本概念和术语11符号串集合定义：若集合A中所有元素都是某字母表上的符号串，则称A为字母表上的符号串集合。符号串集合的乘积：符号串集合A和B的乘积定义为：AB={xy|x∈A且y∈B}，即AB是由A中的串x和B中的串y连接而成的串xy组成的集合。例：若集合A=ab,cde，B=0,1，则AB=ab0,ab1,cde0,cde1。显然，{ε}A=A{ε}=A。符号串集合的方幂：设A是符号串的集合，则称Ai为符号串集A的方幂，其中i是非负整数。具体定义如下：A0={ε}A1=A,A2=AAAk=AA......A(k个)2.2.1基本概念和术语12集合的闭包闭包集合Σ的闭包Σ*定义如下：Σ*=Σ0∪Σ1∪Σ2∪Σ3∪…例：设有字母表Σ={0,1}，则Σ*=Σ0∪Σ1∪Σ2∪…={ε,0,1,00,01,10,11,000,…}，即Σ*表示Σ上所有有穷长的串的集合。正闭包Σ+=Σ1∪Σ2∪Σ3∪…称为Σ的正闭包。+表示上的除ε外的所有用穷长串的集合。Σ*=Σ0∪Σ+Σ+=ΣΣ*=Σ*Σ2.2.1基本概念和术语13例题定义标识符是由字母开头、后跟字母或数字的任意组合构成，设A={a,b,…,z}，B={0,1,…,9}，将所有标识符的集合用A和B的运算来表示。2.2.1基本概念和术语14例题定义标识符是由字母开头、后跟字母或数字的任意组合构成，设A={a,b,…,z}，B={0,1,…,9}，将所有标识符的集合用A和B的运算来表示。A(A∪B)*2.2.1基本概念和术语15小结符号与字母表符号串符号串的运算符号串集合集合的闭包字母表的闭包2.2.2文法和语言的形式定义16“我是大学生”是汉语的一个句子用→表示的汉语句子的构成规则：〈句子〉→〈主语〉〈谓语〉〈主语〉→〈代词〉｜〈名词〉〈代词〉→我｜你｜他〈名词〉→王明｜大学生｜工人｜英语〈谓语〉→〈动词〉〈直接宾语〉〈动词〉→是｜学习〈直接宾语〉→〈代词〉｜〈名词〉2.2.2文法和语言的形式定义17句子“我是大学生”的推导过程如下：从句子出发，反复把规则中的→左边的成分替换成右边的成分〈句子〉〈主语〉〈谓语〉〈代词〉〈谓语〉我〈谓语〉我〈动词〉〈直接宾语〉我是〈直接宾语〉我是〈名词〉我是大学生2.2.2文法和语言的形式定义18文法介绍包括四个组成部分：一组终结符号（不能被替换的符号，单词符号）一组非终结符号（能够被替换为终结符号或非终结符号，语法单位）一个开始符号（从这个符号开始替换，最大语法单位—程序）一组产生式（替换规则，把左边的字符串替换为右边的字符串）2.2.2文法和语言的形式定义19关键思路从文法的开始符号出发反复使用产生式，对非终结符进行替换（展开）直到整个字符串中不再包含非终结符这时，得到了这个文法的一个句子（一个程序）这个过程称为推导2.2.2文法和语言的形式定义20文法的形式定义产生式（规则）产生式是一个有序对(α,β)，通常写作α→β（或α::=β）文法定义文法G(Grammar)定义为四元组（VN,VT,P,S）VN(Nonternimal)：非终结符集VT(Terminal)：终结符集P(Production)：产生式（规则）集合S：开始符号或识别符号2.2.2文法和语言的形式定义21文法的形式定义说明V=VN∪VT，V称为文法G的字母表P中产生式形如：α→β，其中α∈VN，β∈V*VN、VT和P是非空有穷集VN∩VT=ΦS是一个非终结符，且至少要在一条产生式的左部出现非终结符代表一个语言中的语法成分，如赋值语句，它是构成程序的一个语法成分，这个符号本身不会在程序中出现，而终结符是组成程序的具体的符号2.2.2文法和语言的形式定义22文法形式定义上的约定文法习惯上只将产生式写出，并有如下约定：第一条产生式的左部是开始符号，或用G[S]表示S是开始符号用尖括号括起的是非终结符，否则为终结符。或者大写字母表示非终结符，小写字母表示终结符G可写成G[S]，S是开始符号希腊字母代表由终结符号和非终结符号组成的符号串α、β、γ左部相同的产生式A→α、A→β可以记为A→α|β，其中“|”是“或”的意思，α、β分别称为侯选式2.2.2文法和语言的形式定义23文法形式定义上的约定例文法G=(VN,VT,P,S)，其中：VN={S}，VT={0,1}，P={S→0S1,S→01}，开始符为SG:S→0S1|01G[S]:S→0S1|012.2.2文法和语言的形式定义24文法形式定义上的约定例文法G=(VN,VT,P,S)，VN={标识符,字母,数字}，VT={a,b,c,…x,y,z,0,1,…,9}，P={标识符→字母,标识符→标识符字母,标识符→标识符数字,字母→a,…,字母→z,数字→0,…,数字→9}，S=标识符G[S]:S→A|SA|SDA→a|b|…|zD→0|1|…|92.2.2文法和语言的形式定义25直接推导和直接归约α→β是文法G的产生式，若有v,w满足：v=γαδ,w=γβδ,其中γ,δ∈V*，则称v直接推导出w，也称w直接归约到v，记作vw直接推导就是用产生式的右部替换产生式的左部的过程直接归约就是用产生式的左部替换产生式的右部的过程例文法G:S→0S1,S→01有直接推导：S0S1（S→0S1）0S100S11（S→0S1）00S11000S111（S→0S1）000S11100001111（S→01）2.2.2文法和语言的形式定义26直接推导序列和广义推导直接推导序列：若存在v=u0u1...un=w,(n0)，则称v+w，v推导出w，或w归约到v（至少有1步推导），这个直接推导序列的长度为n。广义推导：若有v+w或v=w，则记为v*w，v广义推导出w，w广义规约到v（可以包含0步推导）。三种推导的比较直接推导（）的长度为1推导（+）的长度≥1广义推导（*）的长度≥02.2.2文法和语言的形式定义27句型和句子设有文法G[S]，若符号串α是从开始符号推导出来的，即S*α，则称α是文法G的句型。若α仅由终结符组成，即S*α，且α∈VT*，则称α是文法G的句子例文法G[S]:S→0S1,S→01，因为S0S100S11000S11100001111，所以S、0S1、00S11、000S111、00001111都是G的句型，00001111是G的句子语言的定义由文法G生成的语言记为L(G)，它是文法G的一切句子的集合，即L(G)={w|S*w，且w∈VT*}例文法G:S→0S1,S→01，S0S100S1103S13…0n-1S1n-10n1n，L(G)={0n1n|n≥1}2.2.2文法和语言的形式定义28文法和语言的关系文法G生成的每个串都在L(G)中：根据文法，可以通过推导得到该文法相应的语言例G[E]:E→E+T|T,T→T×F|F,F→(E)|a，EE+TT+TF+Ta+Ta+T×Fa+F×Fa+a×Fa+a×a表示一切能用符号a、+、×、(、)构成的算术表达式L(G)中的每个串确实能被G生成：有了语言的要求，也可以为该语言设计文法例若语言由0、1符号串组成，串中0和1的个数相同，构造其文法为：G(A):A→0B|1CB→1|1A|0BBC→0|0A|1CC2.2.2文法和语言的形式定义29推导例题1文法G1：SβA,AαA|α定义了一个什么样的语言？SβAβαSβAβαAβααSβAβαAβααAβααα……SβAβαA…βα…αL(G1)={βαn|n1}L(G1)={以β开头后跟一个或多个α的串}2.2.2文法和语言的形式定义30推导例题2文法G2:SAB,AαA|α,BβB|β，L(G2)={αmβn|m,n1}，文法G2对句子αααββ的推导：SABSABαABAαAααABAαA