上下文无关语法.ppt

1,计算理论,2,主要内容,2.1 上下文无关文法概述 2.1.1 上下文无关文法的形式化定义 2.1.2 上下文无关文法举例 2.1.3 设计上下文无关文法 2.1.4 歧义性 2.1.5 乔姆斯基范式 2.2 下推自动机 2.2.1 下推自动机的形式化定义 2.2.2 下推自动机举例 2.2.1 与上下文无关文法的等价性 2.3 非上下文无关语言,3,上下文无关文法 (CFG) 概述,A 0A1 A B B #,变量 (Variables) A, B,终止符 (Terminals) 0,1,#,起始变元 (Start Variable) A,箭头的左侧只有一个变量,替换规则又称为产生式,4,如何利用 CFG 产生字符串,A 0A1 A B A #,获取一个字符串的替换过程叫派生。 例如字符串 000#111 的过程如下： A 0A1 00A11 000A111 000B111 000#111,(1) 写下起始变元第一条规则左边的变元。 (2) 取一个已写下的变元，并找到以该变元开始的规则，把这个变元替换成规则右边的字符串。 (3) 重复步骤2，直到写下的字符串没有变元。,5,如何利用 CFG 产生字符串,A 0A1 A B A #,可以用语法生成树形象地表示派生过程。,A,A,A,B,#,0,0,0,1,1,1,A,6,文法的语言,A 0A1 A B A #,文法 G1 可以产生的字符串包括： #, 0#1, 00#11, 000#111, 用文法 生成的所有字符串的集合称为文法的语言。 L(G1) 表示文法 G1 产生的语言。 L(G1) = 0n#1n | n 0 用上下文无关文法产生的语言叫上下文无关语言。 文法 G1 的简写： A 0A1 | B B #,7,上下文无关文法的形式化定义,定义 2.1,上下文无关文法是一个 4 元组 ( V, , R, S )，且 (1) V 是一个有穷集合，称为变元集。 (2) 是一个与 V 不相交的有穷集合，称为终结符集。 (3) R 是一个有穷规则集，每条规则由一个变元和一个由变元及终结符组成的字符串构成。 (4) SV 是起始变元。,8,CFG的术语,假设 u 与 v 由变元及终结符构成的字符串，Aw 是文法的一条规则，称 uAv 生成 uwv，记作 uAv uwv 。 如果 u = v ，或者存在 u1, u2, , uk, k 0 使得 u u1 u2 uk v，则称 u 派生 v，记作 u * v。 文法 G = (V, ,R,S)的语言为 L(G) = w *| S * w ,9,上下文无关文法举例,例2.1 考虑文法 G = ( S, a,b, R, S )，其中规则集 R 为： S aSb | SS | 。 该文法生成 abab，aaabbb，aababb， 如果将 a 看作 (，将 b 看作 )， L(G)是所有正常嵌套的括号字符串构成的语言。,10,设计上下文无关文法,设计如下语言的上下文无关文法 0n1n | n 01n0n | n 0 0n1n | n 0 1n0n | n 0 设计技巧 化繁为简，利用正则，考察子串，利用递归。,11,设计上下文无关文法,CFG for L1 = 0n1n | n 0 S 0S1 | CFG for L2 = 1n0n | n 0 S 1S0 | CFG for L1L2 S S1 | S2 S1 0S11 | S2 1S20 | CFG for L3 = 02n13n | n 0? S 00S111 | ,12,上下文无关文法与正则语言,任何正则语言可以由 CFG 描述。,如果 (qi, a) = qj，则增加规则 Vj aVi 如果 qi 是接受状态，则增加规则 Vi 如果 q0 是起始状态，则 V0 是起始变元。,CFG,G = ( V0, V1, 0,1, R, V0 ) V0 0V0 | 1V1 | V1 1V1 | 0V0,13,最左派生,对于文法 G 中的一个字符串 w 的派生，如果在每一步都是替换左边剩下的变元，则称这个派生是最左派生。 例如G=( S, (,), R, S ) ，其中规则为 S ( S ) | SS | S SS (S)S ( )S ( ) ( S ) ( ) ( ) S SS S(S) (S)(S) ( ) ( S ) ( ) ( ),14,歧义性,一个串可能有两个甚至更多的最左派生。 例如 CFG G=( S, +,*,a, R, S) ，其中规则为 S S + S | S * S | a 产生串 a + a * a S S + S a + S a +S *S a + a * S a + a * a S S *S S + S * S a +S * S a + a * S a + a * a,15,歧义性,定义 2.4,如果字符串 w 在上下文无关文法 G 中有两个或两个以上不同的最左派生，则称 G 歧义地(ambiguously) 产生字符串 w，如果文法 G 歧义地产生某个字符串，则称 G 是歧义的。 某些上下文无关语言只能用歧义文法产生，这样的语言是固有二义的。,16,乔姆斯基范式,定义 2.5,称一个上下文无关文法是为乔姆斯基范式(Chomsky normal form)，如果它的每一个规则具有如下形式： A BC A a 其中 a 是任意的终结符，A、B 和 C 是任意的变元，且 B 和 C 不能同时是起始变元。此外，允许规则 S ，其中 S 是起始变元。,17,乔姆斯基范式,定理 2.6,任一上下文无关语言都可以用一个乔姆斯基范式的上下文无关文法产生。,Step 1: 增加起始变元 S0 和规则 S0 S, 其中S是原来的起始变元。 Step 2: 考虑所有的 规则。 对于 A , 删去每个A都会产生一个新规则。 例如 R uAvAw R uAvw, R uvAw, R uvw,18,乔姆斯基范式,定理 2.6,任一上下文无关语言都可以用一个乔姆斯基范式的上下文无关文法产生。,Step 3: 考虑单一产生式A B。 例如： A B, B aC, B CC, 则增加 A aC, A CC 。 Step 4: 考虑A u1 u2 uk, 其中 k 2且ui 是变量或终结符。替换该规则 A u1A1, A1 u2A2, A2 u3A3, , Ak-2 uk-1uk,19,例题,S ASA | aB A B | S B b | ,S0 S S ASA | aB A B | S B b | ,20,例题,After that, we remove B ,S0 S S ASA | aB A B | S B b | ,S0 S S ASA | aB | a A B | S | B b,Before removing B ,After removing B ,21,例题,After that, we remove A ,S0 S S ASA | aB | a A B | S | B b,Before removing A ,After removing A ,S0 S S ASA | aB | a | SA | AS | S A B | S B b,22,例题,Then, we remove S S and S0 S,After removing S S,After removing S0 S,S0 S S ASA | aB | a | SA | AS A B | S B b,S0 ASA | aB | a | SA | AS S ASA | aB | a | SA | AS A B | S B b,23,例题,Then, we remove A B,Before removing A B,After removing A B,S0 ASA | aB | a | SA | AS S ASA | aB | a | SA | AS A B | S B b,S0 ASA | aB | a | SA | AS S ASA | aB | a | SA | AS A b | S B b,24,例题,Then, we remove A S,Before removing A S,After removing A S,S0 ASA | aB | a | SA | AS S ASA | aB | a | SA | AS A b | S B b,S0 ASA | aB | a | SA | AS S ASA | aB | a | SA | AS A b | ASA | aB | a | SA | AS B b,25,例题,Then, we apply Step 4,Before Step 4,After Step 4 Grammar is in CNF,S0 ASA | aB | a | SA | AS S ASA | aB | a | SA | AS A b | ASA | aB | a | SA | AS B b,S0 AA1 | UB | a | SA | AS S AA1 | UB | a | SA | AS A b | AA1 | UB | a | SA | AS B b A1 SA U a,26,作业,W5: 3.3、3.6,27,主要内容,2.1 上下文无关文法概述 2.1.1 上下文无关文法的形式化定义 2.1.2 上下文无关文法举例 2.1.3 设计上下文无关文法 2.1.4 歧义性 2.1.5 乔姆斯基范式 2.2 下推自动机 2.2.1 下推自动机的形式化定义 2.2.2 下推自动机举例 2.2.1 与上下文无关文法的等价性 2.3 非上下文无关语言,28,下推自动机,考虑语言 0n1n | n0 的识别装置,状态 控制器,栈,下推自动机 (pushdown automata ) PDA = NFA + stack with unlimited size 确定型 PDA 和非确定型 PDA 的语言识别能力不相同。,29,下推自动机(PDA)的形式化定义,定义 2.8,下推自动机是 6 元组(Q, , , , q0, F) (1) Q 是一个有穷集合，称为状态集。 (2) 是一个有穷集合，称为输入字母表。 (3) 是一个有穷集合，称为栈字母表。 (4) : Q P(Q) 是转移函数， 其中 = , = (5) q0 Q是起始状态。 (6) F Q是接受状态集。,PDA 的形式化定义没有提供检验空栈的直接手段。 约定 PDA 在开始时就把一个特殊符号 $ 放入栈中。,30,PDA的计算过程,PDA M = (Q, , , , q0, F) 接受输入串 w ，如果 能够把 w 写成 w1w2wm，其中 wi 存在状态序列 r0, r1, , rmQ 存在 s0, s1, , sm * 满足下述 3 个条件，字符串si 是 M 在计算的接受分支中的栈内容序列。 (1) r0 = q0, s0 = (2) 对于 i = 0, 1, , m-1, 有 (ri+1, b) (ri, wi+1, a), 其中 si = at, si+1 = bt , a, b (3) rm F,31,下推自动机举例,例2.9 描述识别语言 0n1n | n 0的 PDA M。,q1,q2,q3,q4, $ ,1, 0 ,0, 0,1, 0 , $,M = (q1,q2,q3,q4, 0,1, 0,$, , q1, q1,q4), (q1, , ) = (q2, $) , (q2, 0, ) = (q2, 0) (q2, 1, 0) = (q3, ) , (q3, 1, 0) = (q3, ) (q3, , $) = (q4, ) , (q, x, y) = ,32,下推自动机举例,例2.10 构造识别语言 aibjck | i, j, k 0 且 i=j 或 i=k 的 PDA M。,q1,q2,q5,q6, $ ,a, a, $,q7,q3,q4, , , $ ,b, ,c, a , ,c, ,b, a ,33,下推自动机举例,例2.11 构造识别语言 wwR | w 0, 1* 的 PDA M。,q1,q2,q3,q4, $ ,0, 0 1, 1 ,0, 0 1, 1, , $,34,PDA与上下文无关文法的等价性,35,PDA与上下文无关文法的等价性,设 A 是一个 CFL，根据定义，存在一个 CFG G 产生它。 如何把 G 转换成一台等价的 PDA P。 通过确定是否存在关于输入 w 的派生，当 G 产生 w 时，PDA P 接受这个输入。 设计 P ，以确定是否有一系列使用 G 的规则替换。,36,由CFG 构造 PDA,P 的非形式化描述如下： (1) 把标记符 $ 和起始变元放入栈中。 (2) 重复下述步骤： a) 如果栈顶是变元 A，则非确定地选择一个关于 A 的规则，并且把 A 替换成这条规则右边的字符串。 b) 如果栈顶是终结符 a，则读输入中的下一个符号，并且把它与 a 进行比较。 如果它们匹配，则重复， 否则，这个非确定性分支被拒绝。 c) 如果栈顶是符号 $ ，则进入接受状态， 如果此刻收入已全部读完，则接受这个输入串。,37,由CFG 构造 PDA,输入: 1100 CFG: S SS | 1S0 | 10,1100,At the beginning,1100,PDA uses the rule S 1S0,100,Input char is matched,Next char,Next char,Next char,38,由CFG 构造 PDA,输入: 1100 CFG: S SS | 1S0 | 10,100,PDA uses the rule S 10,00,Input char is matched,0,Input char is matched,Next char,Next char,Next char,39,由CFG 构造 PDA,输入: 1100 CFG: S SS | 1S0 | 10,Whole input string is processed,The $ in the top of stack tells PDA the stack is empty. PDA accepts the string,Next char,Next char,40,由CFG 构造 PDA的证明,采用一种缩写记号表示转移函数，即一步把一个字符串写入到栈中。 设 q 和 r 是 P 的状态，a ，s 。 要求 P，当读 a 并且弹出 s 时，从 q 到 r，并且同时把整个字符串 u=u1u2ul 推入栈。可以如下完成这个动作：引入新的状态 q1,ql-1,并且令转移函数 (q, a, s) 包含 (q1, ul) (q1, , ) =(q2,ul-1) (ql-1, , )=(r,u1) 使用记号 (r, u) (q, a, s) 表示当 q 是 P 的状态，a 是下一个输入符号以及 s 是栈顶符号时，PDA P 能够读 a 和弹出s，然后把字符串 u 推入栈和转移到状态 r。,41,由CFG 构造 PDA的示意图,q,r,a, s xyz,A shorthand notation,q,r,q1,q2,a, s z, y, x,Using two dummy states to replace s by xyz at the top of the stack,42,由CFG 构造 PDA的证明,P 的状态集 Q = qstart, qloop, qaccept E，E 实现上面描述的缩写所需要的状态集合。 转移函数定义如下：从初始化栈开始，把符号 $ 和 S 推入栈，实现步骤1的非形式描述： (qstart, , ) = (qloop, S$), 然后进行步骤 2 循环 处理情况1, 此时栈顶为一变元。令 (qloop, , A)=(qloop, w) |Aw 是 R 中的一条规则 处理情况2，这时栈顶是一个终结符。令 (qloop, a, a)=(qloop, ) 处理情况3，这时栈顶是空栈标记符。令 (qloop, , $)=(qaccept, ),43,由CFG 构造 PDA的示意图,qstart,qloop,start, S$, A xyz for rule A xyz,a, a for terminal a, $ ,qaccept,shorthand notation used here,44,例题,例2.14 把下述CFG G转换成一台PDAP1 S aTb | b T Ta | ,见书74页。,45,PDA与上下文无关文法的等价性,为简化工作，对P轻微修改: (1) 有唯一的接受状态, qaccept (2) 在接受之前清空栈 (3) 每一个转移把一个符号推入栈，或者把一个符号弹出栈，但不同时做这两个动作 使P具有第三个特点，需要： (1) 把同时push和pop的转移替换成两个转移，中间要经过一个新的状态； (2) 把每一个既不push也不pop的转移，替换成两个转移，先推入任意一个栈符号，再把它弹出,证明略,46,PDA与上下文无关文法的等价性,对P中的每一对状态p, q,建立一个 CFG变量Apq 目标是使Apq 能准确地产生把P从 p和空栈 一块带到 q和空栈的所有字符串。 PDA有两种方法可以从 p和空栈到 q和空栈: (1) 在到达q之前栈变空 这意味着我们从p到某一个r (with empty stack) 然后到达q (2) 在到达q之前栈从不变空 表明在p时，我们push一些字符t进栈，在q时，我们弹出相同的字符t,47,PDA与上下文无关文法的等价性,对每一个p, q, r, 增加规则 Apq AprArq 对每一个 p, q, r, s ，当(r, t) (p, a, ) 且 (q, ) (s, b, t), 增加规则 Apq aArsb,即, 如果我们可以从p到r，并且从r到q，那么我们可以从p到q（这里，所有开始与结束时栈都为空的,即, 如果我们可以从状态p到r，通过读一个字符a并且将t压入栈中，我们可以从状态s到达q，通过读字符b并且从栈中弹出t，那么如果我们开始状态p，栈为空，可以到达q，栈为空，通过读a，从r到s，然后读b获得,48,PDA与上下文无关文法的等价性,对每一个 p, 增加规则 App ,即, 我们可以从p到p，不需要读任何字符,49,PDA与上下文无关文法的等价性,所以, 在我们的文法中，将有所以的规则 Apq 与 Aqstart, qaccept 集合作为开始变元 剩下的就是证明 Apq 能通过P中准确地产生那些串，从p到q（with empty stacks) 也就是说, 我们需要证明 如果 Apq 产生x, x 由P 从p 到q (with empty stacks)产生 如果 x 由 P 从p到q (with empty stacks), Apq 产生 x,Exercise: Prove the above two statements (Hint: by induction),50,主要内容,2.1 上下文无关文法概述 2.1.1 上下文无关文法的形式化定义 2.1.2 上下文无关文法举例 2.1.3 设计上下文无关文法 2.1.4 歧义性 2.1.5 乔姆斯基范式 2.2 下推自动机 2.2.1 下推自动机的形式化定义 2.2.2 下推自动机举例 2.2.1 与上下文无关文法的等价性 2.3 非上下文无关语言,51,非上下文无关语言,定理 2.19,关于上下文无关语言的泵引理 如果 A 是上下文无关语言，则存在 p (泵长度)，使得 A 中任何一个长度不小于 p 的字符串 s 都能被划分成 5 段 s = uvxyz，且满足下述条件： (1) 对于每一个 i 0, uvixyiz A； (2) | vy | 0； (3) | vxy | p。,52,泵引理的证明思路,设 A 是 CFL，G 是产生 A 的 CFG。要证明 A 中任何足够长的字符串 s 都能够被抽取，并且抽取后的字符串仍在A中。 设 s 是 A 中一个很长的字符串。由于 s 在 A 中，它可以用G 派生出来，从而有一棵语法树。由于 s 很长，s 的语法树一定很高，即，这棵语法分析树一定有一条很长的从树根的起始变元到树叶上的终结符的路径。根据鸽巢原理，在这条长路径上一定有某个变元 R 重复出现。,53,泵引理的证明思路,把 s 切成 5 段 uvxyz，重复第 2 段和第 4 段，得到的字符串仍在A中。即，对任意 i0， uvixyiz A,54,泵引理的证明思路泵长度,设 G 是关于 CFL A 的一个 CFG，令 b 是规则右边符号数的最大值。 在 G 的任意一棵语法树中，一个节点做多有 b 个儿子，即，离起始变元 1 步最多有 b 片树叶；离起始变元不超过 2 步最多有 b2 片树叶；离起始变元不超过 h 步最多有 bh 片树叶。