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

第一章 形式语言与自动机基础 第2章 形式语言与自动机基础 知识点：文法的形式定义 上下文无关文法、正规文法 推导、短语、分析树、二义性 有限自动机的形式定义 自动机、文法、表达式等价性 NFA的确定化、DFA的最小化 形式语言与自动机基础 2.1 语言和文法 2.2 有限自动机 2.3 正规文法与有限自动机的等价性 2.4 正规表达式与有限自动机的等价性 2.5 正规表达式与正规文法的等价性 小 结 2.1 语言和文法 一、字母表和符号串 二、语言 三、文法及其形式定义 四、推导和短语 五、分析树及二义性 六、文法的变换 一、字母表和符号串 字母表 符号的非空有限集合 典型的符号是字母、数字、各种标点和运算符等。 符号串 定义在某一字母表上 由该字母表中的符号组成的有限符号序列 同义词：句子、字 符号串有关的几个概念 长度 符号串?的长度是指?中出现的符号的个数，记作|?|。 空串的长度为0，常用?表示。 前缀 符号串?的前缀是指从符号串?的末尾删除0个或多个符号后得到的符号串。如：univ 是 university 的前缀 连接 符号串?和符号串?的连接??是把符号串?加在符号串?之后得到的符号串 若?=ab，?=cd，则??=abcd，??=cdba。 对任何符号串?来说，都有??=??=? 幂 若?是符号串，?的n次幂?n 定义为： 二、语言 语言：在某一确定字母表上的符号串的集合。 空集?，集合{?}也是符合此定义的语言。 这个定义并没有把任何意义赋予语言中的符号串。 语言的运算：假设L和M表示两个语言 L和M的并记作L∪M：L∪M={s|s?L 或 s?M} L和M的连接记作LM：LM={st|s?L 并且 t?M} L的闭包记作L*：即L的0次或若干次连接。 L={A,B, … ,Z,a,b, … ,z}，D={0,1, … ,9} 可以把L和D看作是字母表 可以把L和D看作是语言 语言运算举例： 三、文法及其形式定义 文法：所谓文法就是描述语言的语法结构的形式规则。 任何一个文法都可以表示为一个四元组G=(VT,VN,S, ?) VT是一个非空的有限集合，它的每个元素称为终结符号。 VN是一个非空的有限集合，它的每个元素称为非终结符号。 VT∩VN =φ S是一个特殊的非终结符号，称为文法的开始符号。 ?是一个非空的有限集合，它的每个元素称为产生式。 产生式的形式为：??? “?” 表示 “定义为”（或“由……组成”） ?、??(VT∪VN)* ，??? 左部相同的产生式???1、???2、……、???n可以缩写 ???1|?2|……|?n “|” 表示 “或”， 每个?i(i=1,2,…,n)称为?的一个候选式 文法的分类 根据对产生式施加的限制不同，定义了四类文法和 相应的四种形式语言类。 上下文无关文法及相应的语言 所定义的语法单位(或称语法实体)完全独立于这种语法单位可能出现的上下文环境 现有程序设计语言中，许多语法单位的结构可以用上下文无关文法来描述。 例：描述算术表达式的文法G： G=({i,+,-,*,/,(,)},{表达式,项,因子},表达式,?) 其中?： 表达式?表达式+项 | 表达式-项 | 项 项?项*因子 | 项/因子 | 因子 因子?(表达式) | i 语言L(G)是所有包括加、减、乘、除四则运算的算术表达式的集合。 BNF（Backus-Normal Form）表示法 如果用“::=”代替“?”，这组产生式可以写为： 表达式 ::= 表达式+项 | 表达式-项 | 项 项 ::= 项*因子 | 项/因子 | 因子 因子 ::= (表达式) | i 元语言： ::= 表示 “定义为” 或 “由……组成” …… 表示非终结符号 | 表示“或” 文法书写约定 终结符号 次序靠前的小写字母，如：a、b、c 运算符号，如：+、-、*、/ 各种标点符号，如：括号、逗号、冒号、等于号 数字1、2、…、9 黑体字符串，如：id、begin、if、then 非终结符号 次序靠前的大写字母，如：A、B、C 大写字母S常用作文法的开始符号 小写的斜体符号串，如：expr、term、factor、stmt 终结符号串 次序靠后的小写字母，如：u、v、…、z 文法符号串 小写的希腊字母，如：?、?、?、? 可以直接用产生式的集合代替四元组来描述文法，第一个产生式的左部符号是文法的开始符号。 四、推导和短语 例：考虑简单算术表达式的文法G： G=({+，*，（，），i},{E，T，F}