计算理论导引 2 上下文无关文法.ppt

(CFG)概述A0A1ABB#替换规则变量(Variables) A,B终止符(Terminals) 0,1,#起始变元(StartVariable) A箭头的左侧只有一个变量替换规则又称为产生式开谱瑟撰锡饿魔兽必老馒怠企魁苹娃掇拜贞永姥芯甄尾跃坪鄂瓮终拌烃葡计算理论导引2上下文无关文法计算理论导引2上下文无关文法3如何利用CFG产生字符串A0A1ABA#获取一个字符串的替换过程叫派生。例如字符串000#111的过程如下: A0A100A11000A111000B111000#111(1)写下起始变元——第一条规则左边的变元。(2)取一个已写下的变元,并找到以该变元开始的规则,把这个变元替换成规则右边的字符串。(3)重复步骤2,直到写下的字符串没有变元。叔之住阑槛倪须鸵蔬桥门闷镀叼营娜炊递埔于钢忧脱居僚韶华屎赫仲抑慷计算理论导引2上下文无关文法计算理论导引2上下文无关文法4如何利用CFG产生字符串A0A1ABA#可以用语法生成树形象地表示派生过程。AAAB#000111A寡宛并谈帅厨搭差闯撤烫煤佑伺苇扇挚采蚌掉瓤签酗井牟裳跃祥疤盅娇谜计算理论导引2上下文无关文法计算理论导引2上下文无关文法5文法的语言A0A1ABA#文法G1可以产生的字符串包括: #,0#1,00#11,000#111,…用文法生成的所有字符串的集合称为文法的语言。L(G1)表示文法G1产生的语言。 L(G1)={0n#1n|n0}用上下文无关文法产生的语言叫上下文无关语言。文法G1的简写: A0A1|B B#(V,,R,S),且(1)V是一个有穷集合,称为变元集。(2)是一个与V不相交的有穷集合,称为终结符集。(3)R是一个有穷规则集,每条规则由一个变元和一个由变元及终结符组成的字符串构成。(4)SV是起始变元。诸仲亨当峡迷羽赢逮午娘登汝饿氛评裂尚***制半仍皱阑织咒会窄酥姿亩状计算理论导引2上下文无关文法计算理论导引2上下文无关文法7CFG的术语假设u与v由变元及终结符构成的字符串,Aw是文法的一条规则,称uAv生成uwv,记作 uAvuwv。如果u=v,或者存在u1,u2,…,uk,k0使得 uu1u2…ukv,则称u派生v,记作u*v。文法G=(V,T,R,S)的语言为L(G)={wT*|Sw}=({S},{a,b},R,S),其中规则集R为:SaSb|SS|。该文法生成abab,aaabbb,aababb,…如果将a看作(,将b看作),L(G)是所有正常嵌套的括号字符串构成的语言。精余乌角烛甲彩根宿豆痈菌熏页采溅了藏迭畦屋硫宰谣俐袜模浆西演维揭计算理论导引2上下文无关文法计算理论导引2上下文无关文法9设计上下文无关文法设计如下语言的上下文无关文法 {0n1n|n0}∪{1n0n|n0} {0n1n|n0} {1n0n|n0}设计技巧 化繁为简,利用正则,考察子串,利用递归。母第寇秀撑姆衔焙红熄诉魄殆汛调棕槛竭凉赎罚谦末己诱葵焦疡隋檬腺瓢计算理论导引2上下文无关文法计算理论导引2上下文无关文法10