编译基础形式语言.ppt

第*章 编译基础-形式语言,第一节 字母表、串、语言,1 字母表：有穷非空字符集,语言允许使用的字符集可识别符号,例： =a-z,A-Z,0-9,+,_,*,/,/(,),=.,2 字符串：字母表中符号组成的任何有穷序列单词,例：scanf,int,3.1415,x1,100,a,3 字符串运算： A、B为字符串集合 x，y为字符串,连接： xy 称为x和y的连接 例：int x x=100,积：AB=xy/x A,而y B,闭包：A*=A0 A1 A2. An 其中： A0= ， Ai= Ai-1 A A+= A*- ,A+中的每一个元素即为一个语句 例： x=3.14159*r*r,形式语言是一个字母表上按某种规则构成的所有串的集合。在语言中这些串称为句子。,对于一个句子，存在两个过程： 读-识别过程-编译的过程 写-推导过程-书写源程序,第二节 文法的引例,句子：I am a teach.,I,am,a,teacher,am,a,teacher, i,第三节 文法的形式定义,一、几个概念,1、非终结符语法变量,2、终结符单词,3、产生式规则,二、文法的定义,文法是一个四元组，表示为： G=（VN，VT，P，S）,其中： VN -非终结符 VT -终结符 P-产生式 S-开始符号,P： V+ ， V* V=VN VT,例：描述系表结构的文法，其形式描述为G=（VN，VT，P，S）,VN = VT =I，am ,a ,teacher S= ,am,a,teacher ,P=,i,再给出一个描述算术表达式的文法例子,p=EE+T|T TT*F|F F(E)|a ,文法G（E）：G=（VN，VT，P，S）,VN =E，T，F VT =+，*，（，），a S= E,* 句型：S= , V* 为句型 例： I am ,* 句子：S= w, w VT* w为句子 例：Iam a teacher,* 语言：L=w/w w VT* , 且S=w 例：I am a teacher,推导的定义,若存在v w0 w1 . wn=w(n0) 则记为v =+ w，v推导出w，或w归约到v,若有v =+ w，或v=w， 则记为v =* w,例：GE： EE+T|T TT*F|F F(E)|a,EE+T T+T F+T a+T a+T*F a+F*F a+a*F a+a*a,句子：用符号a，+，*，(和)构成的算术表达式,通过对产生式施加不同的限制，Chomsky将文法分为四种类型：,0型文法：对任一产生式，都有 (VNVT)+， (VNVT)*,1型文法：对任一产生式，都有|， 仅仅 S除外,2型文法：对任一产生式A，都有AVN ， (VNVT)*,3型文法：任一产生式A的形式都为AaB或 Aa，其中AVN ，BVN ，aVT,文法分类：,文法的类型,自然语言属于上下文有关文法,例：1型（上下文有关）文法 文法GS： SCD AbbA CaCA BaaB CbCB BbbB ADaD C BDbD D AabD,文法的类型,是语法分析的基础,例：2型（上下文无关）文法 文法GS： SAB ABS|0 BSA|1,3型文法,GS： S0A|1B|0 A0A|1B|0S B1B|1|0,GI： I lT I l T lT T dT T l T d,是词法分析的基础,文法的类型,四种文法之间的逐级“包含”关系,0型文法,1型文法,2型文法,3型文法,文法和语言,0型文法产生的语言称为0型语言,1型文法或上下文有关文法（ CSG ）产生的语言称为1型语言或上下文有关语言（CSL）,2型文法或上下文无关文法（ CFG ）产生的语言称为2型语言或上下文无关语言（ CF L ）,3型文法或正则（正规）文法（ RG ）产生的语言称为3型语言正则（正规）语言（ RL ）,根据形式语言理论,文法和识别系统间有这样的关系,0型文法（短语结构文法）的能力相当于图灵机，可以表征任何递归可枚举集，而且任何0型语言都是递归可枚举的 1型文法（上下文有关文法）：产生式的形式为1A212，即只有A出现在1和2的上下文中时，才允许取代A。其识别系统是线性界限自动机。,带 a0 a1 a2 a3 a4 a5 a6 a7 a8 an-1 an,有限控制器,磁头,任何能用图灵机描述的计算都能机械实现，任何能在现代计算机上实现的计算都能用图灵机描述,2型文法（上下文无关文法CFG）：产生式的形式为A，取代A时与A的上下文无关。其识别系统是不确定的下推自动机。 3型文法（正规文法RG）：产生的语言是有穷自动机（FA）所接受的集合,第五节 正规方法与有穷自动机,一、正规文法,例：文法 G=（VN，VT，P，S） 其中： VN=A，B，C VT=a,b,c S=A P:A aB A aA B bB B bC C cC C c,L(G)=ambncp/m,n,p1,A=aA=aaA=aaaB =aaabB=aaabbbC =aaabbbcC= aaabbbccC = aaabbbccc,最小句子：abc,P:A aB A aA B bB B bC C cC C c,例：写出产生语言L(G)=ambcn/m,n0的正规文法,解：文法 G=（VN，VT，P，S） 其中： VN=A，S VT=a,b S=S P:,最小语言：b,S aS,S b,S bA,A cA,Ac,例：C语言标识符的文法描述 L（G）=w/w为字母或-打头的字母数字串,解：P:,IaB I -B,B aB B dB Ba B d,I a,二、有穷自动机 1。特点：接收离散输入，状态有穷，只需考虑当前输入和当前内部状态,2、原理：有穷自动机控制器读头自左向右逐个扫描并读入输入符号，并且根据控制器的当前状态和当前输入符号控制转入下一个状态,、模型,Main ( ) int I , j , k ;,有穷控制器,例：电梯：当前状态（五楼，向上） 当前输入（二楼，向下）,、表示状态图,I,B,T,T,a,-,a,d,其它,例：C语言的标识符,、形式定义 确定的有穷自动机是一个五元组 M=（Q， ， ，q0，Z）,其中：Q是一有穷状态集,是有穷输入字母表,是Qx Q的映射函数 其含义： （ q1,a)= q2,q0 Q,唯一的初态,Z是的子集，是终态集,例：奇偶测试器,q0,0,q1,1,q1,0,1,自动机：（Q， ， ，q0，Z） Q q0, q1 =0,1 q0=q0 Z=q1,映射函数： （ q,)= q （ q,)= q （ q1,)= q （ q1,)= q,例：,三、正规表达式与有穷自动机 关系：等价、交换,文法 G=（VN，VT，P，S）和 自动机 M=（Q， ， ，q0，Z）,可转换为： VN 为终态 q0 VT ,，S若 ,映射函数： 、： a2 , 则（ ,a)= A2 2、： a, 则（ ,a)= T 3、（ ,a)= 空动作,例：已知正规文法 （A,B,C,a,b,c,P,S 其中： P:A aA A aB B bB B bC C cC Cc 试写出与其等价的,解：(A,B,C,a,b,c, ,S,T),A,B,C,T,a,a,b,b,c,c,映射函数： （ A,a)= A （ A,a)= B （B,b)= B （B,b)= C （C,c)= C （C,c)= T,练习：w/w是和的个数都为偶数的、串 试写出能识别该语言的自动机和描述该语言的文法,第六节 上下文无关文法语法基础,一、上下文无关文法 文法 G=（VN，VT，P，S） ： A （ VN VT),例：anbn/n 1 P: S aSb S ab,二、自嵌套性 如果上下文无关文法中存在一个终结符，且 ( , 不空），称该上下文无关文法具有可嵌套性,自嵌套性是上下文无关文法与正规文法的本质区别,例：wcwr/w （a |b), wr是w的反置 P: S aSa S bSb S c,句子abbacabba,三、下推自动机,、模型,输入带,有穷 控制器,下推栈,、操作,、接收,b.空动作 （ q, ,Z)= (q1, ),A、读入输入符号，替换栈顶，改变状 态，读头右移 （ q,a,Z)= (q1, ),空栈：输入串空，栈内也空,终态：规定终态，导致进入终态的串被 认为接收。此时，栈内可能工不 空,、定义 是一个七元组， M=（Q, , ,q0, 0 , ）,是有穷输入字母表；,其中：Q是一有穷状态集,是下推字母表,是Qx()x Q x*的映射函 数, 其含义： ( q1,a,Z)= (q2, ),q0 Q,唯一的初态;,F是的子集，是终态集,0 是栈底符号,例：wcwr/w （a |b), wr是w的反置,写出识别该语言的,解：M=（Q, , ,q0, 0 , ） Q q0， q， q a,b； =Z0， q0 q0 0 =0,映射函数： ( q0,a,Z0)= (q1, AZ0),( q0,b,Z0)= (q1, BZ0) ( q1,a,A)= (q1, AA),( q1,a,B)= (q1, AB) ( q1,b,A)= (q1, BA),( q1,b,B)= (q1, BB) ( q1,c,A)= (q2, A),( q1,c,B)= (q2, B) ( q2,a,A)= (q2, ),( q2,b,B)= (q2, ) ( q2, , Z0)= (q0, ),( q0, c, Z0)= (q0, ),句型、推导,EE+T T+T T+T*F F+T*F F+F*F a+F*F a+F*a a+a*a,GE： EE+T|T TT*F|F F(E)|a,EE+T T+T F+T a+T a+T*F a+F*F a+a*F a+a*a,EE+T E+T*F E+T*a E+F*a E+a*a T+a*a F+a*a a+a*a,对于句子a+a*a 有不同的推导,规范推导 规范句型,最左（最右）推导：在推导的任何一步，其中、是句型，都是对中的最左（右）非终结符进行替换 最右推导被称为规范推导。 由规范推导所得的句型称为规范句型,语法树,设G=( VN,VT,P,S)为一cfg，若一棵树满足下列4个条件，则此树称作G的语法树(推导树)(派生树）：,1. 每个内结点都有一个标记，此标记是VN的一个符号,2. 根的标记是S,3. 若一结点n至少有一个它自己除外的子孙，并且有标记A，则肯定AVN,4. 如果结点n有标记A,其直接子孙结点从左到右的次序是n1，n2，nk，其标记分别为A1，A2，Ak，那么AA1A2，Ak一定是P中的一个产生式,语法树-句型推导的直观表示,给定文法G=(VN,VT,P,S)，对于G的任何句型都能构造与之关联的语法树(推导树),语法树的结果：,从左到右读出叶子的标记所构成的符号串称为句子,构造语法树,EE+T,GE： EE+T|T TT*F|F F(E)|a,T+T,F+T,a+T,a+T*F,a+F*F,a+a*F,a+a*a,E,E,+,T,a+a*a,T,F,a,T,*,F,F,a,a,语法树看不出推导顺序,上下文无关文法的语法树的用处,用于描述上下文无关文法句型推导的直观方法,例: GS: SaAS ASbA ASS Sa Aba,S a A S S b A a a b a,句型aabbaa的语法树（推导树）,叶子结点：树中没有子孙的结点。 从左到右读出推导树的叶子标记连接成的文法符号串，为GS的句型。也把该推导树称为该句型的语法树。,但是，一个句型是否只对应唯一的一棵语法树呢?一个句型是否只有唯一的一个最左(最右)推导呢?,一棵语法树表示了一个句型的种种可能的(但未必是所有的)不同推导过程.,例：GE: E i E E+E E E*E E (E),E E + E E * E i i i,E E * E i E + E i i,句型 i*i+i 的两个不同的最左推导：,推导2：E E*E i*E i*E+E i*i+E i*i+i,推导1：E E+E E*E+E i*E+E i*i+E i*i+i,二义文法,若一个文法存在某个句子对应两棵不同的语法树，则称这个文法是二义的或者，若一个文法存在某个句子有两个不同的最左（右）推导，则称这个文法是二义的,判定任给的一个上下文无关文法是否二义，或它是否产生一个先天二义的上下文无关语言，这两个问题是递归不可解的，但可以为无二义性寻找一组充分条件,二义文法改造为无二义文法 GE: E i GE：E T|E+T E E+E T F|T*F E E*E F （E）|i E (E) 规定优先顺序和结合律 如果产生上下文无关语言的每一个文法都是二义的，则说此语言是先天二义的。对于一个程序设计语言来说，常常希望它的文法是无二义的，因为希望对它的每个语句的分析是唯一的。,句型的分析,句型分析就是识别一个符号串是否为某文法的句型，是某个推导的构造过程。,从左到右的分析算法，即总是从左到右地识别输入符号串，首先识别符号串中的最左符号，进而依次识别右边的一个符号，直到分析结束。,在语言的编译实现中，把完成句型分析的程序称为分析程序或识别程序。分析算法又称识别算法。,句型的分析算法分类,分析算法可分为： 自上而下分析法： 从文法的开始符号出发，反复使用文法的产生式，寻找与输入符号串匹配的推导。,自下而上分析法： 从输入符号串开始，逐步进行归约，直至归约到文法的开始符号。,两种方法反映了两种语法树的构造过程。,