北京商城网站建设报价单,企业管理咨询考试,设计本官方网站广告,宁波网络营销推广哪家好一、文法的种类
1.1 分类定义
Chomsky 文法定义#xff1a; G(V,Vt,P,Z)G (V, V_t, P, Z)G(V,Vt,P,Z)VVV#xff1a;符号集合VtV_tVt#xff1a;终结符号集合PPP #xff1a;有穷规则集合ZZZ#xff1a;是被符号#xff0c;不能是终结符
关于不同文法的区别
类型…一、文法的种类
1.1 分类定义
Chomsky 文法定义
G(V,Vt,P,Z)G (V, V_t, P, Z)G(V,Vt,P,Z)VVV符号集合VtV_tVt终结符号集合PPP 有穷规则集合ZZZ是被符号不能是终结符
关于不同文法的区别
类型定义接受重点0 型文法α::β\alpha::\betaα::β图灵机由字符串推导出另一个字符串对于左部和右部都没有限制1 型文法αUβ::αuβ\alpha U \beta :: \alpha u \betaαUβ::αuβ线性界限的图灵机要求左部必须有一个非终结符而且一次只能改变一个非终结符同时具有上下文敏感的特性2 型文法U::αU:: \alphaU::α不确定的下推自动机左部只能有一个非终结符也就是上下文不敏感的但是对于右部没有限制3 型文法U::Va,U::aU::Va, U:: aU::Va,U::a有穷自动机右部一定会推出终结符而且右部很规则
在判断文法的时候因为不同文法呈现包含关系所以应当按照 3−2−1−03 - 2 - 1 - 03−2−1−0 的顺序去判断。
当一个文法的右部呈现正则形式的时候那么为 3 型文法否则判断左部如果左部都是一个非终结符那么就是 2 型。然后判断是否每条规则只改变一个非终结符不是则为 0 型。
1.2 三型文法直观感受
因为只有两种推导形式所以其语法树会长得很“偏瘫”比如说对于左线性文法就是长成这个样子的 正是因为这种“偏瘫”的性质才使得有限状态机成为接受三型文法的工具可以一个个字符的读入而且没有“回溯”过程。其推导的过程就好像我们平时书写一样成一个线性的趋势。
1.3 上下文无关特性
我们说大部分高级程序设计语言都是二型文法具有上下文无关的特性但是其实对于复杂特性的语言比如说 CPP对又是它他是具有上下文敏感的特性的比如说
abc d 可以被理解成一个
vectorvectorint matrix; 也可以被理解成位运算
int x 4 3 2 1 所以在“不引入符号表”可以看做符号表就是记录上下文信息的工具的前提下是没有办法进行语法分析的所以 CPP 会进行一种“试错式”的语法分析就好像我们的错误处理一样。
递归下降法更适合分析二型文法也不是完全都可以分析出来而不适合分析一型文法所以在实验课中一旦引入错误处理也就是相当于引入了一些一型文法就会导致语法分析没有办法是朴素的递归下降而是必须进行尝试性回溯这是递归下降的局限性。
有一个观点很有意思就是词法分析语法分析语义分析其实完成的是同一个任务的不同部分所以我们在设计的时候可以考虑将总任务分给这三个部分当一个部分被设计的简单的时候另一个部分就会被设计的复杂比如说 python 如果按照普通理解其实是一型文法因为缩进的原因语法变得上下文敏感了但是实际上是二型文法这是因为缩进在词法分析的时候被处理成了“缩进增”和“缩进减”这与“左大括号”和“右大括号”是等价的。另一个例子肯定程序本身是上下文相关的又不是计算器那么相当于符号表这类语义分析中上下文敏感的实现代替了复杂的语法分析使得语法分析可以很简单。
另外文法不仅和表达能力相关它同时也与计算能力相关所以只有 0 型文法具有图灵机的全部能力严格讲高级语言并不能够发挥出其全部实力。据说 lisp 是基于 0 型文法的。
1.4 文法的等价性
文法的等价性指的是如果两个文法描述的语言是相等的那么就称这个两个文法是等价的也就是说这并不涉及文法的本身性质一个三型文法可以与一个一型文法等价并无大碍。 二、正则转换
2.1 等价转换框架 如图所示图上的这五种东西是等价的并且是可以相互转化的虽然有一些是没有意义的下面将分别介绍。
2.2 正则文法与 DFA 转换 正则文法又称为 3 型文法。正则文法有两种左线性和右线性分别长这样 左线性A :: Bt右线性A :: tB 之前觉得正则文法就已经可以描述很多东西了我以为 SysY 是可以用正则文法表示的但是其实正则文法连基本的表达式都没有办法表达。所以正则一般都用于词法分析语法分析其就不适用了。 首先讨论正则文法转换为 DFA
对于左线性文法有如下方法
对于 A::BtA :: BtA::Bt 有 δ(B,t)A\delta(B, t) Aδ(B,t)A对于 A::tA :: tA::t有 δ(S,t)A\delta(S, t) Aδ(S,t)A 其中 SSS 为状态机的起始状态状态机只有一个终止状态 ZZZ 同时 ZZZ 是正则文法的起始符号识别符号。
举个例子 不可否认左线性有些不自然因为明明是 A→BA \rightarrow BA→B 这种规则但是最后的边却是 B→AB \rightarrow AB→A 恰恰反过来但是并非毫无道理相反当前状态代表着已经规约的非终结符是一种自底向下的过程进行最左规约如下所示 对于右线性文法
对于 A::tBA :: tBA::tB 有 δ(A,t)B\delta(A, t) Bδ(A,t)B对于 A::tA :: tA::t有 δ(A,t)Z\delta(A, t) Zδ(A,t)Z 其中 ZZZ 为状态机的终止状态状态机只有一个起始状态 SSS 同时 SSS 是正则文法的起始符号识别符号。
这就很好理解这是一个自顶向下的过程当前状态是要解析的非终结符。这么看正则文法真的有很多很好的性质他们的 FIRSTFIRSTFIRST 和 FOLLOWFOLLOWFOLLOW 都是直白的这就导致其对于语法规则的选择很简单。
对于 DFA 转换成正则文法一般转换为左线性文法并不可以直接看成逆过程有如下规则
对转换函数 δ(A,t)B\delta(A, t) Bδ(A,t)B 可写成一个产生式A::tBA :: tBA::tB对于终止状态可写成一个产生式Z::εZ::\varepsilonZ::εDFA 的初态对应于文法的开始符号识别符号。
如下示例 2.3 正则文法与正则表达式
比较简单需要注意的是当正则文法向正则表达式转换的时候应用的不只是转换法则还有正则表达式的运算。
由正则文法转正则表达式 由正则表达式转正则文法 2.4 正则表达式与 NFA
第一条规则描述的是很“显然”的事情他说的是对于一个正则表达式它天然拥有“开始”和“终止”两个状态他们中间会有一条边或者一堆状态和一堆边。 在这里其实可以反思一个事情就是在 DFA 或者在 NFA 中绝对不会有从一个状态中出现两条相同的边也就是 这是显然的因为这样在 AAA 状态输入 xxx 就并不知道是应当转移到 BBB 还是应当转移到 CCC 。但是对于 ϵ\epsilonϵ 却没有这个约束如下所示 下面的规则都是这种现象的体现他们会给 NFA 引入大量的 ϵ\epsilonϵ 。这显然是不利于 NFA 到 DFA 的化简的后面的例题也有说明为了规避这种现象我们考虑将一些的 ϵ\epsilonϵ 化简掉。在化简中这样形式的正则表达式可以十分有用 XaYbX aYb XaYb 其中 YYY 可以是任何正则表达式a,ba, ba,b 是终止符这个表达式意味着XXX 一定是由 aaa 开头由 bbb 结尾这个是一个很好的性质我们可以将开头的 ϵ\epsilonϵ 和结尾的 ϵ\epsilonϵ 可以分别被替换成 a,ba, ba,b 。这种替换只要不会导致 NFA 的定义被违反也就是上面提到的情况那么就是可行的。 反之 2.5 NFA 转 DFA
首先是确定 I(S)I(S)I(S) 这是一种 I−εI-\varepsilonI−ε 闭包说的是开始状态和可以通过 ε\varepsilonε 到达的状态组成的集合。
然后需要通过边访问比如说 Ia(S)I_a(S)Ia(S) 表示的是通过 aaa 这条边 I(S)I(S)I(S) 可以到达的状态的集合而且这个集合中还有通过 ε\varepsilonε 到达的状态换句话说也是闭包。
然后就这么周而复始的运动即可。
实际操作的时候是真的难首先是这种题一般是给出正则表达式然后求最小 DFA。那么如果不幸构造出一个极其复杂的 NFA那就真的完蛋了比如说下面的例子如果按照规则构造的话是这样的 a((a∣b)∗∣ab∗a)∗b\tt{a((a|b)*|ab*a)*b } a((a∣b)∗∣ab∗a)∗b 正常构造是 7 个状态 然后就会陷入无限的求解闭包的过程甚至 DFA 的状态比 NFA 还多中所以应当用前面介绍的方法先手动化简成这样 具体的过程是这样的考虑题目 a((a∣b)∗∣ab∗a)∗b\tt{a((a|b)*|ab*a)*b } a((a∣b)∗∣ab∗a)∗b 可以知道大概会翻译成这样 然后进行一个显然的化简 然后观察子正则表达式发现 ab∗a\tt{ab*a}ab∗a 发现他是以 aaa 开头结尾的所以可以进行化简 其核心在于不能让一个状态有两个同为 ε\varepsilonε 的出边或者入边显然是可以化简的而且这种太难搞了。
然后进行化简的时候可以考虑先对于每个状态求一遍闭包这样对于多个状态的合并就不需要多次重复计算了如下所示
状态ab12, 323, 42, 3, 532, 3, 43, 542, 345
这里一定要小心谨慎因为一不小心就错了。
然后就可以进行查表求解过程了因为 DFA 的状态也需要标识所以建议用英文字母与原来 NFA 的阿拉伯数字区分
DFANFAabA12, 3B2, 32, 3, 42, 3, 5C2, 3, 42, 3, 42, 3, 4, 5D2, 3, 52, 3, 42, 3, 5E2, 3, 4, 52, 3, 42, 3, 4, 5
2.6 最小化 DFA 采用分割法进行计算不过必须要承认这个方法实际上的如果按照严谨的计算那么运算量是极其复杂的是没有办法很容易的得出答案在得出答案的过程中还需要不断的依靠直觉而且似乎具有某些不动点算法的性质。 最小化 DFA 干的事情就是将 DFA 中“等价”的状态合并到一起主要考虑两个条件 一致性条件状态 sss 和状态 ttt 必须同时为接受状态或者非接受状态。这个很显然也很好判断。蔓延性条件对于所有的输入符号状态 sss 和状态 ttt 必须转换到等价状态里。这个就是很符合直观认知的但是很难应用因为等价状态是一个变化的东西。 在教材上只是用例子演示了一下并没有完整的算法。我凑活写了一个 首先利用一致性条件将状态划分为两个集合。“认为“此时每个集合里的每个状态都是等价的。基于第二点遍历集合中的每个状态利用蔓延性条件检验是否真的与该状态所在集合的其他状态等价当出现不等价情况分割集合回到第二点。如果所有状态均检查完毕则算法结束。 以一道题举例这是状态转移表
ab163273315446573641742
其中接受状态是 {5,6,7}\{5, 6, 7\}{5,6,7} 。
原题在求解的时候在这张表的右侧拓展了一列用于分区但是这是不严谨的因为我们并不保证等价状态一定在表上挨在一起。所以考虑手写集合。
首先根据一致性条件划分出两个集合
{1,2,3,4},{5,6,7}\{1, 2, 3, 4\}, \{5, 6, 7\}{1,2,3,4},{5,6,7}
然后遍历 1发现 2 和 1 等价但是和 3 不等价所以分割出 12
{1,2},{3,4},{5,6,7}\{1, 2\}, \{3, 4\}, \{5, 6, 7\}{1,2},{3,4},{5,6,7}
此时遍历 12 没有问题遍历 3发现和 4 不等价所以分割数 3
{1,2},{3},{4},{5,6,7}\{1, 2\}, \{3\}, \{4\}, \{5, 6, 7\}{1,2},{3},{4},{5,6,7}
遍历 1234 没有问题遍历 5发现与 6 不等价所以分割 5
{1,2},{3},{4},{5},{6,7}\{1, 2\}, \{3\}, \{4\}, \{5\}, \{6, 7\}{1,2},{3},{4},{5},{6,7}
检查完毕算法结束。
