CH02--形式语言与自动机.ppt

第2章 形式语言与自动机基 础知识点：文法的形式定义上下文无关文法、正规文法推导、短语、分析树、二义性有限自动机的形式定义自动机、文法、表达式等价性NFA的确定化、DFA的最小化形式语言与自动机基础2.1 语言和文法 2.2 有限自动机 2.3 正规文法与有限自动机的等价性 2.4 正规表达式与有限自动机的等价性 2.5 正规表达式与正规文法的等价性小 结22.1 语言和文法一、字母表和符号串二、语言三、文法及其形式定义四、推导和短语五、分析树及二义性六、文法的变换3一、字母表和符号串字母表 –符号的非空有限集合 –典型的符号是字母、数字、各种标点和运算符等 符号串 –定义在某一字母表上 –由该字母表中的符号组成的有限符号序列 –同义词：句子、字 符号串有关的几个概念n长度 –符号串的长度是指中出现的符号的个数，记作 || –空串的长度为0，常用表示4n前缀 –符号串的前缀是指从符号串的末尾删除0个或多 个符号后得到的符号串如：univ 是 university 的 前缀n后缀 –符号串的后缀是指从符号串的开头删除0个或 多个符号后得到的符号串如：sity 是 university 的后缀n子串 –符号串的子串是指删除了的前缀和/或后缀后 得到的符号串。

如：ver 是 university 的子串n真前缀、真后缀、真子串 –如果非空符号串是的前缀、后缀或子串，并且 ，则称是的真前缀、真后缀、或真子串n子序列 –符号串的子序列是指从中删除0个或多个符号( 这些符号可以是不连续的)后得到的符号串如：nvst5n连接 –符号串和符号串的连接是把符号串加在符 号串之后得到的符号串 –若=ab，=cd，则=abcd，=cdba –对任何符号串来说，都有==n幂 –若是符号串，的n次幂n 定义为：……n个–当n=0时，0是空串 –假如=ab，则有： 0= 1=ab 2=abab ……n=abababn个ab6二、语言语言：在某一确定字母表上的符号串的集合 –空集，集合{}也是符合此定义的语言 –这个定义并没有把任何意义赋予语言中的符号串 语言的运算：假设L和M表示两个语言nL和M的并记作L∪M：L∪M={s|sL 或 sM}nL和M的连接记作LM：LM={st|sL 并且 tM}nL的闭包记作L*：即L的0次或若干次连接 L0∪L1∪L2∪L3∪ ……nL的正闭包记作L+：即L的1次或若干次连接。

L1∪L2∪L3∪L4∪ ……7nL={A,B, … ,Z,a,b, … ,z}，D={0,1, … ,9} –可以把L和D看作是字母表 –可以把L和D看作是语言n语言运算举例：n把幂运算推广到语言 L0={}，Ln=Ln-1L，于是Ln是语言L与其自身的n-1 次连接语言 描述L∪D 全部字母和数字的集合LD 由一个字母后跟一个数字组成的所有符号串的集合L4 由4个字母组成的所有符号串的集合L* 由字母组成的所有符号串（包括）的集合L(L∪D)* 以字母开头，后跟字母、数字组成的所有符号串的集合D+ 由一个或若干个数字组成的所有符号串的集合 8三、文法及其形式定义n文法：所谓文法就是描述语言的语法结构的形式规则n任何一个文法都可以表示为一个四元组G=(VT,VN,S, )VT是一个非空的有限集合，它的每个元素称为终结符号VN是一个非空的有限集合，它的每个元素称为非终结符号VT∩VN =φS是一个特殊的非终结符号，称为文法的开始符号是一个非空的有限集合，它的每个元素称为产生式。

产生式的形式为： “” 表示 “定义为”（或“由……组成”） 、(VT∪VN)* ，左部相同的产生式1、2、……、n可以缩写1|2|……|n “|” 表示 “或”， 每个i(i=1,2,…,n)称为的一个候 选式9文法的分类根据对产生式施加的限制不同，定义了四类文法和相应的四种形式语言类文法类型 产生式形式的限制 文法产生的语言类0型文法 其中 ,(VT∪VN)* 0型语言||0 1型文法，即  1型语言，即 上下文有关文法 其中 ,(VT∪VN)* 上下文有关语言|||| 2型文法，即 A 2型语言，即 上下文无关文法 其中 AVN，(VT∪VN)* 上下文无关语言3型文法，即 Aa或AaB（右线性），或 3型语言，即正规文法 Aa或ABa（左线性） 正规语言（线性文法） 其中 A,BVN， aVT∪{}10上下文无关文法及相应的语言n所定义的语法单位(或称语法实体)完全独立于这种 语法单位可能出现的上下文环境n现有程序设计语言中，许多语法单位的结构可以用 上下文无关文法来描述。

例：描述算术表达式的文法G：G=({i,+,-,*,/,(,)},{,,},,) 其中： + | - | * | / | () | in语言L(G)是所有包括加、减、乘、除四则运算的算 术表达式的集合11n如果用“::=”代替“”，这组产生式可以写为 ：::= + | - | ::= * | / | ::= () | in元语言： ::= 表示 “定义为” 或 “由……组成 ”表示非终结符号 | 表示“或”BNF（Backus-Normal Form）表示法12文法书写约定n终结符号 –次序靠前的小写字母，如：a、b、c –运算符号，如：+、-、*、/ –各种标点符号，如：括号、逗号、冒号、等于号 –数字1、2、…、9 –黑体字符串，如：id、begin、if、thenn非终结符号 –次序靠前的大写字母，如：A、B、C –大写字母S常用作文法的开始符号 –小写的斜体符号串，如：expr、term、factor、 stmt13n终结符号串 –次序靠后的小写字母，如：u、v、…、zn文法符号串 –小写的希腊字母，如：、、、n可以直接用产生式的集合代替四元组来描述文法， 第一个产生式的左部符号是文法的开始符号。

n文法符号 –次序靠后的大写字母，如：X、Y、Z14四、推导和短语例：考虑简单算术表达式的文法G：G=({+，*，（，），i},{E，T，F},E,)： E E + T | TT T * F | FF（E）| in文法所产生的语言 从文法的开始符号出发，反复连续使用产生式对 非终结符号进行替换和展开，就可以得到该文法定义的 语言15推导假定A是一个产生式，和是任意的文法符号串， 则有： A  n “” 表示 “一步推导”即利用产生式对左边符号串中的一个非终结符号进 行替换，得到右边的符号串n 称A直接推导出n 也可以说是A的直接推导n 或说直接归约到A16从文法开始符号E推导出符号串i+i的详细过程如果有直接推导序列：12…n 则说1推导出n，记作：1 n **“ ”表示0步或多步推导称这个序列是从1到n的长度为n的推导A    所用产生式 从E到  的推导长度E E+T   EE+T 1E+T T+T  +T ET 2T+T F+T  +T TF 3F+T i+T  +T Fi 4i+T i+F i+  TF 5i+F i+i i+  Fi 6E  E+T  T+T  F+T  i+T i+F i+i 17最左推导最右推导如果  ，并且在每“一步推导”中，都替换中最左 边的非终结符号，则称这样的推导为最左推导。

记作：**lm 如果  ，并且在每“一步推导”中，都替换中最右 边的非终结符号，则称这样的推导为最右推导记作：**rm 最右推导也称为规范推导E  E+T  T+T  F+T  i+T i+F i+iE  E+T  E+F  E+i  T+i F+i i+i18句型句子 仅含有终结符号的句型是文法的一个句子 语言 文法G产生的所有句子组成的集合是文法G所定义的语言 ，记作L(G)对于文法G=(VT,VN,S,)，如果S ，则称是当前文法 的一个句型若S ，则是当前文法的一个左句型，若S ，则是当前文法的一个右句型lm*rmL(G)={ | S ，并且 VT* }+19对于文法G=(VT,VN,S,)，假定是文法G的一个句型 ，如果存在：短语S A，并且 A *+则称是句型关于非终结符号A的短语 如果存在：S A，并且 A  *则称是句型关于非终结符号A的直接短语一个句型的最左直接短语称为该句型的句柄。

例:ETT*FT*(E)F*(E)i*(E)i*(E+T)i*(T+T)i*(F+T)i*(i+T) ① ② ③ ④ ⑤ ⑥ ⑦ ⑧ ⑨ ⑩20五、分析树及二义性n分析树n子树n子树与短语之间的关系n二义性21分析树n推导的图形表示，又称推导树n一棵有序有向树，因此具有树的性质 ；n自己的特点：每一个结点都有标记 –根结点由文法的开始符号标记； –每个内部结点由非终结符号标记， 它的子结点由这个非终结符号的这次推 导所用产生式的右部各符号从左到右依 次标记； –叶结点由非终结符号或终结符号标 记，它们从左到右排列起来，构成句型 ETT*FT*(E)F*(E)i*(E)i*(E+T)i*(T+T)i*(F+T) i*(i+T)ETT * FF ( E )i E + TT F i ETT*FF*Fi*Fi*(E) i*(E+T)i*(T+T)i*(F+T)i*(i+T)22T子树E子树T子树ETT * FF ( E )i E + TT F i 子树n分析树中一个特有的结点 、连同它的全部后裔结点 、连接这些结点的边、以 及这些结点的标记。

n子树的根结点的标记可能 不是文法的开始符号n如果子树的根结点标记为 非终结符号A，则可称该子 树为A-子树23直接短语短语句柄ETT * FF ( E )i E + TT F i 子树与短语的关系n一棵子树的所有叶。