第2章 前后文无关文法和语言

[e-mail]编译原理第二章前后文无关文法和语言本章目的为语言的语法描述寻求工具掌握对源程序给出精确无二义（严谨、简洁、易读）的语法描述手段之一---文法熟练使用文法定义程序设计语言的单词和语法成分对形式语言的理论有一个初步基础问题的提出如何描述定义一种语言？如何识别&分析之？用一组数学规则来描述语言的方式：形式描述形式语言本章内容文法和语言的表示文法和语言的定义句型的分析文法的化简和改造文法和语言的Chomsky分类2.1文法和语言的表示“Whatislanguage?”语言是由句子组成的集合，是由一组符号所构成的集合。语言的表示方法：枚举句子制定有限的规则建立一种装置（自动机），以检验/识别句子符号串2.2文法和语言的定义基本概念和术语文法和语言2.2.1基本概念和术语（一）符号：可以相互区别的记号（元素）。字母表：符号（元素）的非空有穷集合。符号串：由字母表中的符号组成的任何有穷序列称为该字母表上的符号串。定义：1.空符号串ε(没有符号的符号串)是上的符号串2.若x是上的符号串，a是的元素,则xa是上的符号串3.y是上的符号串，当且仅当它可以由1和2导出区分ε，{ε}和2.2.1基本概念和术语（二）前缀：移走符号串s尾部的零个或多于零个符号得到的符号串真前缀后缀：删去符号串s头部的零个或多于零个符号得到的符号串真后缀子串：从s中删去一个前缀和一个后缀得到的符号串2.2.1基本概念和术语（三）符号串的长度：符号串中符号的个数.符号串s的长度记为|s|。ε的长度为0连接：符号串x、y的连接,是把y的符号写在x的符号之后得到的符号串xy方幂：符号串自身连接n次得到的符号串an定义为aa…aan个aa1=a,a2=aa则a0=ε符号串集合：若集合A中所有元素都是某字母表上的符号串，则称A为字母表上的符号串集合。2.2.1基本概念和术语（四）两个符号串集合A和B的乘积定义为AB=xy|xA且yB使用*表示上的一切符号串（包括ε）组成的集合。Σ*称为Σ的闭包。上的除ε外的所有符号串组成的集合记为+。Σ+称为Σ的正闭包。......}{2*......}{32**2.2.2文法和语言产生语言有限个规则全部句子语言是由句子组成的集合，是由一组符号所构成的集合。换言之,字母表上的一个语言是上的一些符号串的集合(字母表上的每个语言是*的一个子集)产生句子——推导〈句子〉∷=〈主语〉〈谓语〉〈主语〉∷=〈代词〉｜〈名词〉〈代词〉∷=我｜你｜他〈名词〉∷=王明｜大学生｜工人｜英语〈谓语〉∷=〈动词〉〈直接宾语〉〈动词〉∷=是｜学习〈直接宾语〉∷=〈代词〉｜〈名词〉王明是大学生推导过程〈句子〉〈名词〉〈谓语〉王明〈谓语〉王明〈动词〉〈直接宾语〉王明是〈直接宾语〉王明是〈名词〉王明是大学生各个概念非终结符（VN）终结符（VT）开始符（S）规则集（P）规则：有序对（U，u）Uu左部变量右部符号串产生式文法定义2.1文法G=（VN，VT，S，P）V=VN∪VT，V：字汇表（词汇表）VN∩VT=φ直接推导定义2.2直接推导β是α的直接推导：文法G=(VT,VN,S,P)α=U，β=，，∈(VT∪VN)*如果存在产生式U→则称U可直接推出即：U，或者：αβGG推导定义2.3推导β是α的推导：α=βα=v0v1v2…vn=β，n1+n0：v0vn；n1：v0vn句型、句子定义2.4句型，句子S，V*，则是句型S，VT*，则是句子语言定义2.5语言由文法G生成的语言记为L(G),它是文法G的一切句子的集合:L(G)={x|S=x，其中S为文法的开始符号，且x∈VT*}*例：G：S→0S1，S→aL(G)={0na1n|n≥0}递归定义2.6若AA，且和不同时为，则为直接递归。•为，则为左递归。若AA，则A是递归的*语言无限的前提条件是：文法是递归的当语言是无限集时，能否用有限的规则来描述呢？递归例子文法G2[E]：EE+T|TTT*F|FF(E)|i直接递归，间接递归语言等价文法与语言之间无一一对应的关系定义2.7若L(G1)=L(G2)，则称文法G1和G2是等价的A-产生式左部变量为A的产生式引理2.1：G=(VN,VT,P,S),ABP,B1,B2,,Bk是P中的全部B-产生式,G1=(VN,VT,P1,S),P1是由P中去除AB添加A1,A2,,Ak组成的，则L(G)=L(G1)。一些练习E→E+E∣E*E∣(E)│i，推导出：i+i*i试构造产生标识符的文法2.3句型的分析内容：规范推导和规范归约语法树和二义性短语和句柄句型的分析：构造一算法，用以判断所给的符号串是否为某文法的句型（句子）常见分析方法有自顶向下分析和自底向上分析两类2.3.1规范推导和规范归约推导过程可能不唯一例：文法G2[E]：EE+T|TTT*F|FF(E)|i最左推导最右推导规范推导从符号串到符号串的推导序列*xUyxuy*总有xVT*(yVT*)时，称为最左（右）推导定义：最左（右）推导所得句型称为左（右）句型；最右推导称为规范推导；右句型称为规范句型。并不是每个句型都有最左和最右推导推导过程可能是带回溯的规范归约若归约的每一步都归约的是当前符号串中最左边的某产生式的右部，则称该归约是规范归约（即最左归约）。规范归约是规范推导的逆过程例：符号串i+i*i的归约过程EE+T|TTT*F|FF(E)|i问题：如何确定当前符号串中可被归约的最左子串？习题试构造一个2型文法G，使得L(G)={a2mbm∣m≥0}2.3.2语法树和二义性树有且仅有一个无任何前驱的结点，称为根（S）除根外，每个结点恰有一个直接前驱对于任一结点m，从根到m可达每个结点的后继是有序的（从左到右）语法树每个结点有一标记X，XV根的标记为S（开始符）若结点X有后继，则XVNA有k个后继，自左至右为X1,X2,…,Xk，则AX1X2…XkP二义性存在某个句子具有两棵不同的语法树例：G[E]：EE+E|EE|(E)|i的句子i+ii例：if-then-else二义性文法是有害的措施：修改文法利用附加条件2.3.3短语和句柄)()(),(:,,,,][8.2**直接短语的短语产生式相对于非终结符是句型则称及有对于若其中的一个句型是文法设定义AAAAASVAVVSGNEE(1)+T(1)E(2)+T(2)T(3)*F(3)F(1)i例如：句型=E+T*F+i短语，直接短语，最左直接短语句柄定义2.9一个句型的最左直接短语称为此句型的句柄问题：如何确定一规范句型的句柄？句柄应被归约成哪个非终结符？习题请证实G(S)：S→SaS∣SbS∣cSd∣eS∣f是一个二义文法2.4文法的化简和改造无用符号和无用产生式的删除-产生式的消除单产生式的消除无用符号和无用产生式的删除设G=(VN,VT,P,S)是一文法,XVN∪VT,X称为是有用的,若X至少出现在一个句子的推导过程中,即X满足:(1)存在,V*,有S*X(2)存在wVT*,使X*w否则,称X是无用的。若一产生式含有无用符号,则此产生式称为无用产生式.消除无用产生式（1）算法2.1将文法G=(VN,VT,P,S)，改造为G1=(V’N,VT,P’,S)，使得对于每个XV’N，存在wVT*，满足X*w。(1)置V’N，P’为空(2)对于P中每个产生式A，若(V’N∪VT)*，则将A加入V’N中(3)重复(2)，直到V’N不再增大(4)对于每个AP，若(V’N∪VT)*，则置A于P’中消除无用产生式（2）算法2.2任给文法G=(VN,VT,P,S)，构造G’=(V’N,V’T,P’,S’)，使x(V’N∪V’T)，,(V’N∪V’T)*，有S*x(1)置V’T为空，V’N={S}(2)对于AP，若AV’N则置中所有非终结符入V’N，所有终结符入V’T(3)重复(2)，直到V’不再增大(4)令P’={A|AP,(V’N∪V’T)*,AV’N}消除无用产生式例例：文法G=({S,U,V,W},{a,b,c},P,S)，其中P:SaS|W|UUaVbV|acWaW-产生式的消除（1）先判断文法是否会产生空串算法2.3任给文法G=(VN,VT,P,S)(1)作集合W1={A|产生式AP}(2)作集合序列WK+1=WK∪{B|产生式BP，且WK+}(3)重复(2)，直到W不再增大可以用来判断一个文法会不会产生空符号串-产生式的消除（2）算法2.4(1)按算法2.3将VN分成两个不相交的集合：W及VN-W(2)设AX1X2…Xm是P中的任一产生式，按下面的规则将所有形如AY1Y2…Ym的产生式放入P’中对于一切1im：（i）若XiW，则取Yi=Xi（ii）若XiW，则分别取Yi为Xi和，将AX1X2…Xi-1XiXi+1…Xm和AX1X2…Xi-1Xi+1…Xm加入P’-产生式的消除（例1）例：文法G=({S,A,B,C},{a,b,c},P,S)，其中P:SaAABCBbB|CcC|-产生式的消除（例2）例：文法G=({S,A,B},{a,b,c},P,S)，其中P:ScS|ABAaAb|BBb|问题：S也能推出。解决单产生式的消除例：文法G=({S,A,B},{a,b},P,S)，其中P:SAB|A|BAaAb|abBBb|b2.5文法和语言的Chomsky分类四类文法和语言0型文法:若P中任一产生式都有一般形式V+V*且对，不加任何限制，则称G为0型文法（短语结构文法，记为PSG:PhraseStructureGrammar）。由0型文法生成（或者说：定义）的语言称为0型（递归可枚举）语言。它可由图灵（Turing）机识别。1型文法和语言若一0型文法所有产生式具有形式1A212其中，1,2V*V+AVN,则称G为1型(前后文有关)文法，记为CSG(ContextSensitiveGrammar)。1型文法产生的语言称为前后文有关语言CSL，它可由线性限界自动机识别2型文法和语言若一1型文法G中所有产生式具有形式:AV+AVN则称G为2型(前后文无关)文法，记为CFG(ContextFreeGrammar)。2型文法产生的语言称为前后文无关语言CFL，它可由下推自动机识别。若允许-产生式存在，则CFG产生式形式为AV*AVN3型文法和语言若一2型文法G中仅含有形如AaBAa的产生式，其中A,BVN,aVT则称G为右线性文法。类似地，若G中仅含有形如ABaAa的产生式，则称G为左线性文法。通常，把左线性文法和右线性文法都称为3型文法（正规文法）3型文法产生的语言称为3型（正规）语言，它可由有限自动机识别。正规语言可用正规表达式表示。四类语言之间的关系若把各类语言视为语言族LK，K=0,1,2,3则它们之间有真包含关系：0123LLLL文法类型文法名称语言名称自动机名称0短语结构~递归可枚举图灵机1前后文有关~前后文有关线性限界2前后文无关~前后文无关下推自动机3正规~有限状态有限自动机NoamChomsky