第2章+文法和语言

1、文法和语言文法和语言n一个程序设计语言是一个记号系统，它的完整一个程序设计语言是一个记号系统，它的完整定义应包括两个方面定义应包括两个方面:q语法语法指一组规则，用它可以形成和产生一个合适的程序。q语义语义n静态语义是一系列限定规则，并确定哪些合乎语法的程序是合适的；n动态语义也称作运行语义或执行语义，表明程序要做些什么，要计算什么。n文法是阐明语法的一个工具文法是阐明语法的一个工具2. 2 符号和符号串符号和符号串n字母表字母表 q字母表是元素的非空有穷集合字母表是元素的非空有穷集合n符号符号q字母表中的元素称为符号字母表中的元素称为符号n符号串符号串q由符号组成的任何有穷序列由符号组成的任

2、何有穷序列q符号串符号串x的长度：的长度：x所包含的符号个数，记作所包含的符号个数，记作|x|q空符号串空符号串 n符号串的头、尾、固有头、固有尾符号串的头、尾、固有头、固有尾n符号串的连接符号串的连接q设设x和和y是符号串，它们的连接是符号串，它们的连接xy是把是把y的符号写在的符号写在x的符号之后得到的符号串。的符号之后得到的符号串。n符号串的方幂符号串的方幂q设设x是符号串，把是符号串，把x自身连接自身连接n次得到符号串次得到符号串z，即即z=xx.xx，称为符号串称为符号串x的方幂。的方幂。0=, n =n-1 =n-1（n0）n符号串集合及其运算符号串集合及其运算q若集合若集合A中的

3、一切元素都是字母表上的符号串，则中的一切元素都是字母表上的符号串，则称称A为该字母表上的符号串集合。为该字母表上的符号串集合。q合并：字符串集合合并：字符串集合A和和B的合并的合并AB=|A或或B。q乘积：字符串集合乘积：字符串集合A和和B的乘积的乘积AB=|A且且B。显然显然A=A=A。q幂：幂：An=An-1A=AAn-1（n0），），并规定并规定A0=。q正闭包：正闭包：A+ =A1A2An。q闭包：闭包：A*=A0A+。显然显然*=012n 。*表示表示上的所有有穷长的串的集合上的所有有穷长的串的集合2.3 文法和语言的形式定义文法和语言的形式定义n引例引例1 =a, A=an|n1n

4、引例引例2 =a,b, A=anbm|n,m1n引例引例3 =a,b, A=anbn|n1n定义定义2.1-文法文法文法文法G定义为四元组定义为四元组(VN，VT，P，S)。其中其中VN: 非终结符的非空有穷集；非终结符的非空有穷集；VT: 终结符的非空有穷集；终结符的非空有穷集；P: 产生式（也称规则）的非空有穷集；产生式（也称规则）的非空有穷集； S: 开始符号，它是一个非终结符，至少要开始符号，它是一个非终结符，至少要在一条规则中作为左部出现。在一条规则中作为左部出现。通常用通常用V表示表示VN VT，V称为文法称为文法G的的文法文法符号集符号集。n例例1=a,b, A=ambn|mn0

5、n例例2=a,b, A=wwR|wR是是w的反向串的反向串n例例3GS:SaSBE|aBEEB BEaB abbB bbbE beeE een定义定义2.2-直接推导、直接归约直接推导、直接归约设设 是文法是文法G=(VN ，VT，P，S)的规则，的规则， 和和 是是V*中的任意符号串。若有符号串中的任意符号串。若有符号串v，w满满足：足：v=， w=，则说则说 v（应用规则应用规则 ）直接产生）直接产生w，或说或说w是是v的直接推导，或说的直接推导，或说w直接归约到直接归约到v，记作记作 vw。n定义定义2.3 -推导推导若存在若存在v w0 w1 . wn=w (n0)，则则说说v推导出推

6、导出w，或说或说w归约到归约到v，记为记为 v w。n定义定义2.4-星推导星推导若有若有v w，或或v=w，则记为则记为v w。*n最左（最右）推导最左（最右）推导q如果在推导的任何一步如果在推导的任何一步 ，其中，其中 V* ，都是，都是对对 中的最左（最右）非终结符进行替换，则称这中的最左（最右）非终结符进行替换，则称这种推导为最左（最右）推导种推导为最左（最右）推导n规范推导规范推导q在形式语言中，最右推导常被称为规范推导。在形式语言中，最右推导常被称为规范推导。n定义定义2.5-句型、句子句型、句子设设有文法有文法G。若若S x，则称则称x是文法是文法G的句型；的句型；若若S x，且

7、且xVT*，则称则称x是文法是文法G的句子。的句子。n规范句型规范句型q由规范推导所得的句型称为规范句型。由规范推导所得的句型称为规范句型。*n定义定义2.6- 语言语言由文法由文法G生成的语言记为生成的语言记为L(G),它是文法它是文法G的一切的一切句子的集合。句子的集合。n定义定义2.7-文法等价文法等价若若L(G1) = L(G2)，则称文法则称文法G1和和G2是等价的。是等价的。2.4 文法的类型文法的类型nChomsky分类分类q0型文法型文法 短语文法短语文法对任一产生式对任一产生式，都有都有(VNVT)+且至少含有一个且至少含有一个非终结符，非终结符， (VNVT)*q1型文法型

8、文法-上下文有关文法（上下文有关文法（CSG） 对任一产生式对任一产生式，都有都有|， 仅仅仅仅 S除外除外q2型文法型文法-上下文无关文法（上下文无关文法（CFG） 对任一产生式对任一产生式，都有都有VN ， (VNVT)*q3型文法型文法-正规文法（正规文法（RG） 任一产生式任一产生式的形式都为的形式都为AaB或或Aa，其中其中AVN ，BVN ，aVT2型文法型文法1型文法型文法0型文法3型文法2型文法型文法1型文法型文法2型文法型文法1型文法型文法2型文法型文法1型文法型文法0型文法3型文法n0型文法产生的语言称为型文法产生的语言称为0型语言型语言1型文法或上下文有关文法产生的语言称

9、为型文法或上下文有关文法产生的语言称为1型语言或上下文有关语言型语言或上下文有关语言2型文法或上下文无关文法产生的语言称为型文法或上下文无关文法产生的语言称为2型语言或上下文无关语言型语言或上下文无关语言3型文法或正规文法产生的语言称为型文法或正规文法产生的语言称为3型语言型语言正则规语言正则规语言n例例给出一个正规文法给出一个正规文法G，使使L(G)=anbm|n,m12.5 上下文无关文法及其语法树上下文无关文法及其语法树n引例引例GS:SaAS | aASbA | SS | ba写出写出aabbaa的最左推导和最右推的最左推导和最右推导。导。n给定文法给定文法G=( VN,VT,P,S)

10、，对于对于G的任何句型的任何句型都能够造与之关联的语法树。这棵树满足下列都能够造与之关联的语法树。这棵树满足下列4个条件：个条件：q每个结点都有一个标记，此标记是每个结点都有一个标记，此标记是V的一个符号。的一个符号。q根的标记是根的标记是S。q若一结点若一结点n至少有一个它自己除外的子孙，并且有至少有一个它自己除外的子孙，并且有标记标记A，则肯定则肯定AVN。q如果结点如果结点n有标记有标记A,其直接子孙结点从左到右的次其直接子孙结点从左到右的次序是序是n1，n2，nk，其标记分别为其标记分别为A1，A2，Ak，那么那么AA1A2Ak一定是一定是P中的一个产生式。中的一个产生式。n一棵语法树

11、表示了一个句型的种种可能的一棵语法树表示了一个句型的种种可能的(但未但未必是所有的必是所有的)不同推导过程，包括最左不同推导过程，包括最左(最右最右)推推导。从左到右读出推导树的叶子标记连接成的导。从左到右读出推导树的叶子标记连接成的文法符号串为文法符号串为G的的句型。句型。n若一个文法存在某个句子对应两棵不同的语法若一个文法存在某个句子对应两棵不同的语法树，则称这个文法是二义的。或者说，若一个树，则称这个文法是二义的。或者说，若一个文法存在某个句子有两个不同的最左（右）推文法存在某个句子有两个不同的最左（右）推导，则称这个文法是二义的。导，则称这个文法是二义的。n例例1GE:EE+E|E*E

12、|(E)|In例例2GE:E-EE|-E|a|b|cn文法的二义性和语言的二义性是两个不同的概文法的二义性和语言的二义性是两个不同的概念。因为可能有两个不同的文法念。因为可能有两个不同的文法G和和G，其中其中G是二义的，但是却有是二义的，但是却有L(G)=L(G)，也就是说也就是说，这两个文法所产生的语言是相同的。，这两个文法所产生的语言是相同的。2.6 句型的分析句型的分析n句型分析句型分析q句型分析就是识别一个符号串是否为某文法的句型，句型分析就是识别一个符号串是否为某文法的句型，是某个推导的构造过程。是某个推导的构造过程。n分析程序（识别程序）分析程序（识别程序）q在语言的编译实现中，把

13、完成句型分析的程序称为分在语言的编译实现中，把完成句型分析的程序称为分析程序或识别程序。析程序或识别程序。n分析算法分析算法q自上而下分析法自上而下分析法q自下而上分析法自下而上分析法考虑文法考虑文法GS：S cAdA abA a识别输入串识别输入串w=cabd是否该文法的句子。是否该文法的句子。q自上而下分析法的主要问题：自上而下分析法的主要问题：假定要被替换的最左非终结符是假定要被替换的最左非终结符是V且有且有n条产生式：条产生式：V 1 | 2 | n，那么如何确定用哪个右部去替那么如何确定用哪个右部去替换换V？q自下而上分析法的关键问题：自下而上分析法的关键问题：从当前串中选择一个可以

14、归约到某个非终结符的子从当前串中选择一个可以归约到某个非终结符的子串（称为串（称为“可归约串可归约串”）。）。n定义定义3.8-短语，直接短语，句柄短语，直接短语，句柄设文法设文法GS如果有如果有S A且且A ，则称则称是句型是句型相相对于非终结符对于非终结符A的短语。的短语。如果有如果有A ，则称则称是句型是句型相对于非终相对于非终结符结符A的直接短语（简单短语）。的直接短语（简单短语）。一个句型的最左直接短语称为该句型的句柄一个句型的最左直接短语称为该句型的句柄。*n例例设文法设文法GE：EE+T|TEE+T|TTTTT* *F|FF|FF(E)|iF(E)|i求句型求句型i i* *i+ii+i的短语、直接短语和句柄的短语、直接短语和句柄2.7 有关文法实用中的一些说明有关文法实用中的一些说明n在实用中，我们将限制文法中不得含有有害规则在实用中，我们将限制文法中不得含有有害规则和多余规则。和多余规则。q有害规则有害规则是形如是形如 U U的产生式。的产生式。q多余规则多余规则是文法中连一个句子