【计算机】形式语言03章无关文法与无关语言

《【计算机】形式语言03章无关文法与无关语言》由会员分享，可在线阅读，更多相关《【计算机】形式语言03章无关文法与无关语言（151页珍藏版）》请在金锄头文库上搜索。

1、第三章 上下文无关文法与上下文无关语言,上下文无关文法的重要性： 拥有足够强的表达力来表示大多数程序设计语言的语法 可以构造有效的分析算法来检验一个给定的字符串是否是由某个上下文无关文法产生。,上下文无关语言在实践中有重要意义： 1）定义程序设计语言: BNF（巴克斯-诺尔范式）； 2）描述文档格式: XML，HTML； 3）使语法分析概念形式化； 4）简化程序设计语言的翻译: 语法分析器的设计；,给定文法G，如果对于G中的任意产生式，而只是一个非终结符，即A，AV，(UV）*，则称文法G为上下文无关文法（简称无关文法）。如果一个语言能由一个无关文法产生，则称这个语言是上下文无关语言（简称无关

2、语言）。,定义3-1 线性的无关文法,若无关文法G=(,V,S,P) 的所有产生式都是下列形式之一： AuBv 或 A w； 其中:A，BV；u，v+；w*。 该文法称为线性的无关文法。 注意： u，v可以有一个为空串 。,特别地，如果u=，称为左线性的(无关)文法；如果v=，称为右线性的(无关)文法。 从定义可以看出，线性的无关文法是受限制的无关文法；本身一定还是无关文法。,化简的上下文无关文法,左线性文法和右线性文法是线性文法中特殊的两类。,定理3-2 G=（，V，S，P）是一个上下文无关文法，产生式的一般形式为Aw，其中： w（UV）* ， 则存在另一个等价的线性的无关文法G1，而G1中

3、产生式的形式为； Aa 或 Aab。 其中: AV；a，bU ；V+。,证明：读者自己完成。,定理3-3 G=（，V，S，P）是一个上下文无关文法，产生式的一般形式为Aw，其中：w（UV）*，则存在另一个等价的无关文法G1，而G1中产生式的形式为； Aa 或 AaB 或 AaBC。 其中：A ，B，CV；a 。 证明： 读者自己完成。,3.1 消除无关文法中的无用非终结符号,定义3-4 文法中的无用符号 一个无关文法G,符号YV,如果不出现在任何形如S=*uYv=*uwv的推导之中，称Y为文法G的无用非终结符。 其中：u ，w ，v *。,反之，一个无关文法G,符号YV,如果能够出现在某个形如

4、S=*uYv=*uwv的推导之中，称Y为文法G的有用非终结符。其中：u ，w ，v *。,从定义可知：有用非终结符，必须同时满足两个条件 (1) 从它开始推导，能够产生终结符号串； (2) 它必须出现在某个句型中； 判断某个符号是有用非终结符，就应该从这两方面同时进行考虑。,有用非终结符的判断算法： 略。,定义3-7 无用的产生式,如果一个产生式中（产生式的左边或右边）包含有无用的非终结符，则该产生式就是无用的产生式。可以将无用的产生式从文法中删除掉。,问题3-8 文法产生的语言是否为空？ 一个无关文法G，产生的语言为L(G)，而L(G)是否为空（即空集），是可以判定的。,注意： 一个语言包含

5、有空串或语言本身就是，它们都不是空集。,判定方法： 首先使用空串定理，消除该无关文法中的所有空串产生式，如果还有S，则该文法产生的语言不为空； (2)构造能产生终结符串的非终结符集合N，如果S N，则该文法产生的语言不为空。否则，该文法产生的语言为空。,定理3-11 已知产生一个非空语言的上下文无关文法G，则对于某个A V，总有A=*w，且w*。 证明：读者自行完成。,定理3-12 一个无关文法G=(,V,S,P)，产生的语言为L(G)。如果L(G)不为空，则至少存在一个非终结符A，而它的产生式右边仅仅只包含终结符号或空串 。 证明提示： 考虑产生串的推导过程中最后使用的产生式的特点。 证明：

6、读者自行完成。,定理3-13 已知产生一个非空语言的上下文无关文法G=（，V，S，P），则能够构造一个等价的无关文法G1，对于任意A V，总有一个推导:S=*w1Aw3=*w1w2w3，且w1，w2，w3 *。 证明：读者自行完成。,定理3-14 已知产生一个非空语言的上下文无关文法G=(,V,S,P)，则文法中的每个非终结符都是有用的；即：若AV，则 S=*uAv=*uwv 其中：u ，w ，v *。 证明：读者自行完成。,问题3-15 上下文无关语言CFL是否有穷是否可以判定？ 上下文无关文法CFG生成无穷个句子的原理是利用递归的产生式，即 S=*uAy=*uvAxy=*=*uviAxiy

7、=*uviwxiy 根据着一原理可以判定上下文无关语言是否有穷。,定义3-16 可派生性图的定义 上下文无关文法G=（，V，S，P），文法G的可派生性图是满足下列条件的有向图： (1)对于终结符或非终结符X，图中有且仅有一个标记为X的顶点。 (2)如果A-X1X2Xn，则图中存在从标记为A的顶点分别到标记为X1,X2,Xn的顶点的弧。 (3)图中只有满足条件(1)和(2)的弧。,可派生性图表示了G中变量间的派生关系：从A到B有一条有向路表示B出现在A派生出的某个符号串中。,3.2 推广的化简上下文无关文法 上下文无关文法化简的目的：限制产生式的格式而不降低文法生成句子的能力，从而降低文法分析算

8、法的复杂度。 上下文无关文法化简的基本手段：删除无用符号删除单一产生式组,对于一个上下文无关文法G，如果： 没有AA形式的产生式； 每个非终结符A都是有用的，即： 有S=*A=*w； 其中：，w，*；则该文法是化简的上下文无关文法。,对于任意的无关文法，进行 （1）直接删除没有AA形式的产生式 对于AA形式的产生式，该类产生式是递归的，可以反复利用任意多次，但对于无穷语言的产生，没有任何作用。可以直接删除即可。 （2）消除无关文法中的无用非终结符号 消除无关文法中的无用非终结符号后，无关文法中的所有非终结符号都是有用的。 得到的文法是化简的上下文无关文法。,定义3-21 推广的简化上下文无关文

9、法： 对于一个上下文无关文法G，如果该文法中不存在形如A B的产生式（A，B V ）， 则该文法是推广的化简上下文无关文法。,定理3-22 对于一个上下文无关文法G，能够找到一个等价的无关文法G1，而G1中不存在形如A B的单产生式（A，B V ）。 证明思路： 对于某个推导过程：S=*A=B=wI= 可简化为：S=*A=wI= 即省略掉A = B的推导。,因此，需要将AB的产生式使用下面产生式进行替换：A w1|w2|w3|wn 而B w1|w2|w3|wn 是文法G中关于B的所有产生式。,实际上，就是将推导过程在产生式中就体现出来。,注意，对于关于B的产生式，B w1|w2|w3|wn 需

10、要保留，不能删除。因为可能存在 S=1B1=1wI1= 的推导，即该推导过程没有使用产生式A B。,思考：,能否将文法中的产生式右边的A直接替换为B，然后将 A1|2|3|m|B 替换为 B1|2|3|m 这是不行的；因为可能产生多余的串。A ，而B ，如果B ，它将B的功能扩大了(能够定义为和)。,例如： S AB S BB A B|a B a B b B b L为:ab,bb L为:aa,ab,bb,ba,3.3 推导树,对于无关文法G，如果串能由该文法产生，则的产生过程可以用推导的办法表示，即用符号“=”表示，也可以用推导树的办法表示。,定义3-23 推导树（语法分析树）,推导树是一棵有

11、向无循环的图。 树的节点是文法中的非终结符或者终结符，如果有空串产生式，则也可以是树的节点，树的根节点是文法的开始符号S； 如果推导使用了产生式Aa1a2a3an，其中A是非终结符，ai是非终结符或者是终结符；则a1，a2，a3，an都是A的直接后继节点（A称为父节点，a1，a2，a3，an称为子节点）；,一个节点和它的直接后继节点之间用有向边连接起来； 如果节点是终结符，该节点称为叶子节点； 如果节点是非终结符，该节点称为非叶子节点（或称为分枝节点）； 端末节点(仅有入口，没有出口的节点)从左到右的连接，是该推导树产生的边缘。,注意：推导树是向下生长的。,定理3-24 设文法G为无关文法，那

12、么S=*，当且仅当存在一棵以为边缘的推导树。即文法和推导树都可以产生串。 证明: 略。,结论： 端末节点从左到右的连接，就是该推导树产生的句型。 注意： 推导树不仅可以表示句子的产生，也可以表示句型的产生。 思考： 端末节点一定为终结符吗？,定义3-24 直接子孙和子孙的定义： 在一个有向无循环的图(树)中，称满足下列条件的节点n为节点m的直接子孙：有一条有向边从节点m出发进入节点n。 如果有节点的序列：n1，n2，n3nk，使得m=n1，n=nk，以及对于每一个i，ni+1是ni的一个直接子孙,则节点n称为节点m的子孙。,约定： 每一个节点都是自己的子孙。,一棵推导树T中的每个节点都是根节点

13、S的一个子孙。,定义3-25 推导树的另一个定义 无关文法G=(,V,S,P)，若一棵树满足下列条件，则称之为文法的推导树：,每个节点都有一个标记(是UV的一个符号或者是)； 根的标记为S； 若一个节点有多于1个的子孙，该节点标记的符号为非终结符号；,如果节点A的所有直接子孙，从左到右的次序是标记为A1，A2，A3，Ak的节点，则 A A1A2A3Ak为文法G的一个产生式。,实际上，存在产生句子的（完整的）推导树，也存在产生句型的（不完整的）推导树。 一棵推导树中，仅有一个子孙的节点称为端末节点（该子孙就是自己）。,定义3-26 最左推导和最左推导的定义 无关文法G，有产生式A ，对于一步直接

14、推导1A2=12： 若1*，则称之为一步最左推导； 若2*，则称之为一步最右推导；,对于文法G和句型w： 如果产生w的每一步推导都是最左推导，则称产生w的推导为最左推导； 如果产生w的每一步推导都是最右推导，则称产生w的推导为最右推导。 最右推导还称为规范推导。,一般，常使用最左推导。,例3-27 文法 S0B|1A A0|0S|1AA B1|1S|0BB 对于串0011的产生过程： 最左推导： S=0B=00BB=001B=0011 最右推导： S=0B=00BB=00B1=0011,推导也可以用推导树表示为：S0 B0 B B 1 1,实际上，一棵推导树代表了一个句型（或者句子）的最左推导

15、和最右推导过程以及其他所有的以任意顺序进行推导的过程。 在推导树中，从根节点到一个叶节点（或者端末节点）叫一条路径，一条路径上的非终结符的个数，叫做该路径的长度。最大的路径长度叫做该推导树的高度。,定义3-28 推导树的子树的定义: 在一棵推导树T中，以任意一个非终结符A为根，连同它的所有后继节点（直接的节点和非直接的节点，即它的所有子孙， 并且子孙的个数1），构成一棵子树，称之为推导树T的A-子树。 推导树本身就是树T最大的一棵子树；即 S-子树。 注意： 一个非终结符本身不是一棵子树。,对于推导树：S0 B0 B B 1 1,共有4棵子树：除它自身外，还有B B B 1 1 0 B B1 1,