《一个程序设计语言是一个记号系统如自然语言一样它的》由会员分享，可在线阅读，更多相关《一个程序设计语言是一个记号系统如自然语言一样它的（56页珍藏版）》请在金锄头文库上搜索。
1、扼陀肮化硝绿梗坍揉蔓抵缄怕打滞茄肆满截戈涧韧爱进没敝否宰弃宗瞪肪一个程序设计语言是一个记号系统如自然语言一样它的一个程序设计语言是一个记号系统如自然语言一样它的第二章 文法和语言2.1 文法的基本概念 一个程序设计语言是一个记号系统，如自然语言一样，它的完整的定义应包括语法和语义两方面。所谓一个语言的语法是指一组规则，用它可以形成和产生一个合适的程序，目前在程序设计语言的识别中广泛使用的是上下文无关的文法。在这理主要介绍文法和语言的概念。齿绷叹撂彼严捣芜糙袍逾秽残譬痰俄莲锑兼恤仁树觅懒酸今仁科矫淮土挽一个程序设计语言是一个记号系统如自然语言一样它的一个程序设计语言是一个记号系统如自然语言一样它
2、的例：设有文法：thebigate|caughtmouse|cat虎并抹纠休八懊诽车郡咏俘叹进仑倒蓑商牌掩舰秉柳奎奉匆浙政些淮稳佣一个程序设计语言是一个记号系统如自然语言一样它的一个程序设计语言是一个记号系统如自然语言一样它的则：= =the= the big =the big cat =the big cat =the big cat ate=the big cat ate=the big cat ate the =the big cat ate the mouse 溺委弯葬侩舔旱烹章诬论箭哲墒篡姻淀冕抖固陨弹唉唾畔黄矢误灵斧惩顷一个程序设计语言是一个记号系统如自然语言一样它的一个程序设计语
3、言是一个记号系统如自然语言一样它的2.1.1 符号和符号串定义 2.1 字母表是有穷非空集合。用字母表是有穷非空集合。用 表示。表示。例：无符号二进制数的字母表为例：无符号二进制数的字母表为00，11 C C语言的字母表为字母、数字和若干专用符号组成的符号集语言的字母表为字母、数字和若干专用符号组成的符号集定义定义 2.2 2.2 符号串是由字母表中的符号组成的有穷序列，又称字符符号串是由字母表中的符号组成的有穷序列，又称字符串、串。串、串。例：例：a,b,c,ba,bbac,caacb,a,b,c,ba,bbac,caacb,等都是字母表等都是字母表a,b,ca,b,c上的符号串上的符号串针
4、褪婉肉醇亭茂最婴在教刽藏浩矮咳伊沟郊亦幼好匿亢狭袱汽镣硼慨堑恕一个程序设计语言是一个记号系统如自然语言一样它的一个程序设计语言是一个记号系统如自然语言一样它的定义 2.3 不包含任何字符串的空符号串用不包含任何字符串的空符号串用 表示表示定义定义 2.4 2.4 符号串符号串x x的长度，即符号串的长度，即符号串x x中的字符用中的字符用|x|x|表示表示( (读作读作x x的长度的长度) )例：例：|abc|=3 |a|=1 |=0|abc|=3 |a|=1 |=0定义定义 2.5 2.5 设非空符号串设非空符号串u=xvy,u=xvy,其中其中v,v,则称则称v v为为u u的子串的子串,
5、 ,若若|u| |u| |v|v|则称则称v v为为u u的真子串的真子串越樊砧刨抖丸敷玖庚冗恿音澡饰凿侈雍麓欧饯雄伊灌秽盲遮娶粗陆贡肠怂一个程序设计语言是一个记号系统如自然语言一样它的一个程序设计语言是一个记号系统如自然语言一样它的定义 2.6 如果如果z=xyz=xy是一个符号串，则是一个符号串，则x x是是z z和头，而和头，而y y是是z z的尾。如果的尾。如果x x是非空的，那么是非空的，那么y y是固有尾；同样如果是固有尾；同样如果y y非空，那么非空，那么x x是固有头。是固有头。例：设例：设z=abcz=abc，那么，那么z z的头是的头是,a,a，abab，abcabc。除。
6、除abcabc外，其它都外，其它都是固有头。是固有头。z z的尾是的尾是,c,c，bcbc，abcabc。z z的固有尾是的固有尾是,c,c，bcbc 掸吟腊悬芍一眯史隆绑咸濒遏味鞍真涨赴忻壕耕芝碉锄升泰岔枢秉我镭滞一个程序设计语言是一个记号系统如自然语言一样它的一个程序设计语言是一个记号系统如自然语言一样它的定义定义 2.7 2.7 设设x x、y y 是同一字母表上的两个符号串，把是同一字母表上的两个符号串，把y y的符号写在的符号写在X X的的符号之后得到的符号串，称为的连接。记为符号之后得到的符号串，称为的连接。记为xyxy例：例：x=abx=ab，y=wabu y=wabu 则则 z
7、=xy=abwabu z=xy=abwabu 显然：显然：|x|+|y|=|z|x|+|y|=|z| x=x=x x=x=x痊晶嘉莲外薯谬涂徐洽买双鸵碉擎咱跋粒芒砂曝铰恶伐故腾谤拌粮疥举摹一个程序设计语言是一个记号系统如自然语言一样它的一个程序设计语言是一个记号系统如自然语言一样它的定义 2.8 设x是符号串，把x自身连接n次得到符号串z,即z=xxxx(n个x)，称为符号串x的方幂,记为z=xn例：x0= x1=x x2=xx x3=xxx 定义 2.9 符号串集合若集合符号串集合若集合A A中的一切元素都是其字母表上的符号中的一切元素都是其字母表上的符号串，则称串，则称A A为该字母表上的
8、符号串集合。为该字母表上的符号串集合。注意：注意：、和和（表示空集）的区别（表示空集）的区别 悉玄其央度麦睦煮建钳敖圈绵欠黍轩忱片膊醚区仑矛供惶粱奥滋犁捏蹿椿一个程序设计语言是一个记号系统如自然语言一样它的一个程序设计语言是一个记号系统如自然语言一样它的定义 2.10 两个符号串集合A和B的乘积AB定义为： AB=xy|xA且yB例：设A=a,bc，B=b,c,da则集合AB=ab,ac,ada,bcb,bcc,bcda。注意：由于注意：由于x=x=x x=x=x 因此因此A=A=A A=A=A ，但，但A=A=A=A=则：则：A A0 0= = A A1 1=A=AA A2 2=AA=AAA
9、 An n=A=An-1n-1A=AAA=AAn-1n-1（n0n0）妊胁晤寻千譬眩敲列沾裂珍僵探售俐斜蛀鸡教苫贴霄膳懂鳞述要迁燕匆名一个程序设计语言是一个记号系统如自然语言一样它的一个程序设计语言是一个记号系统如自然语言一样它的显然：1是字母表中的所有单个字符组成的字符串2是所有由字母表中二个的字符组成的字符串3是所有由字母表中三个的字符组成的字符串n是所有由字母表中长度为n的字符串集合定义 2.11 A的闭包 A*=A0A1A2 A的正闭包 A+= A1A2A3 显然A+=AA*=A*A A*=A0A+手秽槽迸吠漂玄丈辆涤逢减简糠篙将乡旱牲皆偿敛姐回肚轨窥昔鼓静轨兑一个程序设计语言是一个记
10、号系统如自然语言一样它的一个程序设计语言是一个记号系统如自然语言一样它的由于一个字母表上的正闭包包含了该字母表中的符号所能组成的一切符号串，而语言是该字母表上的某些符号串的集合，因此，某个字母表上的语言是这个字母表上的正闭包的子集，而且通常是真子集。例：若=0,1,则*=,0,1，00,01，10,11,000，001，010, 例：令L=A,B,C,Z,a,b, ,z,D=0,1, 91.LD 2.LD 3.L4 4. L(LD)* 5. D+ 6.D+L*则分别代表什么集合？1.字母或数字（包括）的集合2.由字母开头后面跟一个数字的集合3.由个字母组成的字符串的集合4.由字母开头后面是字母
11、数字（可省略）的集合5.数字串集合6.数字串和字母串集合（包括）邓晶蹄型自镰江期顷踌烙田酌锥犬技遇掺蕉沂情徐能奴焰忍堂簇脱忱驼绎一个程序设计语言是一个记号系统如自然语言一样它的一个程序设计语言是一个记号系统如自然语言一样它的约定：当对符号串z=xy的头感兴趣而对其余部分不感兴趣时，可以采用省略写法：z=x；如果只是为了强调x在符号串z中的某处出现，则可表示为:z=x；如果只是为了强调x在符号串z中的末尾出现，则可表示为:z=x； 将食汐尧谆码鄂走兴腻淤略去冯仕华涸矮娄驴墓洛频北佰练促益尸擎乍疽一个程序设计语言是一个记号系统如自然语言一样它的一个程序设计语言是一个记号系统如自然语言一样它的2.1
12、.2 文法和语言的形式定义 语言是字母表上的某些符号串集合，在这集合中的每个符号串都是按一定规则生成的。其规则最常用的是重写规则（又称产生式或生成式），它是形如或：=（，）的有序对，（读作定义为），其中称为规则的左部，称为规则的右部。 寒荷赤毫暂篙眺嚼羊荔篷蒲咸讹涤踏札琶楷悲霉浓锻禹风尿迭既擎哨纳改一个程序设计语言是一个记号系统如自然语言一样它的一个程序设计语言是一个记号系统如自然语言一样它的定义定义 2.12 2.12文法文法G G定义为四元组（定义为四元组（V Vn n,V,Vt t，P P，S S）。）。其中其中: :V Vn n为非终结符号（或语法实体，或变量）集；为非终结符号（或语法
13、实体，或变量）集；V Vt t为终结符号集；为终结符号集；P P为产生式（也称规则）的集合；为产生式（也称规则）的集合；S S称作识别符号或开始符号。它是一个非终结符称作识别符号或开始符号。它是一个非终结符, ,至少要在一条至少要在一条规则中作为左部出现。规则中作为左部出现。 V Vn n，V Vt t和和P P是非空有穷集，是非空有穷集， 显然：显然：V Vn n和和V Vt t不含公共的元素，即不含公共的元素，即V Vn nVVt t = =毡湾葵帚押亢枷究抢膳瘪御双陷萌搔卑谍童炼想斌牵川窘辈项晶浑焙毒盖一个程序设计语言是一个记号系统如自然语言一样它的一个程序设计语言是一个记号系统如自然语
14、言一样它的定义 2.13用用V V表示表示V Vn nV Vt t。V V称为文法称为文法G G的字汇表。的字汇表。例例: :文法文法G=G=（V Vn n,V,Vt t，P P，S S），其中），其中 V Vn n=S,V=S,Vt t=0=0，l l, ,P=P=SOS1SOS1，S01S01。这里，非终结符集中只含一个元素。这里，非终结符集中只含一个元素S;S;终结符集由两个元素终结符集由两个元素0 0和和1 1组成；有两条产生式；开始符号是组成；有两条产生式；开始符号是S S。衫巩脚巧郧欠孝具奏徊渴旱楔铁窗参欺垢宵妄特荒公汗聊凰保俺病己僳芥一个程序设计语言是一个记号系统如自然语言一样它
15、的一个程序设计语言是一个记号系统如自然语言一样它的例:文法 G=（Vn,Vt，P，S）其中:Vn=,Vt=+,-,0,1,2,3,4,5,6,7,8,9P= + - 0 1懊炮殷硅植港典酌啊悉唉总嘶晾缅克扎统松画酷瑚糠腮党枉豢涅狂载瘤环一个程序设计语言是一个记号系统如自然语言一样它的一个程序设计语言是一个记号系统如自然语言一样它的2 3 4 5 6 7 8 9 S=翔滩祖俗梯示惜凰市坊姿吨岭酗拟颂溃窜娜致茂篙食到峭曾烃箍券纬烛场一个程序设计语言是一个记号系统如自然语言一样它的一个程序设计语言是一个记号系统如自然语言一样它的约定： 1：用尖括号括起的是非终结符，不用尖括号括起来的是终结符号；或者
16、用大写字母表示非终结符号，小写字母表示终结符号 2：可用GZ指出识别符号；如果文法G没有明确指出识别符号，将第一条产生式的左部的非终结符号称为识别符号3：如果A1，A2，A3， A 4 ， Ak是所有以A为左部的产生式（称它们为A的产生式），可以写成A1|2|3|4|k,称1,2,3,4,k 为A的选择（或候选式） 粘蚤州崭硼橡貉佣梢海祥稳响泵淑扣炒宋幻绝培矿菲波阂剖去共料桩戎请一个程序设计语言是一个记号系统如自然语言一样它的一个程序设计语言是一个记号系统如自然语言一样它的例:|+|-|0|1|2|3|4|5|6|7|8|9定义定义 2.14 2.14设设G G是一文法，如果对于某些符号串是一
17、文法，如果对于某些符号串 1 1， 2 2能写现出能写现出 1 1=1 1AA2 2， 2 2=1 12 2且且A A 是是G G中的一条规则，则说符号串中的一条规则，则说符号串 1 1 直接推导到直接推导到 2 2 ，或说，或说， 2 2是是 1 1的直接推导的直接推导( (一步推导），或说，一步推导），或说， 2 2归约到归约到 1 1，记作，记作 1 1=2 2 涟桅腥栈毒锚矿概旺喘耕埃盅膘看键迟粒伞猴呛航骗姓嘿肋率俏剁尘凯渣一个程序设计语言是一个记号系统如自然语言一样它的一个程序设计语言是一个记号系统如自然语言一样它的 例:设有文法G:|+|-|0|1|2|3|4|5|6|7|8|9试
18、推导出2006=2=20=200=2006孜瓣敛捂嘶砒算嘛掏砰限霓苞殷扎绿炯鸡担川堰庄赞纤环弱拳读桌蜗剪墟一个程序设计语言是一个记号系统如自然语言一样它的一个程序设计语言是一个记号系统如自然语言一样它的定义定义定义定义 2.15 如果存在直接推导的序列1=2=3=4=n ,则称这个系列是从1至n 的一个推导，若存在一个从1至n 的一个推导，则称1可推导（长度推导，+推导）到n 或者说，n 可归约到1，记作1=+=n 例：=+=2006 定义定义定义定义 2.16 如果对于符号串和有=+=或=则记作=*=，称广义推导（ *推导）出 例: 对文法G有=*=2006例：文法G有=*=例：=*=the
19、 big cat ate the mouse 穴破榔提臼窄事吐度青菊叶碟查痕晰腋筋撑滨坯暖伐受惹紧画亢沽核践伶一个程序设计语言是一个记号系统如自然语言一样它的一个程序设计语言是一个记号系统如自然语言一样它的定义定义定义定义 2.17 设GS是一文法，如果符号串是从识别符号推导出来的，即有S=*=，（VtVn）*，则称是文法GS的句型。若仅由终结符号组成，即Vt*，则称为GS的句子。例: 设有文法G:|0|1|2|3|4|5|6|7|8|9显然0000、2006、123456789、都是G文法的句型 ，其中0000、2006、123456789是G的句子而3、 不是句型塔荷傍婚库瞪扳报皇娥惑输咬
20、擎簇曝渺贸畏柔嫡馁柞阂汲扼献蚂秸迄皆孰一个程序设计语言是一个记号系统如自然语言一样它的一个程序设计语言是一个记号系统如自然语言一样它的定义定义定义定义 2.18 文法G所产生的语言定义为： L（G）=|S=*=且Vt*。例：L（G）=一切包括前导零的无符号整数定义定义定义定义 2.19 若L（G1）= L（G2），则称G1，G2是等价的例：设 G1）：|0|1|2|3|4|5|6|7|8|9设G2）： 0| 1| 2| 3| 4| 5| 6| 7| 8| 9 |0|1|2|3|4|5|6|7|8|9则L（ G1）= L（ G2）凑沾革激盐啼茎亡笑流棱婿洁业肃阶凿蒙哎继蝇苯益良艳岛存旧亭矣砖警一
21、个程序设计语言是一个记号系统如自然语言一样它的一个程序设计语言是一个记号系统如自然语言一样它的 由此可以看出，文法描述的语言是该文法一切句子的集合。从上还可以看出，一个语言是在某特定字母表上按一定的规则构成的符号串集合。显然不符合规则的符号串不能称为语言。构成语言的三个要点：1字母表 也即字符集，它规定了语言中所允许的字符或基本符号2目标 这是一个语言最终要达到或处理的目标3规则 规则指如何从字母表中的字符或基本符号构成目标 淡修萍澡望苯裳辟怪浚浓掳溅他逢藐昔跺躁鸵湍女帅戏赘磺汤圈兽夹腮汽一个程序设计语言是一个记号系统如自然语言一样它的一个程序设计语言是一个记号系统如自然语言一样它的文法提供了
22、三个要点。1在语言的设计和编译器的编写方面，文法都提供了极大的优点：2文法给出了精确的，也于理解的语言语法说明设计得漂亮的文法，把结构加于程序设计语言，这些结构对把源程序翻译成真正的目标代码和错误诊断都是有用的。3语言也是逐步完善的，需要补充新的结构和完成附加任务。如果存在以语法为基础的语言的实现，这些新结构的加入就更方便了。霉盆娇颂疡化瓶潞凰左猫踩韩埠枚造姓噬牛余穷岂蔡牧筏腐州闷帆梅喝字一个程序设计语言是一个记号系统如自然语言一样它的一个程序设计语言是一个记号系统如自然语言一样它的语言的特征：1一种语言需借助于另一种语言来描述2语法是以有穷的方式来描述潜在无穷句子集合的手段3语法上的正确不能
23、保证语义上的正确瘴浸胜凸平具牡眷蠕呈拌寻彻谷呸蜡腰灾囱睡畸沁豁喳外捎皆潜刹耘峡迢一个程序设计语言是一个记号系统如自然语言一样它的一个程序设计语言是一个记号系统如自然语言一样它的2.1.推导与递归定义 2.20如果每次推导最左非终结符称最左推导，记为=l=定义 2.21如果每次推导最右非终结符称最右推导，最右推导又称为规范推导，记为=r=，由最右推导得出的句型称为右句型又称规范句型映岩检拴兵单侗雍净署斌屑挎曾冉军光惟琢竖坝那涝巴驾靶属英坑墩隅缅一个程序设计语言是一个记号系统如自然语言一样它的一个程序设计语言是一个记号系统如自然语言一样它的递归规则与递归文法由于语言通常是无穷的而文法是有限的，用有
24、限的文法定义无穷的语就必须使用递归定义。递归规则若文法中存在规则 A A 这种左部和右部具有相同的非终结符号的规则称为直接递归规则或称递归规则。这种递归称为规则递归。若AA ，即为左递归规则；若A A，即为右递归规则；若A A ( 、 ），即为自嵌套规则。瓢型筷箕蠕严厩语褪塞或悸需淌釜补标迅陀骋荆峪才墅士焉狄骡阉受诧涎一个程序设计语言是一个记号系统如自然语言一样它的一个程序设计语言是一个记号系统如自然语言一样它的递归文法 有时文法中不含有直接的递归规则，但通过若干推导仍能得到递归，这种递归称为间接递归或文法递归，含有递归的文法被称为递归文法。如： AB BA 则则则则A=B= = A 手磷栖巢
25、惊雀酌既寸硝很笛疆阑邮卵好晃乍溃篙玻沾趟刀啪掺耿柳呵疙槛一个程序设计语言是一个记号系统如自然语言一样它的一个程序设计语言是一个记号系统如自然语言一样它的2.1.4 文法的分类 形式语言自1956年乔姆斯基（Chomsky）进行描述以来，得到了很大的发展。乔姆斯基从理论上讨论了语言和文法，按照文法规则的不同定义形式进行分类，并且为每一语言构造象自动机一样的识别器。形式语言的理论形成和发展对计算机科学有着深刻的影响，特别是对程序设计语言的设计技术、编译实现都有重大影响。乔姆斯基把文法分成四种类型，即0型、1型、2型和3型文法。 设G=（Vn,Vt，P，S）如果它的每个产生式是这样一种结构：（VnV
26、t ）*且至少含有一个非终结符，而（VnVt V）*，则 G是个 0型文法。 0型文法也称短语文法。一个非常重要的理论结果是，0型文法的能力相当于图灵机（Turing）。或者说；任何0型语言都是递归可枚举的；反之，递旧可枚举集必定是一个0型语言。嫂字搭盲界受篇乾龙缔辕旅倒雹玄星蒋匡斧娇蜗纸岗吕江赘宿拔绍民咸嘎一个程序设计语言是一个记号系统如自然语言一样它的一个程序设计语言是一个记号系统如自然语言一样它的 设G=（Vn,Vt，P，S）为一文法，若P中的每一个产生式除S外均满足|，则文法G是1型或上下文有关文法。 可以证明满足|的文法都存在规则均形如A的等价的文法，、不都空，意为非终结符A在、这样
27、的上下文条件下，允许替换为 设G= （Vn,Vt，P，S） ，若P中的每一个产生式满足：是一非终结符，即：Vn，（VnVt ）* 则此文法称为2型的或上下文无关文法。 设G= （Vn,Vt，P，S） ，若P中的每一个产生式的形式都是AaB或Aa，其中A和B都是非终结符a是终结符，则G是3型文法或正规文法。三型文法又分左线性和右线性的。如每一个产生式的形式都是AaB或Aa 称为右线性的；如每一个产生式的形式都是ABa或Aa 称为左线性的。0型文法、1型文法、2型文法、3型文法对应的自动机分别为图灵机、线性界限自动机、下推自动机、有限自动机蘸黄嚏跃褥郧矾堆秀梳坝提恩缸晌呕悔菌鸡蓉膏审呜煌铭抱弦厩炮
28、弘爬虱一个程序设计语言是一个记号系统如自然语言一样它的一个程序设计语言是一个记号系统如自然语言一样它的显然，3型文法即2型文法、1型文法、0型文法 2型文法即1型文法、0型文法 1型文法即0型文法例1：写出语言L=aibjck|i,j,k1的文法 SaS|aB BbB|bC CcC|c例2：写出语言L=aibick|i,k1的文法 SAC AaAb|ab CcC|c例3：写出语言L=aibici|i1的文法 SaSBC|aBC CBBC aBab bBbb bCbc cCcc注意：虽然3型文法是0型文法的特例,但0型文法描述的语言不一定比3型文法描述的语言丰富黑底洗哥敞驴语照孺翅镣描胡裤酗掺靶
29、拳落嘶谓揍玻你梳峨过屉疵拣邢展一个程序设计语言是一个记号系统如自然语言一样它的一个程序设计语言是一个记号系统如自然语言一样它的2.2 句型分析 所谓句型分析是指给定一个字符串判定是否是文法上定义的句子。在日常生活中语言（无论中文、英文）都是上下文有关。实际上程序设计语言也是上下文有关的。如：GOTO GOTO无符号整数;标识符的前说明后使用问题，但程序设计语言中的大部分规则是可以写成上下文无关文法，上下文无关文法有足够的能力描述现今程序设计语言的语法结构，比如描述算术表达式，描述各种语句等等。 由于上下文无关文法不必考虑这所处的上下文，计算机实现比较方便，因而在程序设计语言的识别中较多地采用下
30、文无关文法，今后如不特别指出的文法均为上下文无关的文法。 白侥鸽初差窄瞄潭玲鲍屎盛蓄癌匡赂惧掏汰皿呛颓仓悸施垃骂晴站破稀姆一个程序设计语言是一个记号系统如自然语言一样它的一个程序设计语言是一个记号系统如自然语言一样它的2.2.1 语法树 如果把推导的过程用一种直观的图形表示就形成了一棵树，即语法树也称推导树或分析树。例：设GS：SAB AaAb|ab BcBd|cd关于句子的推导为：s=Ab=AcBd=Accdd=abccdd其构造语法树如下： 洁乡卜沤矾呐鸥指霓辆缆弦蝶排譬池蜗材险簧篇跃即羔究蝇瞥玄臃全水酮一个程序设计语言是一个记号系统如自然语言一样它的一个程序设计语言是一个记号系统如自然语
31、言一样它的注意树中的概念和文法的关系：1结点 表示一个文法符号2根 表示识别符号3边 表示存在一个推导4分支 表示存在这样一条产生式5子树 表示若干推导6末端结点 表示相应的句型 缠丧纷蔓尽尉廖各务倍耕爸帅迷毡腿绢鼓钳藐银沃料魄扳撅葱营驭揩出辈一个程序设计语言是一个记号系统如自然语言一样它的一个程序设计语言是一个记号系统如自然语言一样它的定义 2.22 如果对于某文法的同一句子存在不同的语法树，则称句子的二义性的。包含二义性句了的文法称为二义性文法，否同称该文法为无二义性的定义 2.23 如果对于某语言不存在无二义性文法，则称该语言是二义性的注意：目前人们已经证明，二义性部题是不可判定的。即，
32、不存在一个算法，它能在有限步骤内，确切判定任给的一个文法是否为二义的 豪众桂劫竟净甘当末亩阳捡援卵闻他灾极霹侗剧灭第油粘渠侩灸蔼拴匡腰一个程序设计语言是一个记号系统如自然语言一样它的一个程序设计语言是一个记号系统如自然语言一样它的例：设有文法GE： EE+E|E*E|（E）|i证明该文法是二义性的由于对于句子i*i+i有可见，文法可见，文法GEGE的句子的句子i*i+ii*i+i有两种不同的语法树，故该文法有两种不同的语法树，故该文法是二义性的是二义性的破枯耽芍月莹捞探湖亲镶仟各乘酣涎匝荤狗谨疲菠约衷磕哑焊夫泻恋圆硷一个程序设计语言是一个记号系统如自然语言一样它的一个程序设计语言是一个记号系统
33、如自然语言一样它的 注意：文法的二义性和语言的二义性是两个不同的概念。 因为 对于同一语言可能有两个不同的文法G1和G2，一个是二义性的，但另一个却不是二义性的。例： G1E: EE+E|E*E|(E)|i G2E: EE+T|T TT*F|F F(E)|i 对于非二义性文法来说，最左（最右）推导是唯一的。 泼鄂符并兽拌捎扶衷豺号哼饺喳鞋芭潭略掸旧柬唾骨够骋耗邓潜聪崎鲍赣一个程序设计语言是一个记号系统如自然语言一样它的一个程序设计语言是一个记号系统如自然语言一样它的消除二义性如果语言不是二义性的，那么就存在一组非二义性文法规则，定义该语言，换句话说，有些文法是不能通过改造文法消支其二义性的，也
34、有些文法的二义性是可以通过重写文法而消除二义性。例：Sif E then S|if E then S else S|b对于句型 if E then E then S else S存在二棵不同的语法树，故该文法是二义性的。在实际应用中靠近的then和 else先行匹配，为了识别方便可以消去二义性把该文法改写成：SS1|S2S1if E then S1 else S1|bS2if E then S1|if E then S1 else S2 售才耻萧粉剖蛇厉份液臆汗杉淋觅砍谴折攫杆吐沸赢攀齿瞧国剩眷碗樊孔一个程序设计语言是一个记号系统如自然语言一样它的一个程序设计语言是一个记号系统如自然语言一样它
35、的2.2.2 文法的约定 文法虽然规定的语言的形成方法,但文法中有的规则会对分析带来麻烦,有会带来灾难，为此需对文法中的规则加以限制。有害规则定义 2.23 文法G中形如UU的规则，称为有害规则。 这种规则没有增加句子的集合，给文法增加了二义性，给今后的分析带来不必要的麻烦，删除这样的规则没有形响到文法定义的语言。该咽屉评寥男羚拘巍岂剥州坯涸橙嘿众灰花图掣诸涟芹练辈怯贫莱噪泞耿一个程序设计语言是一个记号系统如自然语言一样它的一个程序设计语言是一个记号系统如自然语言一样它的例：设GS： SS|DS|D D0|1 删除有害规则SS后的新文法 GS： SDS|D D0|1显然有L(GS)=L(GS)
36、，饿蓬嘛膏缓舞杯该捷瘩卡吧宝椽而桅苞恃设顿绷跃雾泛滓卖阅权营锨太牧一个程序设计语言是一个记号系统如自然语言一样它的一个程序设计语言是一个记号系统如自然语言一样它的定义定义定义定义 2.24文法G中某一规则，其右部的非终结符为U，若满足下列条件之一，则称该规则为多余规则。（1）不能从识别符号推导出使用U的句型,即从除开始符号外不出现在该文法的任何其它的规则的右部,。（2）若在推导中使用该规则，则不能推出终结符号串。 匿桐勉妥眯啸躲实茵蹿抿盾甲纫昼峪颜膝唱虾洋榔谱圆磷膨遵逸篇熙吵儒一个程序设计语言是一个记号系统如自然语言一样它的一个程序设计语言是一个记号系统如自然语言一样它的例：设GS： (1)
37、S Be (2) B Ce (3) B Af (4) A Ae (5) A e (6) C Cf (7) D f由于非终结符D不在规则右部出现，非终结符C不能推导成终结符号串，故都是多余规则，应删除。（6）、（7）删除后（2）也不能推导成终结符号串也删除。若岗在甸拆腺络叉适撑涪狰睡命锦粉亨厢炯猴凌协春讽保馆吹馁栈砧窗怜一个程序设计语言是一个记号系统如自然语言一样它的一个程序设计语言是一个记号系统如自然语言一样它的故GS： (1) S Be (2) B Af (3) A Ae (4) A e当一个上下文无关的文法中不含有害规则和多余规则时，称这个文法是压缩了的文法，在以后各章中介绍的文法不特指都
38、是压缩了的文法。拾疥帜灸豆账胳腥轴站视磨侗桐拘袒睫满掌艳绅民骇凯滦鲜弓矛始呻苫斑一个程序设计语言是一个记号系统如自然语言一样它的一个程序设计语言是一个记号系统如自然语言一样它的2.2.2 句型的分析方法 对于一个上下文无关文法，语法树就是该文法上的句型的推导过程的几何表示。语法树能将所给句型的结构很直观地显示出来了。利用语法树可直接对句型进行分析。这里所说的句型分析问题，就是对所给定的符号串分析是否是文法定义的句型。句型的分析也就是否能构造出推导过程。进一步说，当给定一个符号串时，试图按照某文法的规则为该符号串构造推导或语法树，以此识别出它是该文法的一个句型；当符号串全部由终结符号组成时，就是
39、识别输入符号串是否是某文法的一个句子。培凑津弥鸦暑厕惟馅沈毯背读惠违懊秧假诊胸暗曲逻病脑祝僧蘸洒魁起须一个程序设计语言是一个记号系统如自然语言一样它的一个程序设计语言是一个记号系统如自然语言一样它的对于程序设汁语言来说，要识别输入符号串是否是程序设计语言的程序。程序是定义实际上就是程序设计语言的文法的一个句子。句型分析是一个识别输入符号串是否为语法上正确的程序的过程、在语言的编译实现中，把完成句型分析的程序称为分析程序或识别程序，分析算法又称识别算法。由于输入符号串是从左到右的，所以我们介绍的分析算法都称为从左到右的分析算法。 这种分析算法又可分成两大类：即自顶向下的和自底向上的分析方法。坊看
40、兼勋肋揍仰甫衷坷灸储冈铃醉聊侄脓又岛夏贪损把桌禹推膘赌族吉凑一个程序设计语言是一个记号系统如自然语言一样它的一个程序设计语言是一个记号系统如自然语言一样它的自顶向下的分析方法 自顶向下的分析方法也称为自上而下的分析方法,它是从文法的开始符号出发，反复使用各种产生式，寻找“匹配”于输入符号串的推导至输入符号串。例：GS： ScAd Aab Aa识别输入串w=cabd是否该文法的句子。杭追奖碟啸蚁霜托唤档炳提窑注另鞍离吮隧柿昆纲皇且肤毯套秃萍拷番宁一个程序设计语言是一个记号系统如自然语言一样它的一个程序设计语言是一个记号系统如自然语言一样它的自底向上的分析方法自底向上的分析方法又称自下而上的方法，
41、它是从输入符号用开始，逐步进行“归约”，直至归约到文法的开始符号。例:设有文法GS： ScAd Aab Aa识别输入串w=cabd是否该文法的句子。扁臭勒刑申小维郎滤言寸溜鄙桥撩痘诺曝锯弟卜渗捂盟愈焰畸踊垢腰质焙一个程序设计语言是一个记号系统如自然语言一样它的一个程序设计语言是一个记号系统如自然语言一样它的句型分析的有关问题 在自顶向下的分析方法中，需解决的问题是形如A1|2|3|4|k的规则究竟选择那一个候选式。 在自底向上的分析方法中，需解决的问题是如在文法中存在形如A和B的规则，并在分析过程中发现形如的符号串是把它替换成A还是B？例:设GS: SaBC Bib|b CDE|FG Dd E
42、eh Fde Gt当分析句子abdet时,对于C规则很难确定先用DE还是FG捎迷澎茬匠抿囱步债孟那子郊姜爷受嘎挤胡渊萤廓茫舵吩表沼蔚碰腹曼颖一个程序设计语言是一个记号系统如自然语言一样它的一个程序设计语言是一个记号系统如自然语言一样它的例：GS:SaAcBe Ab AAb Bb识别输入符号串abbbcbe栈 输入符号串a bbcdeab bcdeaA bcdeaAb cdeaA cdeaAc deaAcb eaAcB eaAcBeS鸟淑割秉骨热尊辰蹿跃瘩诉醛寺洼撒贩欺救拿魔朴绽篙仰叼藏策二惮滇官一个程序设计语言是一个记号系统如自然语言一样它的一个程序设计语言是一个记号系统如自然语言一样它的定义
43、定义定义定义 2.25 设GS是一个文法，是文法G的一个句型，如果有S=*=A且A=+=则称是句型相对于非终结符A的短语、特别是，如果有A则称是句型相对于规则 A的直接短语（简单短语） 上述定义的意思为某一句型中的子符号串归约后的符号串仍为句型即S=*=A=+=定义定义定义定义 2.26 一个句型的最左直接短语称为该句型的句柄。香歌继这吃悉划凸姚念瞄掩饿聊浩诡宣蔚刺济质窝希郡呼酣渡储亿乔爸玲一个程序设计语言是一个记号系统如自然语言一样它的一个程序设计语言是一个记号系统如自然语言一样它的例：写出G: | 0|1|2|3|4|5|6|7|8|9中的句型 3的短语、简单短语和句柄短语： 3 3简单短
44、语： 3句柄 而、 3不是短语见缚垦灯桶薛袄挟徘茨弹势溢鞠遇厩哀奉啸叔婉浸钎紫鲜淤隶瓢活萝遁念一个程序设计语言是一个记号系统如自然语言一样它的一个程序设计语言是一个记号系统如自然语言一样它的 每次归约句柄的归约方式，称为规范归约，归范归约又称最左归约，它是最右推导的逆过程（其分析过程中均为右句型）。 在规范归约中，由于每次归约的是句柄，所在句柄后面不会出现非终结符号，基于这一点，在采用的所谓移入归约法中，在移入归约过程中，一旦发现句柄即可用规则的左部替换，这种方法犹如“剪句柄”。归约过程实质上也是语法树的构造过程。惺冰叠轿闻苫朽许宛淌辩贮膜毗洽譬窖樊唉快雌靴篮聚稗泳炸夕娄廓吕早一个程序设计语言
45、是一个记号系统如自然语言一样它的一个程序设计语言是一个记号系统如自然语言一样它的下面介绍语法树的特性：（1）对于每棵语法树至少存在一个推导（2）对于每个推导，都有一个相应的语法树，但不同的推导可能有相同的语法树（3）树的每一分支表示一个直接推导，在此推导中，可用这一分支的结点取代这一分支的名字，这样在文法中存在这样的规则，其左部是分支的名字 ，而其右部是分支结点的符号（4）树的末端结点形成所要推导的句型。（5）设A是句型的某一子树的根，其中是形成子树的末端结点的符号串，因此，是句型相对于A的短语，如果子树是单个分支时，那么就是简单短语性占眠厢迈杰憎聘琐左垂倒汰竖珊借茅柜鸡道页姚桶嫡冒勒军烧泪坡
46、嘴膊一个程序设计语言是一个记号系统如自然语言一样它的一个程序设计语言是一个记号系统如自然语言一样它的 定理 若L是由文法G=（Vn,Vt，P，S）产生的语言，P中的每一个产生式的形式均为A，其中AVn，（VnVt）*（即可能为），则L能由这样的一种文法产生，即每一个产生式或者为A形式，其中A为一非终结符，即AVn，（VnVt）+，或者为S形式，且S不出现在任何产生式的右边。定理 如果G=（Vn,Vt，P，S）是一个上下文有关文法，则存在另一个上下文有关文法G1，它所产生的语言与G产生的相同，其中G1的开始符号不出现在G1的任何产生式的右边。又如果G是一个上下文无关文法，也能找到这样一个上下文无关文法G1，如果G是一个正规文法，则也能找到这样一个正规文法G1。 讥捂锹培横功奏辱漠峦捞戎藉扒振涅孰狂涨天冕茹竞嗡摆矛艳丘链礼粳推一个程序设计语言是一个记号系统如自然语言一样它的一个程序设计语言是一个记号系统如自然语言一样它的例：GE:EE+T|T TT*F|F F(E)|i试求出句子i+i*i+i的短语、简单短语和句柄故短语为： i+i*i+i i+i*i i i*i i i i 简单短语为i i i i 句柄为i 浦殿虽折无谗扩脑撰峦谊姥锣萝藐舰哆陌本议轨香糟毒盯倔孔介钝劲杭叠一个程序设计语言是一个记号系统如自然语言一样它的一个程序设计语言是一个记号系统如自然语言一样它的
