《第二章文法和语言21文法的基本概念一个程序设计语言是一个记培训教材》由会员分享，可在线阅读，更多相关《第二章文法和语言21文法的基本概念一个程序设计语言是一个记培训教材（56页珍藏版）》请在金锄头文库上搜索。
1、第二章 文法和语言 2.1 文法的基本概念 一个程序设计语言是一个记号系统，如自然语言一样，它的完整的定义应包括语法和语义两方面。所谓一个语言的语法是指一组规则，用它可以形成和产生一个合适的程序，目前在程序设计语言的识别中广泛使用的是上下文无关的文法。在这理主要介绍文法和语言的概念。,例：设有文法： the big ate|caught mouse|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 m
2、ouse,定义 2.3 不包含任何字符串的空符号串用表示 定义 2.4 符号串x的长度，即符号串x中的字符用|x|表示(读作x的长度) 例：|abc|=3 |a|=1 |=0 定义 2.5 设非空符号串u=xvy,其中v,则称v为u的子串,若|u| |v|则称v为u的真子串,定义 2.6 如果z=xy是一个符号串，则x是z和头，而y是z的尾。如果x是非空的，那么y是固有尾；同样如果y非空，那么x是固有头。 例：设z=abc，那么z的头是,a，ab，abc。除abc外，其它都是固有头。z的尾是,c，bc，abc。z的固有尾是,c，bc,定义 2.7 设x、y 是同一字母表上的两个符号串，把y的符
3、号写在X的符号之后得到的符号串，称为的连接。记为xy 例：x=ab，y=wabu 则 z=xy=abwabu 显然：|x|+|y|=|z| 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为该字母表上的符号串集合。 注意：、和（表示空集）的区别,定义 2.10 两个符号串集合A和B的乘积AB定义为： AB=xy|xA且yB 例：设A=a,bc，B=b,c,da则集合AB=ab,ac,ada,b
4、cb,bcc,bcda。 注意：由于x=x=x 因此A=A=A ，但A=A= 则： A0= A1=A A2=AA An=An-1A=AAn-1（n0）,显然： 1是字母表中的所有单个字符组成的字符串 2是所有由字母表中二个的字符组成的字符串 3是所有由字母表中三个的字符组成的字符串 n是所有由字母表中长度为n的字符串集合 定义 2.11 A的闭包 A*=A0A1A2 A的正闭包 A+= A1A2A3 显然A+=AA*=A*A A*=A0A+,由于一个字母表上的正闭包包含了该字母表中的符号所能组成的一切符号串，而语言是该字母表上的某些符号串的集合，因此，某个字母表上的语言是这个字母表上的正闭包的
5、子集，而且通常是真子集。 例：若=0,1,则*=,0,1，00,01，10,11,000，001，010, 例：令L=A,B,C,Z,a,b, ,z,D=0,1, 9 1.LD 2.LD 3.L4 4. L(LD)* 5. D+ 6.D+L*则分别代表什么集合？ 1.字母或数字（包括）的集合 2.由字母开头后面跟一个数字的集合 3.由个字母组成的字符串的集合 4.由字母开头后面是字母数字（可省略）的集合 5.数字串集合 6.数字串和字母串集合（包括）,约定：当对符号串z=xy的头感兴趣而对其余部分不感兴趣时，可以采用省略写法：z=x；如果只是为了强调x在符号串z中的某处出现，则可表示为:z=x
6、；如果只是为了强调x在符号串z中的末尾出现，则可表示为:z=x；,2.1.2 文法和语言的形式定义 语言是字母表上的某些符号串集合，在这集合中的每个符号串都是按一定规则生成的。其规则最常用的是重写规则（又称产生式或生成式），它是形如或：=（，）的有序对，（读作定义为），其中称为规则的左部，称为规则的右部。,定义 2.12 文法G定义为四元组（Vn,Vt，P，S）。 其中: Vn为非终结符号（或语法实体，或变量）集；Vt为终结符号集； P为产生式（也称规则）的集合； S称作识别符号或开始符号。它是一个非终结符,至少要在一条规则中作为左部出现。 Vn，Vt和P是非空有穷集， 显然：Vn和Vt不含公
7、共的元素，即VnVt =,定义 2.13 用V表示VnVt。V称为文法G的字汇表。 例:文法G=（Vn,Vt，P，S），其中 Vn=S,Vt=0，l, P=SOS1，S01。这里，非终结符集中只含一个元素S;终结符集由两个元素0和1组成；有两条产生式；开始符号是S。,例:文法 G=（Vn,Vt，P，S） 其中: Vn=, Vt=+,-,0,1,2,3,4,5,6,7,8,9 P= + - 0 1,2 3 4 5 6 7 8 9 S=,约定： 1：用尖括号括起的是非终结符，不用尖括号括起来的是终结符号；或者用大写字母表示非终结符号，小写字母表示终结符号 2：可用GZ指出识别符号；如果文法G没有明
8、确指出识别符号，将第一条产生式的左部的非终结符号称为识别符号 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 设G是一文法，如果对于某些符号串1，2能写现出1=1A2，2=12且A 是G中的一条规则，则说符号串1 直接推导到2 ，或说，2是1的直接推导(一步推导），或说，2归约到1，记作1=2,例:设有文法G: | +|- | 0|1|2|3|4|5|6|7|8|9 试推导出2006 = =2=20=
9、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 big cat ate the mouse,定义 2.17 设GS是一文法，如果符号串是从识别符号推导出来的，即有S=*=，（VtVn）*，则称是文法GS的句型。若仅由终结符号组成，即Vt*，则称为GS
10、的句子。 例: 设有文法G: | 0|1|2|3|4|5|6|7|8|9 显然0000、2006、123456789、都是G文法的句型 ，其中0000、2006、123456789是G的句子 而3、 不是句型,定义 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）
11、,由此可以看出，文法描述的语言是该文法一切句子的集合。 从上还可以看出，一个语言是在某特定字母表上按一定的规则构成的符号串集合。显然不符合规则的符号串不能称为语言。 构成语言的三个要点： 1字母表 也即字符集，它规定了语言中所允许的字符或基本符号 2目标 这是一个语言最终要达到或处理的目标 3规则 规则指如何从字母表中的字符或基本符号构成目标,文法提供了三个要点。 1在语言的设计和编译器的编写方面，文法都提供了极大的优点： 2文法给出了精确的，也于理解的语言语法说明 设计得漂亮的文法，把结构加于程序设计语言，这些结构对把源程序翻译成真正的目标代码和错误诊断都是有用的。 3语言也是逐步完善的，需
12、要补充新的结构和完成附加任务。如果存在以语法为基础的语言的实现，这些新结构的加入就更方便了。,语言的特征： 1一种语言需借助于另一种语言来描述 2语法是以有穷的方式来描述潜在无穷句子集合的手段 3语法上的正确不能保证语义上的正确,2.1.推导与递归 定义 2.20 如果每次推导最左非终结符称最左推导，记为=l= 定义 2.21 如果每次推导最右非终结符称最右推导，最右推导又称为规范推导，记为=r=，由最右推导得出的句型称为右句型又称规范句型,递归规则与递归文法 由于语言通常是无穷的而文法是有限的，用有限的文法定义无穷的语就必须使用递归定义。 递归规则 若文法中存在规则 AA 这种左部和右部具有
13、相同的非终结符号的规则称为直接递归规则或称递归规则。这种递归称为规则递归。 若AA，即为左递归规则； 若AA，即为右递归规则； 若AA(、），即为自嵌套规则。,递归文法 有时文法中不含有直接的递归规则，但通过若干推导仍能得到递归，这种递归称为间接递归或文法递归，含有递归的文法被称为递归文法。 如： AB BA 则A=B= A,2.1.4 文法的分类 形式语言自1956年乔姆斯基（Chomsky）进行描述以来，得到了很大的发展。乔姆斯基从理论上讨论了语言和文法，按照文法规则的不同定义形式进行分类，并且为每一语言构造象自动机一样的识别器。形式语言的理论形成和发展对计算机科学有着深刻的影响，特别是对
14、程序设计语言的设计技术、编译实现都有重大影响。 乔姆斯基把文法分成四种类型，即0型、1型、2型和3型文法。 设G=（Vn,Vt，P，S）如果它的每个产生式是这样一种结构：（VnVt ）*且至少含有一个非终结符，而（VnVt V）*，则 G是个 0型文法。 0型文法也称短语文法。一个非常重要的理论结果是，0型文法的能力相当于图灵机 （Turing）。或者说；任何0型语言都是递归可枚举的；反之，递旧可枚举集必定是一个0型语言。,设G=（Vn,Vt，P，S）为一文法，若P中的每一个产生式除S外均满足|，则文法G是1型或上下文有关文法。 可以证明满足|的文法都存在规则均形如A的等价的文法，、不都空，意
15、为非终结符A在、这样的上下文条件下，允许替换为 设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型文法对应的自动机分别为图灵机、线性界限自动机、下推自动机、有限自动机,显然，3型文法即2型文法、1型文法
16、、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型文法描述的语言丰富,2.2 句型分析 所谓句型分析是指给定一个字符串判定是否是文法上定义的句子。在日常生活中语言（无论中文、英文）都是上下文有关。实际上程序设计语言也是上下文有关的。如：GOTO GOTO无符号整数;标识符的前说明后使用问题，但程序设计语言中的大部分规则是可以写成上下文无关文法，上下文无关文法有足够的能力描述现今程序设计语言的语法结构，比如描述算术表达式，描述各种语句等等。 由于上下文无关文法不必
