第二章-形式语言与自动机理论.ppt

1、第二章形式语言和自动机理论，主要内容：语法和语法异议语法等变量环DFA和NFA等变量DFA简化正则表达式，2.1语言和语法，字母符号字符串中连接符号字符串的平方前缀和后缀子字符串集，符号字符串集的乘积符号字符串集的平方符号字符串集的正闭包符号字符串集的星形闭包语言提供了字母表。任意一组字符串易于理解语法构造，其中上述语言、基本概念和语法可以清楚地说明编程语言语法。语法可以自动建立有效的语法分析器结构，检查源程序是否符合语言规定的语法格式。语法定义有助于理解编程语言结构，将源程序转换为目标代码程序，并检查语法错误。基于语法的语言易于扩展，语法概述，语法定义，语法G被定义为4条(VT，VN，S，P

2、) VT。有限终止子集合VN是有限的非终止子集合S是起始子，S VN P是生产式集合，其中，(1型语法3360也称为上下文相关语法)。这是0型语法的特殊情况，要求| | (S除外，S不能出现在生产式的右侧)。2型语法：也称为上下文无关文法。那是一型语法的特例。也就是说，生成式左侧是非终极者3360a。3型语法：也称为正规语法。那是2型语法的特例。也就是说，生成表达式的右侧最多有两个符号，下面的格式之一是： A a，A a B中的A，BVN，aVT。由上下文无关文法(CFG)，四元组(VT，VN，S，P) VT定义的有限最终字符集VN是有限非最终字符集S是起始字符，S VN P是AX1X2Xn其

3、中AVN，Xi (VTVN，派生：A是生产表达式时的A其中，A表示第一步衍生(使用A)。据说这是A直接诱导的。意思是用规则代替左边的符号。右端的符号字符串：表示可以通过一个或多个步骤导出* :也就是说，* :可以通过零阶段或更高阶段导出。文章样式：如果S*存在，则符号字串称为CFG的文章样式。我们用SF(G)表示语法G的所有句型的集合句子。如果只包含终极者，则是名为CFG的句子。其中S是语法的起始语。L(G)=u| S u，u VT*。语法G定义的语言是开头字符可以派生的所有最终符号字符串(文章)的集合。最左(右)导出：导出时，如果选取了文章样式中最左(右)牙齿以外的最终字元，则牙齿导出称为最

4、左(右)导出，使用符号lm(rm)表示最左(右)导出。左(右)文章图案：导出到最左侧柔道的文章图案称为左文章图案，导出到最右侧柔道的文章图案称为右文章图案(标准文章图案)。结论：每个句子都有对应的最右和最左的推导(但关于文章模式的结论不成立)。短语：S是语法的开始，是文章模式(即S *)，满足条件时称为S * A文章模式中的一个短语。直接句(简单句):如果满足条件，S * A A就是句子的简单句。控制柄：一个文章图案中可以有多个简单的球体，最左边的简单球体称为控制柄。语法分析树及语法异议性、语法分析树(分析树)用于说明句型的结构，是句型诱导的树形表达。语法G=(VN，VT，S，P)，满足以下条

5、件的树称为G的分析树：1。每个节点都有G的语法符号，根节点显示初始字母S，非叶节点显示非最终字符，叶节点显示最终字符或非最终字符或。2.非叶节点a有n个儿子节点(从左到右)，分别为X1、X2、对于Xn，g必须为AX1X2.将创建Xn牙齿。线性导出：使用符号导出称为线性导出。树导出不同于线性导出。线性导出表示导出顺序，树导出不表示导出顺序。因此，文章模式通常只有一棵分析树(没有双重性)，而线性诱导可以多得多。异议语法，异议语法：如果一个句型有两个徐璐的其他语法分析树，语法就有异议语法G=(，*，I，(，)，E，E，E，P)。其中P是E I E E E E E E E E * E * E。文章模式

6、i*i i:柔道1: e e * e e I * e I * e I I柔道13360 e * e I * e I * e e I * e e I * e e I * e e I * I e I * I e I * I e I * I e I * I e I * I e I * I I I I I，语法等效删除空的生成式清理：可以为所有语法G1配置语法G2，以便L(G1)=L(G2)和G2中没有空的生成式。例如：AaBcD Bb | DBB | d，删除不可到达生成式清理：可以为所有语法G1配置语法G2以创建L(G1)=L(G2)，G2中的每个非终结式字符必须出现在相应的文章之一中。删除特殊生

7、成式清理：可以为所有语法G1配置语法G2以创建L(G1)=L(G2)，G2没有特殊生成式清理。例如：AB | D | aB BC | b Cc DB | d，删除公共前缀删除非最终字符a中的a，a(包括左侧的公共前缀)删除方法：1 .建立类似a1 | 2 | | n的形式，引入非最终字元A，以取代为A A | A 1 | 2 | | n。如果左侧递归语法包含以下格式的生成表达式：(1)A avn，v * (2)删除ab ba，bvn，v，(1)直接删除左侧递归：A A |删除左侧递归：A A A A | (2)主要内容：自动机限制DFA(Deterninistic FA)非固定自动机NFA(N

8、ondeterninistic FA) NFA到DFA的转换DFA简化验证，有限自动机DFA验证，有限自动机DFA验证为5字节(，ss)S0 SS是唯一的初始状态。f是SS SS的切换函数(单值)TSSS，是一组退出状态，也称为接受状态集。DFA中的两个茄子表示，状态切换图：节点表示状态，平移边表示平移函数，边的箭头方向指向在平移函数中定义的平移方向。标识初始和结束状态。状态转换表：可以描述为2d阵列。标识初始和结束状态。Trans(SI，a) SJ，DFA示例，DFA M=(a，b，S，U，V，Q，S，f，Q)，其中f表示f(；A )=Q f (U，b )=V f (Q，b )=Q，DFA允

9、许的字符串，*中的所有字符串对于t，如果存在从初始节点到结束节点的路径，牙齿路上所有圆弧的标志连接诸如t的字符串，则DFA M牙齿可接受的字符串的完整记录为L(M)。DFA确定性，初始状态是唯一的。转换函数f:SSSS具有单值函数，即所有状态的SSS和输入符号a，f(S，a)唯一标识以下状态：换句话说，函数变换最多决定一个状态。没有空边。也就是说，不是用()输入的，不确定的自动机NFA，定义1:不确定的有限自动机(NFA)A是5元组A=(，SS，S0，f，TS)。其中，字母SS是状态集S0。初始状态集F是变换函数，但不是。定义2: a为NFA，A=(，SS，S0，f，TS)将L(A)定义为允许

10、从任意初始状态到任意结束状态的字符串。L(A)=|s0s，s0 S0 sTS定义3:集A1和A2是相同字母的自动机，如果L(A1)=L(A2)牙齿，则A1和A2是等效的。NFA到DFA的转换，清理每个非固定自动机A的L(A)=L(A)。变换：符号合并相同状态的徐璐其他输出边，以显示相同的字符。包含边，NFA-DFA转换，合并1。寻找边f(A，)=B，B不输出边。2.b的输出边为f (b，a1)=B1，f (b，a2)=B2，f (b，an)=bn，1)减去A，b之间的边2)添加边f(A4)如果从开始状态到a有长度，则使b进入开始状态。3.重复1和2，直到无限。4.如果存在循环，则可以将这些状态

11、合并为一个状态，以便正确处理。从NFA切换到DFA，合并符号：A: NFA，A3360 DFA1。将a的初始状态设置为S0=S1、S2、Sk。其中S1Sk是A的所有初始状态。2.如果s=S1，sm定义A的状态，A定义f (s，a)=f (S1，a) f (S2，a) f (sm，a) 3.s，NFA到DFA转换(子集方法)将a的初始状态设置为I0=_CLOSURE(S1，S2，Sk)。其中S1Sk是a的所有初始状态。2.如果I=S1，则sm是a的状态，a定义f(S，a)=Ia 3。如果I=S1，则sn是a的状态，如果Si是a的关闭状态，则I是a的关闭状态。DFA的简化(最小化)、DFA的两种状

12、态S1和S2的等效状态、假定初始状态并允许相同的符号字符串，则定义S1和S2是相同的。方法状态合并法状态分离法、DFA简化法、状态合并法(状态吸收法)查找等虚拟态S1和S2 S2初始状态下S1和S2对S2的出现已修改为S1删除状态S2。状态分离方法由两个不同的状态集组初始化：未终止的状态组和已终止的状态组。为每个组的状态分离不等于此的状态组，直到所有状态组的内部状态相同。2.3正则表达式，是描述编程语言中单词的简单数学工具。表示符号字符串的配置模式正则表达式R定义符号字符串集RS。RS中的每个符号字符串都与R牙齿定义的模式相匹配。RS称为R生成语言L(r)正则表达式中出现的所有符号的集合。牙齿

13、正则表达式字母用S表示。正则表达式，主要内容：基本概念正则表达式定义和部分特性扩展正则表达式和编程语言过程中单词的定义正则表达式限制。对于正则表达式、有限自动机、正则表达式定义和某些特性，以及给定的字母表，每个上述正则表达式定义中都有一组字符串。正则表达式(r)、字符串集(r) (r) (r)。也就是说，函数l表示正则表达式字符串集的映射。r的定义和含义如下：正则表达式，即R。其中L()=。正则表达式，即R。其中L()=。c是正则表达式，即cR。其中L(c)=c。如果A和B是正则表达式A R，B R，则(A )R，l(A)=l(A)A | br，l (a | b)=l (a) l牙齿A | B=B.|.符号范围3360-9 a-z a-z不在指定范围内Beginbegin标识符letter=a-z，a-z digit=0-9 identifier=letter(letter | digitw c w | w不能用正则表达式表示A