形式语言与自动机理论基础(形式语言).ppt

第二章 形式语言与自动机理论基础,2.1 预备知识2.2 文法的讨论2.3 文法和语言的定义2.4 分析树和二义性2.5 形式语言概观,2.1 预备知识,字母表 符号串 一、符号串的定义 二、术语 三、符号串的运算 四、符号串集合的运算,字母表是符号的非空有穷集合；例：=a，b，c任何程序语言都有自己的字母表。,2.1.1 字母表,1.计算机语言：由符号“0”和“1”组成的字 母表:=0，1 2.Pascal语言字母表：=AZ,az,09,+,-,*,/,:,”,;，.，,(,),3.C语言字母表：=AZ,az,09,+,-,*,/,_,，.，?,(,),空格,!,#,%,一.符号串的定义 由字母表中的符号所组成的的任何有穷序列被称之为该字母表上的符号串。空符号串：无任何符号的符号串，记作,2.1.2 符号串,符号串的形式定义：(1)字母表上字符是上的符号串。(2)若x是上的符号串，而a是的元素,则xa 是上的符号串。(3)y是上的符号串,当且仅当它由(1)和(2)导出。,二 术语,（设s是符号串banana）前 缀：移走s的尾部的零个或多于零个符号所得符号串,b,ba,ban,bana,banan,banana后 缀：删去s的头部的零个或多于零个符号所得符号串 banana,anana,nana,ana,na,a,子 串:从s中删去一个前缀和一个后缀所得符号串 banana,anana,banan真前缀、真后缀和真子串：不是s和的前缀、后缀和子串子序列:从s中删去零个或多于零个符号(不要求是连续）而得到的符号串。如baaa长 度：是符号串中符号的个数。例如|aab|=3,|=0,语 言：确定字母表上字符串的任何集合,例如：不含任何元素的空集合，即 只含有空符号串的集合 符合Pascal语法的程序组成的集合（Pascal语言）符合英文语法的句子组成的集合,1.连接：设x和y是符号串，它们的连接xy是把符号串y写在符号串x的之后得到的符号串。例如 x=ba,y=nana,xy=banana.x=x=ba2.方幂：x0=x1=x x2=xx xn=xn-1x 例如 x=ba x1=ba x2=baba x3=bababa,三.符号串的运算,（语言L和M）1.合并：LMs|sL or sM 属于L或属于M的符号串s所组成的集合 2.连接：LMst|sL and tM s属于L和t属于M的所有符号串st组成的集合 L=L=L 3.方幂：L0=L1L LnL（n-1）L(n0),四.语言(符号串集合）的运算,4.语言L的正闭包，记作L+L+L1L2L3L45.语言L的Kleene闭包(自反闭包)，记作L*L*L0 L L0L1L2L3,例：A=x,y A？A*？,x,y,xx,xy,yx,yy,A1 A2,x,y,xx,xy,yx,yy,A0 A1 A2,例:（语言 L=AZ,az D=09）1LD=A Z,a z,0 9 2LD 所有一字母后跟一数字组成的符号串构成的集合 3L4 所有的四个字母的符号串构成的集合 4L（LD)*所有字母打头的字母和数字符号串构成的集合 5D+所有长度大于等于1的数字串构成的集合,2.2 文法的讨论,例：有一英文句子：“The grey wolf will eat the goat.”。这是一个在语法、语义上都正确的句子。如何用语法单位如、等推导出该句子？,BNF范式表示法：如果用符号“”(或“:=”)表示“定义为”，用符号“|”表示“或”，表示语法成分,句子 主语 谓语（1）主语 冠词 形容词 名词（2）冠词the（3）形容词 grey（4）谓语 动词 直接宾语（5）动词 助动词 动词原形（6）助动词will（7）动词原形 eat（8）直接宾语 冠词 名词（9）名词wolf（10）名词 goat（11）,名词wolf|goat,由规则推导句子：有了一组规则之后，可以按照一定的方式用它们去推导或产生句子。推导方法：从一个要识别的符号开始推导，即用相应规则的右部来替代规则的左部，每次仅用一条规则去进行推导。,=冠词 形容词 名词 这种推导一直进行下去，直到所有带的符号都由终结符号替代为止。,1、终结符号集 VT=the,gray,wolf,will,eat,goat2、非终结符号集 VN=句子，主语，谓语，冠词，形容词，名词，动词，直接宾语，助动词，动词原形 3、语法规则集 P=句子 主语谓语，4、开始符号 S=句子,推导句子所需的四部分,2.3 文法和语言的形式定义,一.文法的形式定义 二.直接推导和推导 三.语言的形式定义 四.短语、直接短语、句柄,一.文法和语言的形式定义,定义1.1：一个上下文无关文法G是一个四元组G=（VT，VN S,P），其中：1.VT 是一个非空有穷终结符号集合；2.VN 是一个非空有穷的非终结符号集合，且VTVN，表示一类具有某种性质的符号 3.S VN 开始符号。4.P是一个产生式的非空有穷集合，每个产生式的形式是A，其中 AVN，（VTVN）*开始符号S至少必须在某个产生式的左部出现一次,(VTVN）*表示什么集合?,一般情况下（缺省）符号指称：1、A，B，C等，表示非终结符号2、a,b,c,d等，表示终结符号3、,，等,表示文法符号串（终结符号和非终结符号组成的符号串）,G=(a,+,*,(,),，P)P：*（)a（用E、T、F分别代替、）E E+T T T T*F F F(E)a,例 简单算术表达式的文法G,二.直接推导和推导,令G=(VT,VN,S,P),S A；若A P,且,(VTVN)*称A直接推出,表示成A 同时也称是A的直接推导，或称 直接归约到A 如果存在一个直接推导序列：012 n（n0）表示成 0 n，称从0到n的长度为n的推导。0 n表示从0出发，经0步或若干步，可推导出n（0=n 或 0 n）,+,*,+,推导：E E+T T+T F+T a+T a+F a+a,E E+T T T T*F F F(E)a,例如 EE+TT+TF+Ta+Ta+T*F a+F*Fa+a*Fa+a*a 特点：A(A)，VT*（最左推导）每一步推导都是对最左非终结符号进行替换 EE+TE+T*FE+T*aE+F*a E+a*a T+a*aF+a*aa+a*a 特点：A(A)，VT*（最右推导）每一步推导都是对最右非终结符号进行替换，也称规范推导，其归约称为规范归约,最左推导和最右推导,三.语言的形式定义,四.短语、直接短语、句柄,令G是一个文法，如果有S A且A 则称是一个关于非终结符号A的，句型的短语。其次如果有 S A 且 A则称是直接短语。一个句型的最左直接短语称为该句型的句柄。,*,+,*,注意：短语、直接短语是相对于句型而言，一个句型可能有多个短语、直接短语，句柄只能有一个。,S aAS aSbAS aabAS,例：S aAS|a A SbA,一.分析树的定义二.画出分析树三.子树四.二义性文法的定义,2.4 分析树(语法树)和二义性,设G=（VT，VN，S，P）是一个上下文无关文法,G的一棵分析树应满足如下条件：每个结点有个标记，是VTVN中的符号根的标记是S如果结点是内部结点，则其标记A必在VN中 如果编号为n的结点其标记为A,n1,n2,nk是结点n的从左到右的儿子，并分别有标记X1,X2,Xk，则AX1X2Xk必须是P的产生式如果结点n有标记，那么结点n是叶子，且是它父亲唯一的儿子，其他叶子结点是终结符,一.分析树（语法树）的定义,G(S):(1)SaASa(2)A SbA SS ba 句子aabbaa的分析树,3,1,2,4,6,5,7,8,9,10,11,S,a,A,S,S,b,A,a,a,b,a,A,S,a,S,b,S,A,a,a,b,a,aSbAS,aabAS,aabbaS,aabbaa,aAS,S,二.画分析树(自顶向下）,1、短语：一棵子树的所有叶子自左至右排列起来形成一个相对于子树根的短语。2、直接短语：仅有父子两代的一棵子树，它的所有叶子自左至右排列起来所形成的符号串。3、句柄：一个句型的分析树中最左那棵只有父子两代的子树的所有叶子的自左至右排列。,子树和短语、直接短语、句柄,S aAS aSbAS,例：S aAS|a A SbA,对表达式文法G和句子a+a*a，挑选出最左推导过程中产生的句型中的短语，直接短语，句柄,G=(a,+,*,(,),，P)P：（用E、T、F分别代替、）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,E,E+T,T+T,F+T,a+T,a+T*F,a+F*F,a+a*F,E+T,T,T+T,F,F+T,a,a+T,a,T*F,a+T*F,a,F,F*F,a+F*F,a,a,a+a*F,a*F,a,a,a,a*a a+a*a,E,E,+,T,T,F,a,T,*,F,F,a,a,a+a*a,短语,例,给定文法G=(a,b,c,d,e,S,A,B,S,P)其中P:SaAcBe Ab AAb Bd 给出句子abbcde的最右推导过程，并指出每一步推导的短语、直接短语、句柄。,S aAcBe aAcBe aAcBe aAcBe,abbcde abbcde,b,bb,d b,d b,短语 直接短语 句柄,aAcde aAcde,d d d,aAbcde aAbcde,d,Ab Ab,d Ab,引例 文法 G产生式如下：EE+EE*E(E)a 对于句子a+a*a,有如下两个最左推导：EE+E a+E a+E*E a+a*E a+a*a EE*EE+E*E a+E*Ea+a*E a+a*a,四.文法的二义性（ambiquity）的定义,EE+E a+E a+E*E a+a*E a+a*a,E E*EE+E*E a+E*Ea+a*E a+a*a,E,E,+,E,E,*,E,a,a,a,E,E,*,E,+,E,E,a,a,a,如果一个文法的句子存在两棵语法树,则称该句子是二义性的；换而言之，无二义性文法的句子只有一棵语法树，尽管推导过程可以不同。如果一个文法包含二义性句子,则称这个文法是二义性的;否则，该文法是无二义性的。,不存在一个算法，它能在有限步骤内，确切地判定一个文法是否是二义的；但能给出一组充分条件，满足这组充分条件的文法是无二义性的。,文法等价,定义：如果两个文法G1、G2对应的语言集合相同L(G1)=L(G2)，则称文法等价,若文法G存在形如A A的推导,则称文法G是递归文法.文法 G1产生式如下：EE+EE*E(E)a 直接递归文法文法 G2产生式如下：ET+a T E*a 间接递归文法,递归文法,2.5 形式语言概观,N.Chomsky把文法分为四种类型，即0型、1型、2型、3型。差别在于对产生式施加了不同限制0型：G=(VT,VN,S,P)规则形式：,(VT VN)*,0型文法产生的语言称为0型语言1型（上下文有关）：规则有 产生式形式：A A VN,(VT VN)*,1型文法产生的语言称为1型语言（上下文有关）,2型（上下文无关）：规则形式：A A VN，(VT VN)*2型文法产生的语言称为2型语言（上下文无关）3型（正规文法）：左线性和右线性文法 AaB或Aa（右线性）A,BVN a VT ABa或Aa（左线性）3型文法产生的语言称为3型语言（正规语言),语言层,正规语言3,上下文无关语言2,上下文有关语言1,递归可枚举语言0,图灵机TM,线性界限自动机LBA,下推自动机PDA,有穷自动机FA,小 结,掌握符号串和符号串集合的运算、文法和语言的定义几个重要概念：短语、直接短语和句柄、分析树（语法树）、文法的二义性。了解文法和语言的分类。,