编译原理第03章文法和语言.ppt

1,编译原理 文法和语言,华东交通大学 软件学院网络工程教研室 万仲保 Tel:7046821E-mail:,2,第三章 文法和语言,本章目的 为语言的语法描述寻求工具 工具要对程序设计语言给出精确无二义的语法描述。（严谨、简洁、易读） 形式工具-形式语言抽象地定义为一个数学系统。“形式”是指这样的事实：语言的所有规则只以什麽符号串能出现的方式来陈述。,3,3.1 文法的直观概念 3.2 符号和符号串 3.3 文法和语言的形式定义 3.4 文法的类型 3.5 上下文无关文法及其语法树 3.6 句型分析 3.7 实用说明,第三章 文法和语言,4,文法的直观概念,一个程序设计语言是一个记号系统，如同自然语言一样，它的完整的定义应包括语法和语义两个方面。所谓一个语言的语法是指一组规则，用它可以形成和产生一个合适的程序。目前广泛使用的手段是上下文无关文法，即用上下文无关文法作为程序设计语言语法的描述工具。语法只是定义什么样的符号序列是合法的，与这些符号的含义毫无关系 阐明语法的一个工具是文法，这是形式语言理论的基本概念之一。 示例：汉语句子的描述 语言概述,5,汉语句子的描述,语法规则定义 字符串的判断,6,语法规则定义,句子=主语谓语 主语=代词名词 代词=我你他 名词=王明大学生工人英语 谓语=动词直接宾语 动词=是学习 直接宾语=代词名词,7,字符串的判断,有了一组规则以后，按照如下方式用它们导出句子：开始去找=左端的带有句子的规则并把它由=右端的符号串代替，这个动作表示成： 句子 主语谓语， 然后在得到的串主语谓语中，选取主语或谓语，再用相应规则的=右端代替之。比如，选取了主语，并采用规则主语=代词， 那么得到：主语谓语 代词谓语， 重复做下去。 句子：“我是大学生”的全部动作过程是： 句子主语谓语 代词谓语 我谓语我动词直接宾语 我是直接宾语我是名词我是大学生,8,字符串的判断,“我是大学生”的构成符合上述规则，而“我大学生是”不符合上述规则，我们说它不是句子。这些规则成为我们判别句子结构合法与否的依据，换句话说，这些规则看成是一种元语言，用它描述汉语。这里仅仅涉及汉语句子的结构描述。其中一种描述元语言称为文法。,9,符号和符号串,定义： 符号：可以相互区别的记号（元素）。 字母表（）：符号（元素）的非空有穷集合。 符号串：由字母表中的符号组成的任何有穷序列称为该字母表上的符号串。 1.空符号串(没有符号的符号串)是上的符号串 2.若x是上的符号串,a是的元素,则xa是上的符号串 3. y是上的符号串,当且仅当它可以由1和2导出。 例如： =a,b ,a,b,aa,ab,aabba都是上的符号串 符号串的运算,10,符号串的运算,既然将语言定义为一个集合，那么有关集合的运算也适合语言。即：设L是（上的）一个语言,M是（上的）一个语言，则语言L和M的并，交，差，补是一个语言。 符号串的头、尾、子串 符号串的长度 符号串的连接 符号串的方幂 符号串的集合,11,符号串的头、尾、子串,符号串s的头（前缀）：移走符号串s尾部的零个或多于零个符号得到的符号串。 如： b是符号串banana的一个前缀. 符号串s的尾（后缀）：删去符号串s头部的零个或多于零个符号得到的符号串。 如:nana是符号串banana的一个后缀. 符号串s的子串：从s中删去一个前缀和一个后缀得到的符号串。 如:ana是符号串banana的一个子串. 对于每个符号串s， s和两者都是符号串s的前缀，后缀和子串。 符号串s的真前缀，真后缀，真子串：任何非空符号串 x,相应地，是s的前缀，后缀或子串，并且 s x。,12,符号串中符号的个数。 符号串s的长度记为|s|。 的长度为0,符号串的长度,13,符号串的连接,设x、y是符号串，则x、y的连接是把y的符号写在x的符号之后得到的符号串xy 如 x=ab,y=cd 则 xy=abcd 有a = a,14,符号串的方幂,方幂：设x是符号串，把x自身连接n次得到的符号串z，即z=aaaa称为符号串x的方幂。写作z=an 示例： a1=a, a2=aa a0=,15,符号串集合,若集合A中所有元素都是某字母表上的符号串，则称A为字母表上的符号串集合。 两个符号串集合A和B的乘积定义为： AB =xy|xA且yB 若 集合A=ab,cde B = 0,1，则 AB =ab1,ab0,cde0,cde1 使用 * 表示上的所有有穷长符号串（包括）组成的集合。*称为的闭包。 上的除外的所有符号串组成的集合记为+ 。 +称为的正闭包。 * = 012n + = 12n * = + + =* = *,16,文法和语言的形式定义,文法和语言的形式定义 文法的定义 推导的定义 句型（子）的定义 语言的定义 文法等价的定义,17,语言概述,语言是由句子组成的集合，是由一组符号所构成的集合。 汉语-所有符合汉语语法的句子的全体 英语-所有符合英语语法的句子的全体 每个句子构成的规律 语言研究 每个句子的含义 每个句子和使用者的关系 每个程序构成的规律 研究程序设计语言 每个程序的含义 每个程序和使用者的关系 语法 Syntax 语言研究的三个方面 语义 Semantics 语用 Pragmatics,18,程序设计语言,研究程序设计语言 每个程序构成的规律 每个程序的含义 每个程序和使用者的关系 语言研究的三个方面 语法 Syntax 语义 Semantics 语用 Pragmatics,19,语言研究的三个方面,语法 - 表示构成语言句子的各个记号之间的组合规律 语义 - 表示各个记号的特定含义。（各个记号和记号所表示的对象之间的关系） 语用 -表示在各个记号所出现的行为中，它们的来源、使用和影响。 每种语言具有两个可识别的特性，即语言的形式和该形式相关联的意义。 语言的实例若在语法上是正确的，其相关联的意义可以从两个观点来看，其一是该句子的创立者所想要表示的意义，另一是接收者所检验到的意义。这两个意义并非总是一样的，前者称为语言的语义，后者是其语用意义。幽默、双关语和谜语就是利用这两方面意义间的差异。,20,文法的定义,文法G定义为四元组(VN，VT，P，S )其中VN为非终结符号(或语法实体，或变量)集；VT为终结符号集；P为产生式(也称规则)的集合；VN，VT和P是非空有穷集。S称作识别符号或开始符号，它是一个非终结符，至少要在一条产生式中作为左部出现。 VN和VT不含公共的元素，即VN VT = 通常用V表示VN VT ，称为文法G的字母表或字汇表。 规则，也称重写规则、产生式或生成式，是形如或=的(，)有序对，其中是字母表V的正闭包V+中的一个符号，是V*中的一个符号。称为规则的左部，称作规则的右部。 示例： 例3.1 例3.2,21,例3.1,文法G=（VN，VT，P，S），VN = S , VT = 0, 1 ，P= S0S1, S01 。这里，非终结符集中只含一个元素S；终结符集由两个元素0和1组成；有两条产生式；开始符号是S。,22,例3.2,文法G=(VN，VT，P，S) 其中VN=标识符，字母，数字VT=a,b,c,，x,y,z,0,1,，9 P =标识符字母 标识符标识符字母 标识符标识符数字 字母a 字母b 字母z 数字0 数字1 数字9 S =标识符 这里，使用尖括号“和“括起非终结符。,23,推导的定义,直接推导“”： 如是文法G=(Vn，VT，P，S)的规则(或说是P中的一产生式)， 和是V*中的任意符号，若有符号串v，w满足： v= ，w= 则说v(应用规则)直接产生w，或者说，w是v的直接推导，也可以说，w直接归约到v，记作v w。 如果存在直接推导的序列： 示例： 直接推导 多步推导,24,直接推导的示例,对于例3.1的文法G，可以给出直接推导的一些例子如下： v=0S1,w=0011， 直接推导：0S10011，使用的规则：S01，这里 =0，=1。 v=S,w=0S1， 直接推导：S0S1使用的规则：S0S1，这里 =，= v=0S1,w=00S11， 直接推导：0S100S11，使用的规则：S0S1，这里 =0，=1。 对于例3.2的文法G，直接推导的例子有： v=标识符，w=标识符字母， 直接推导：标识符 标识符字母， 使用的规则：标识符标识符字母，这里 = v=标识符字母数字，w=字母字母数字， 直接推导：标识符字母数字 字母字母数字， 使用的规则：标识符字母。这里 =， 字母数字。 v=abc数字，w=abc5， 直接推导：abc数字 abc5, 使用的规则：数字5，这里 =abc,=。,25,多步推导的示例,对例3.1的文法，存在直接推导序列 v=0S100S11000S11100001111=w， 即0S1 00001111，也可记作0S1 00001111 对例3.2的文法，存在直接推导序列 v=标识符标识符数字字母数字x数字x1=w， 即 x1，也可记作 x1。,26,句型(子)的定义,设GS 是一文法，如果符号串x是从识别符号推导出来的，即有S x，则称x是文法GS的句型。若x仅由终结符号组成， 即S x，xVT*，则称x为GS的句子。 例： S，0S1，000111都是例3.1的文法G的句型，其中000111是G的句子。 标识符字母，字母数字，a1等都是例3.2文法G的句型，其中a1是G的句子。,27,语言的定义,文法G所产生的语言定义为集合x|S x，其中S为文法识别符号，且xVT*。可用L(G)表示该集合。 从定义可以看出两点： 第一，符号串x可从识别符号推出，也即x是句型。 第二，x仅由终结符号组成，即x是文法G的句子。也就是说，文法描述的语言是该文法一切句子的集合。 例： 例3.1 G： S0S1， S01 L(G)=0n1n|n1 例3.3,28,例3.3,设G=(VN，VT，P，S)， VN=S,B,E，VT=a,b,e，P由下列产生式组成： (1) SaSBE (2) SaBE (3) EBBE (4) aBab (5) bBbb (6) bEbe (7) eEee 则L（G）= anbnen | n1 ,29,文法的等价,若L（G1）=L（G2），则称文法G1和G2是等价的。 示例：文法G1A：A0R A01 RA1与G2S：S0S1 S01等价。,30,文法的类型,乔姆斯基分类 示例： 例3.4 例3.5 乔姆斯基分类文法之间关系 对应于乔姆斯基分类文法的语言 文法和语言之间的关系,31,乔姆斯基对文法的分类,通过对产生式施加不同的限制，Chomsky（乔姆斯基）将文法分为四种类型： 0型文法：对文法G=(VN，VT，P，S)的任一产生式，都有(VNVT)*且至少含有一个非终结符，(VNVT)*。 1型文法（上下文有关文法） ：对文法G=(VN，VT，P，S)的任一产生式，都有|， 仅仅 S除外。 2型文法（上下文无关文法）：对文法G=(VN，VT，P，S)的任一产生式，都有VN ， (VNVT)* 。 3型文法（正规文法）：设G=(VN，VT，P，S)，若P中的每一个产生式的形式都是AaB或Aa，其中A和B都是非终结符，a是终结符。 3型文法G=(VN，VT，P，S)的P中的规则有两种形式：一种是前面定义的形式，即：AaB或Aa其中A，BVN ，aVT*，另一种形式是：ABa或Aa，前者称为右线性文法，后者称为左线性文法。正规文法所描述的是VT*上的正规集。,32,例3.4,G=(S,A,B,a,b,P,S)，其中P由下列产生式组成： SaB AbAA SbA Bb Aa BbS AaS BaBB 或将P改写为： SaB|bA AbA|a Aa|AaS BbS|BaB|b 则G是正规文法或3型文法。,33,例3.5,文法G=(S,A,B,0,1,P,S)，其中P由下列产生式组成： S0A A1B S1B B1B S0 B1 A0A B0 A0S 或将P改写为： S0A|1B|0 A0S|1B|0A B1B|1|0 则G是正规文法或3型文法。,34,乔姆斯基分类文法之间关系,2型文法,1型文法,0型文法,四种文法之间的逐级“包含”关系,3型文法,35,对应乔姆斯基分类文法的语言,0型文法产生的语言称为0型语言。 1型文法或上下文有关文法（ CSG ）产生的语言称为1型语言或上下文有关语言（CSL）。 2型文法或上下文无关文法（ CFG ）产生的语言称为2型语言或上下文无关语言（ CF L ）。 3型文法或正则（正规）文法（ RG ）产生的语言称为3型语言正则（正规）语言（ RL ）。,36,文法和语言之间的关系,四种文法之间的关系是将产生式做进一步限制而定义的。 语言之间的关系依次：有不是上下文有关语言的0型语言，有不是上下文无关语言的1型语言，有不是正则语言的上下文无关语言。,37,上下文无关文法及其语法树,语法树 句型能够构造关联语法树的条件 示例：例3.7 最左（右）推导 二义性文法 判断依据 示例：例3.8 二义性文法与二义性语言的区别,38,句型能够构造关联语法树的条件,给定文法G=(VN，VT，P，S)，对于G的任何句型都能构造与之关联的语法树(推导树)。这棵树满足下列4个条件： 每个结点都有一个标记，此标记是V的一个符号。 根的标记是S。 若一结点n至少有一个它自己除外的子孙（子结点），并且有标记A，则A肯定在VN中。 如果结点n的直接子孙，从左到右的次序是结点n1，n2，nk，其标记分别为A1，A2，Ak，那么AA1A2Ak一定是P中的一个产生式。,39,例3.7,G=(S,A,a,b,P,S)，其中P为： SaAS ASbA ASS Sa Aba 右图是G（aabbaa）的一棵推导树。,40,最左（右）推导,如果在推导的任何一步，其中，是句型，都是对中的最左(最右)非终结符进行替换，则称这种推导为最左(最右)推导。 在形式语言中，最右推导常被称为规范推导。由规范推导所得的句型称为规范句型。 最左推导示例 SaASaSbASaabASaabbaSaabbaa 最右推导示例 SaASaAaaSbAaaSbbaaaabbaa,41,二义文法的判断依据,若一个文法存在某个句子对应两棵不同的语法树，则称这个文法是二义的。 或者，若一个文法存在某个句子有两个不同的最左（右）推导，则称这个文法是二义的。 如果产生上下文无关语言的每一个文法都是二义的，则说此语言是先天二义的。 判定任给的一个上下文无关文法是否二义，或它是否产生一个先天二义的上下文无关语言，这两个问题是递归不可解的，即，不存在一个算法，它能在有限步骤内，确切判定任给的一个文法是否为二义的。我们所能做的事是为无二义性寻找一组充分条件(当然它们未必都是必要的)。,42,例3.8,文法G=(E,+,*,i,(,),P,E)其中P= Ei EE+E EE*E E(E) 是二义性的，假若规定了运算符“+”与“*”的优先顺序和结合规则，即按惯例，让“*”的优先性高于“+”，且它们都服从左结合，那么就可以构造出一个无二义文法。 定义表达式的无二义文法GE： ET|E+T TF|T*F F(E)|i 它和上述文法产生的语言是相同的。即它们是等价的。,43,二义性文法与二义性语言的区别,文法的二义性和语言的二义性是两个不同的概念。因为可能有两个不同的文法G和G，其中G是二义的，但是却有L(G)=L(G)，也就是说，这两个文法所产生的语言是相同的。,44,句型的分析,句型分析是识别一个输入符号串是否为语法上正确的程序的过程。在语言的编译实现中，把完成句型分析的程序称为分析程序或识别程序，分析算法又称识别算法。 从左到右的分析算法，即总是从左到右地识别输入符号串，首先识别符号串中的最左符号，进而依次识别右边的一个符号，直到分析结束。 句型的分析算法分类 句型的分析算法反映语法树的构造过程 句型分析的有关定义 句型分析的有关问题,45,句型的分析算法分类,自上而下分析法： 是从文法的开始符号出发，反复使用各种产生式，寻找“匹配”于输入符号串的推导。 示例：例3.9 自下而上分析法： 从输入符号串开始，逐步进行“归约”，直至归约到文法的开始符号。 示例,46,两种方法反映语法树的构造过程,自上而下方法： 自上而下方法是从文法符号开始，将它做为语法树的根，向下逐步建立语法树，使语法树的末端结点符号串正好是输入符号串。 自下而上方法： 自下而上方法是从输入符号串开始，以它做为语法树的末端结点符号串，自底向上地构造语法树。,47,例3.9：自上而下分析,例：考虑文法GS； ScAd Aab Aa 识别输入串w=cabd是否该文法的句子。,推导过程：ScAd cabd,48,示例：自下而上分析,例：考虑文法GS； ScAd Aab Aa 识别输入串w=cabd是否该文法的句子。,S A A c a b d c a b d c a b d 规约过程构造的推导： cAd cabd S cAd,49,句型分析的有关定义,令G是一文法，S是文法的开始符号，是文法G的一个句型。如果有： S A且A 则称是句型相对于非终结符A的短语。特别，如有A 则称是句型相对于规则A的直接短语(也称简单短语)。一个句型的最左直接短语称为该句型的句柄。 示例 从句型的推导树中查找方法,50,示例,文法GE的一个句型i*i+i。为了叙述方便，将句型改写为i1*i2+i3。因为有： E F* i2+i3 且Fi1则称i1是句型i1*i2+i3的相对于非终结符F的短语，也是相对于规则Fi的直接短语。又有： E i1*F+i3 且Fi2则i2是句型i1*i2+i3的相对于F的短语，也是相对于规则Fi的直接短语，还有： E i1*i2+F 且Fi3则i3也是句型i1*i2+i3的相对于F的短语，也是相对于规则Fi的直接短语。 E T*i2+i3，且T i1则i1是句型i*i2+i3的相对于T的短语。 E i1*i2+T 且T i3则i3是句型i1*i2+i3的相对于T的短语。 E E+i3 且E i1*i2则i1*i2是句型i1*i2+i3的相对于E的短语。 E E 且E i1*i2+i3则i1*i2+i3是句型i1*i2+i3相对于E的短语。 即i1，i2，i3，i1*i2和i1*i2+i3都是句型i1*i2+i3的短语，而且i1，i2，i3均为直接短语，其中i1是最左直接短语，即句柄。 虽然i2+i3是句型i1*i2+i3的一部分，并不是它的短语，因为尽管有E i2+i3，但不存在从文法开始符号E到i1*E的推导。,51,从句型的推导树中查找方法,从句型的推导树上很容易找出句型的短语和直接短语。 设A是句型的某一子树的根，其中是形成此子树的末端结点的符号串，则其中是句型的相对于A的短语。若这个子树只有一层分支，则是句型的直接短语。 示例,52,示例：推导树中找短语,53,句型分析的有关问题,在自上而下的分析方法中如何选择使用哪个产生式进行推导？ 假定要被代换的最左非终结符号是B，且有n条规则：BA1|A2|An，那么如何确定用哪个右部去替代B？ 在自下而上的分析方法中如何识别可归约的串？ 在分析程序工作的每一步，都是从当前串中选择一个子串，将它归约到某个非终结符号，该子串称为“可归约串”。 存在确定和不确定分析。,54,实用说明,有关文法的实用限制 上下文无关文法中的规则 无用符号和无用产生式的消除 -产生式的消除 单产生式的消除,55,有关文法的实用限制,在实用中，我们将限制文法中不得含有有害规则和多余规则： 有害规则，是指形为UU的产生式。它对描述语言显然是没有必要的。说它有害，是说它只会引起文法的二义性。 多余规则，是指文法中那些连一个句子的推导都用不到的规则，这类规则在文法中以两种形式出现。一种是文法中某些非终结符不在任何规则的右部出现，所以任何句子的推导中不可能用到它。 对文法G=(VN，VT，P，S)来说，为了保证其任一非终结符A在句子推导中出现，必须满足如下两个条件： A必须在某句型中出现。即有S A，其中，属于(VTVN)* 。 必须能够从A推出终结符号串t来。即A t，其中tVT 。 若程序设计语言的文法包含有多余规则时，其中必定有错误存在，因此检查文法是否包含多余规则是很有必要的。,56,上下文无关文法中的规则,上下文无关文法中某些规则可具有形式A，称这种规则为规则。 规则会使得有关文法的一些讨论和证明变得复杂,有时会限制这种规则的出现。 上下文无关文法的相关定理 定理3.1 定理3.2,57,定理3.1,若L是由文法G=(VN，VT，P，S)产生的语言，P中的每一个产生式的形式均为A，其中AVN，(VN VT)*(即可能为)，则L能由这样一种文法产生：每一个产生式或者为A形式，其中AVN， (VN VT)+(即)，或者 S且 S不出现在任何产生式右边。,58,定理3.2,如果G=(VN，VT，P，S)是一个上下文有关文法，则存在另一个上下文有关文法G1，它所产生的语言与G产生的相同，即L(G)=L(G1)，其中G1的开始符号不出现在G1的任何产生式的右边。 若G为上下文无关文法或正规文法，类似结论成立。,59,无用符号和无用产生式的消除,定义：设G=(VN，VT，P，S)是一文法，我们说G中的一个符号x(VNVT)是有用的指x至少出现在一个句子的推导过程中。即x必须同时满足以下两个条件： 存在、V*，有S*x 存在wVT*,x*w 否则就说x是无用的。如果一个产生式的左部或右部含有无用符号，则此产生式称之为无用产生式。 消除算法 算法1 算法2 示例,60,算法1,1、分别置VN(1)和P(1) 为； 2、对于P中的每一产生式A ，若 VT* ，则将A置于VN(1) 中； 3、对于P中的每一产生式A x1x2xm若每个xi都属于VN(1) 或VT ，则将A置于VN(1) ； 4、重复步骤3，直到VN(1)不再增大为止； 5、对于P中的每一产生式B y1y2yn ，若B及每一个yi都属于VN(1) VT ，则将此产生 式B y1y2yn置于P (1)。,61,算法2,1、分别置VN 、VT和P 为； 2、将文法的开始符号S置入VN中； 3、对于G (1)中任何形如A x1|x2 | | xm的产生式，若A VN ，则将符号串x1，x2 ， ， xm中的全部非终结符号置于VN中，而将其中的全部终结符号置于VT中； 4、重复步骤3，直到VN和VT都不再增大为止； 5、将P中左右部仅含VN VT中符号的所有产生式置P 。,62,示例,文法的定义 已知文法G=（S,U,V,W，a,b,c，P，S），产生式P的组成如下： SaS SW SU Ua VbV Vac WaW 执行算法1 执行算法2,63,执行算法1,第一步，由于产生式Ua、 Vac的右部均为终结符号串，故置VN(1) =U，V； 第二步，对于产生式SU ，由于U VN(1) ，故将S置于中，所以VN(1) =S，U，V； 于是得到以下文法G1： G1=（S,U,V,a,b,c,P (1),S），其中P (1)由如下产生式组成： SaS SU Ua VbV Vac,64,执行算法2,第一步，置VN =S； 第二步，因为G1中含有产生式SU、Ua ，故应将U、a分别置于，即VN =S，U VT =a; 因此得到等价的且不含无用符号和无用产生式的文法为G2=（S，U，a，P，S），其中，P由如下产生式组成： SaS SU Ua,65,-产生式的消除,算法3 算法4（ 不属于文法所产生的语言） 算法5 （属于文法所产生的语言） 示例： 不属于文法所产生的语言 属于文法所产生的语言,66,算法3,1、作集合 W1=A|产生式A P； 2、作集合序列 W