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

《第二章形式语言与自动机理论基础(形式语言).ppt》由会员分享，可在线阅读，更多相关《第二章形式语言与自动机理论基础(形式语言).ppt（45页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第二章第二章 形式语言与自动机理论基础形式语言与自动机理论基础2.1 预备知识2.2 文法的讨论2.3 文法和语言的定义2.4 分析树和二义性2.5 形式语言概观2.1 预备知识预备知识2.1.1 字母表字母表2.1.2 符号串符号串 一、符号串的定义一、符号串的定义 二、术语二、术语 三、符号串的运算三、符号串的运算 四、符号串集合的运算四、符号串集合的运算 字母表是字母表是符号符号的的非空有穷非空有穷集合；集合；例：例：=a a，b b，c c 任何程序语言都有自己的字母表。任何程序语言都有自己的字母表。2.1.1 字母表字母表 1.计算机语言：由符号“0”和“1”组成的字 母表:=0，1

2、 2.Pascal语言字母表：=AZ,az,09,+,-,*,/,:,”,;，.，,(,),3.C语言字母表：=AZ,az,09,+,-,*,/,_,&,:,”,;，.，?,(,),空格,!,#,%一一.符号串的定义符号串的定义 由字母表字母表中的符号所组成的的任何有穷序列有穷序列被称之为该字母表上的符号串。空符号串空符号串：无任何符号的符号串，记作 2.1.2 符号串符号串 符号串的形式定义符号串的形式定义：(1)字母表上字符是上的符号串。(2)若x是上的符号串，而a是的元素,则xa 是上的符号串。(3)y是上的符号串,当且仅当它由(1)和(2)导出。二二 术语术语（设s是符号串banana

3、）前前 缀缀：移走s的尾部的零个或多于零个符号所得符号串 ,b,ba,ban,bana,banan,banana后后 缀缀：删去s的头部的零个或多于零个符号所得符号串 banana,anana,nana,ana,na,a,子子 串串:从s中删去一个前缀和一个后缀所得符号串 banana,anana,banan真前缀、真后缀和真子串真前缀、真后缀和真子串：不是s和的前缀、后缀和子串子序列子序列:从s中删去零个或多于零个符号(不要求是连续）而得到的符号串。如baaabaaa长长 度度：是符号串中符号的个数。例如|aab|=3,|=0语语 言言：确定字母表上字符串的任何集合确定字母表上字符串的任何集

4、合例如例如：不含任何元素的空集合不含任何元素的空集合，即即 只含有空符号串的集合只含有空符号串的集合 符合符合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

5、 sM 属于L或属于M的符号串s所组成的集合 2.连接连接：LMst|sL and tM s s属于L和t t属于M的的所有符号串st组成的集合 L L=L L=L 3.方幂方幂：L0=L1L LnL（n-1）L (n0)四四.语言语言(符号串集合）的运算符号串集合）的运算4.语言语言L L的的正闭包正闭包，记作L+L+L1L2L3L45.语言语言L L的的KleeneKleene闭包闭包(自反闭包自反闭包)，记作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

6、=09）1LDLD=A Z,a z,0 9 2LD LD 所有一字母后跟一数字组成的符号串构成的集合 3L L4 4 所有的四个字母的符号串构成的集合 4L L（LD)LD)*所有字母打头的字母和数字符号串构成的集合 5D D+所有长度大于等于1的数字串构成的集合2.2 文法的讨论文法的讨论 例：有一英文句子：例：有一英文句子：“The grey wolf will eat the goat.”。这是一个在语法、语义上都正确的句子。如何用语这是一个在语法、语义上都正确的句子。如何用语法单位如法单位如、等推导出该句子？等推导出该句子？ThegreywolfwilleatthegoatBNF范式表

7、示法：范式表示法：如果用符号如果用符号“”(或或“:=”)表示表示“定义为定义为”，用符号，用符号“|”表示表示“或或”，表表示语法成分示语法成分 句子 主语 谓语 （1）主语 冠词 形容词 名词 （2）冠词the （3）形容词 grey （4）谓语 动词 直接宾语 （5）动词 助动词 动词原形 （6）助动词will（7）动词原形 eat （8）直接宾语 冠词 名词 （9）名词wolf （10）名词 goat （11）名词wolf|goat 由规则推导句子由规则推导句子：有了一组规则之后，可以按照一定的方式：有了一组规则之后，可以按照一定的方式用它们去用它们去推导或产生句子推导或产生句子。推导

8、方法：从一个要识别的符号开始推导，即用相应规则的推导方法：从一个要识别的符号开始推导，即用相应规则的右部右部来替代规则的来替代规则的左部左部，每次仅用一条规则去进行推导。，每次仅用一条规则去进行推导。=冠词冠词 形容词形容词 名词名词 这种推导一直进行下去，直到所有带这种推导一直进行下去，直到所有带的符号都由终结符号的符号都由终结符号替代为止。替代为止。1、终结符号集终结符号集 V VT T=the,gray,wolf,will,eat,goat2、非终结符号集非终结符号集 V VN N=句子，主语，谓语，冠词，形容词，名词，动词，直接宾语，助动词，动词原形 3、语法规则集语法规则集 P P=

9、句子 主语谓语，4、开始符号开始符号 S S=句子推导句子所需的四部分推导句子所需的四部分2.3 2.3 文法和语言的形式定义文法和语言的形式定义 一一.文法的形式定义文法的形式定义 二二.直接推导和推导直接推导和推导 三三.语言的形式定义语言的形式定义 四四.短语、直接短语、句柄短语、直接短语、句柄一一.文法和语言的形式定义文法和语言的形式定义定义定义1.11.1：一个上下文无关文法一个上下文无关文法G G是一个四元组G=（V VT T，V VN N S,P S,P），其中：1.V VT T 是一个非空有穷终结符号集合；2.V VN N 是一个非空有穷的非终结符号集合，且VTVN，表示一类具

10、有某种性质的符号 3.S S VN 开始符号。4.P P是一个产生式的非空有穷集合，每个产生式的形式是A，其中 AV VN N，（V VT TVVN N）*开始符号S至少必须在某个产生式的左部出现一次(V(VT TVVN N）*表示什么集合表示什么集合?一般情况下（缺省）符号指称：一般情况下（缺省）符号指称：1 1、A A，B B，C C等，等，表示非终结符号表示非终结符号2 2、a,b,c,da,b,c,d等，等，表示终结符号表示终结符号3 3、,，等等,表示文法符号串表示文法符号串（终结终结符号和非终结符号组成的符号串符号和非终结符号组成的符号串）G=(a,+,*,(,),，P)P：*（)

11、a（用（用E、T、F分别代替分别代替、）E E+T T T T*F F F(E)a 例例 简单算术表达式的文法简单算术表达式的文法G G二二.直接推导和推导直接推导和推导 令G=(VT,VN,S,P),S A；若A P,且,(VTVN)*称A直接推出直接推出,表示成A 同时也称是A的直接推导直接推导，或称 直接归约直接归约到A 如果存在一个直接推导序列：012 n（n0）表示成 0 n，称从0到n的长度为长度为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 E+T E+T T T

12、T T T*F T*F F F F F(E)(E)a 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（VT，VN，S S,P）。如果S S

13、,则称是一个句型句型。仅含终结符号的句型是一个句子句子。语言语言 L(GL(G）是由文法G产生的所有句子所组成的集合：L(G)|S 且VT*例子：例子：一个文法 G(a,b,S,S，P）其中P：SaSb ab 则 SaSb aaSbb a3Sb3 an-1Sbn-1 anbn*+四四.短语、直接短语、句柄短语、直接短语、句柄 令G是一个文法，如果有S A且A 则称是一个关于非终结符号A的，句型的短语。其次如果有 S A 且 A则称是直接短语。一个句型的最左直接短语称为该句型的句柄。*+*注意：短语、直接短语是相对于句型而言，一个句型可能有多个短语、直接短语，句柄只能有一个。S aAS aSbA

14、S aabAS例：S aAS|a A SbAs aASSbAaSbASaabAaabAS一一.分析树的定义分析树的定义二二.画出分析树画出分析树三三.子树子树四四.二义性文法的定义二义性文法的定义2.4 分析树分析树(语法树语法树)和二义性和二义性设G=（VT，VN，S，P）是一个上下文无关文法,G的一棵分析树分析树应满足如下条件：1.每个结点有个标记标记，是V VT TVVN N 中的符号2.根的标记是S S3.如果结点是内部结点内部结点，则其标记A A必在必在V VN N中 4.如果编号为n的结点其标记为A,n1,n2,nk是结点n的从左到右的儿子，并分别有标记X1,X2,Xk，则AX1X

15、2Xk必须是P的产生式5.如果结点n有标记，那么结点n是叶子，且是它父亲唯一的儿子，其他叶子结点是终结符一一.分析树（语法树）的定义分析树（语法树）的定义G(S):(1)SaASa (2)A SbA SS ba 句子aabbaa的分析树3124657891011SaASSbAaabaASaSbSAaabaASaSbSAaaba aSbAS aabAS aabbaS aabbaa aAS S二二.画分析树画分析树 (自顶向下）自顶向下）一棵分析树中一个特有的结点连同它的全部后裔，连接这些后裔的边以及这些结点的标记SAbSaSbaAaa三三.子树子树1、短语短语：一棵子树的所有叶子自左至右排列起来

16、形成一个相对于子树根的短语。2、直接短语直接短语：仅有父子两代的一棵子树，它的所有叶子自左至右排列起来所形成的符号串。3、句柄句柄：一个句型的分析树中最左那棵只有父子两代的子树的所有叶子的自左至右排列。子树子树和和短语、直接短语、句柄短语、直接短语、句柄 S aAS aSbAS例：S aAS|a A SbA 对表达式文法对表达式文法G G和句子和句子a+aa+a*a*a，挑选出最左推导过挑选出最左推导过程中产生的句型中的短语，直接短语，句柄程中产生的句型中的短语，直接短语，句柄 G=(a,+,*,(,),，P)P：（用用E、T、F分别代替分别代替、）E E+T T T T*F F F(E)a

17、EE+TT+TF+T a+T a+T*F a+F*F a+a*Fa+a*aEE+TT+TF+T a+T a+T*F a+F*F a+a*FE+T T,T+T F,F+T a,a+T a,T*F,a+T*Fa,F ,F*F,a+F*F a,a,a+a*F,a*F a,a,a,a*a a+a*aEE+TTFaT*FFaaa+a*a短语 例 给定文法给定文法G=(a,b,c,d,e,S,A,B,S,P)其中其中P:SaAcBe Ab AAb Bd 给出句子给出句子abbcde的最右推导过程，并指出每一步的最右推导过程，并指出每一步推导的短语、直接短语、句柄。推导的短语、直接短语、句柄。S aAcBe

18、 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*aEE+

19、EE*EaaaEE*E+EEaaa 如果一个文法的句子存在两棵语法树存在两棵语法树,则称该句子是二义性的；换而言之，换而言之，无二义性文法的句子只有一棵语法树，尽管推导过程可以不同。如果一个文法包含二义性句子包含二义性句子,则称这个文法是二义性的;否则，该文法是无二义性的。不存在一个算法，它能在有限步骤内，确切地判定一个文法是否是二义的；但能给出一组充分条件，满足这组充分条件的文法是无二义性的。文法等价文法等价定义：定义：如果两个文法G1、G2对应的语言集合相同L(G1)=L(G2)，则称文法等价若文法G存在形如A A的推导,则称文法G是递归文法.文法 G1产生式如下：EE+EE*E(E)a

20、直接递归文法文法 G2产生式如下：ET+a T E*a 间接递归文法递归文法递归文法2.5 2.5 形式语言概观形式语言概观 N.Chomsky把文法分为四种类型四种类型，即0 0型、型、1 1型、型、2 2型、型、3 3型。差别在于型。差别在于对产生式施加了不同限制0 0型型：G=(VT,VN,S,P)规则形式：,(VT VN)*,0 0型文法产生的语言称为型文法产生的语言称为0 0型语言型语言1 1型（上下文有关）型（上下文有关）：规则有 产生式形式：A A VN,(VT VN)*,1型文法产生的语言称为型文法产生的语言称为1 1型语言（上下文有关）型语言（上下文有关）2 2型（上下文无关

21、）型（上下文无关）：规则形式：A A VN，(VT VN)*2 2型文法产生的语言称为型文法产生的语言称为2 2型语言（上下文无关）型语言（上下文无关）3 3型（正规文法）型（正规文法）：左线性和右线性文法：左线性和右线性文法 AaB或Aa（右线性）A,BVN a VT ABa或Aa（左线性）3 3型文法产生的语言称为型文法产生的语言称为3 3型语言（正规语言型语言（正规语言)语言层正规语言3上下文无关语言2上下文有关语言1递归可枚举语言0图灵机TM线性界限自动机LBA下推自动机PDA有穷自动机FA小 结掌握符号串和符号串集合的运算、文法和语言的定义几个重要概念：短语、直接短语和句柄、分析树（语法树）、文法的二义性。了解文法和语言的分类。