第二章-文法和语言基本知识课件

本章知识点：第二章 文法和语言基本知识字母表和符号串的概念文法和语言的形式定义直接推导、推导、句型、句子短语、直接短语、句柄语法树、文法的二义性了解文法和语言的分类2.1 概述程序设计语言的精确定义和描述：语法：语言结构的定义语义：描述语言的含义语用：从使用的角度来描述语言非形式化描述形式化描述：用一整套带有严格规定的符号体系来描述问题。编译程序是针对某种程序设计语言的。2.2 字母表和符号串的基本概念1、字母表字母表：字母表是元素的非空有穷集合。任何程序语言都有自己的字母表，例如:机器语言：由符号“0”和“1”组成的字母表，=0，1 ASCII字符集；C语言字母表为：=AZ,az,09,+,-,*,/,:,;，.，!,%,&,(,),2.2.12.2.1字母表和符号串字母表和符号串2.2 字母表和符号串的基本概念1、字母表：元素的非空有穷集合。2、符号：字母表中的元素。3、符号串（字）符号串：字母表中的符号所构成的一个有穷序列。空字：不包含任何符号的序列。：不含任何元素的空集2.2.12.2.1字母表和符号串字母表和符号串2.2 字母表和符号串的基本概念1.符号串的连接 y=y=y2.集合的乘积 A=A=A3.符号串的幂运算 y0=y1=y y2=yy4.集合的幂运算 A0=A1=A A2=AA5.集合A的闭包A*与正闭包A+的闭包*：上所有符号串的全体例如，若=a,b，则+=a,b,aa,ab,ba,bb,aaa,则*=，a,b,aa,ab,ba,bb,aaa,=0 U+2.2.22.2.2符号串的运算符号串的运算设L和M是两个符号串集合，则 1.合并：LMs|sL or sM 2.乘积：LM st|sL and tM 3.幂：L0=，L1L，L2LL,.,LnLLn-1 4.L的闭包，记作L*，L*Li(i=0)=L0L1L2L3 5L的正则闭包，记作L+（L+LL*）L+Li(i=1)=L1L2L3L4 例如：L=AZ,az D=091LD=AZ,az,09 2LD是由所有用一个字母后跟一个数字组成的符号串所构成的集合。3L4是由所有的四个字母的符号串构成的集合。4L（LD)*是由所有的字母开头的字母和数字组成的符号串所构成的集合。5D+是由所有的长度大于等于1的数字串所构成的集合。形式语言：符号串的集合不考虑语义程序符号串2.3 2.3 文法和语言的形式定义文法和语言的形式定义2.3.12.3.1形式语言形式语言 有穷集合的语言描述：枚举法 无穷集合的语言描述：文法（含递归）无穷集合的语言描述：文法（含递归）例例=0,1,=0,1,则集合则集合+表示为递归文法：表示为递归文法：A0 A 1 AA0 A A1 2.3 2.3 文法和语言的形式定义文法和语言的形式定义2.3.22.3.2文法的形式定义文法的形式定义文法：描述语言的语法结构的形式规则。上下文无关文法(Context-freeGrammar)：即文法所定义的语法范畴（语法单位）完全独立于这种范畴可能出现的环境。2.3.22.3.2文法的形式定义文法的形式定义1.规则（Backus-NaurForm，简记为BNF）规则：也叫产生式，是一个符号与一个符号串的有序对（A,），通常写作：A(或A:)其中，A是规则的左部，是规则的右部表示生成或定义为语言的语法结构用一组规则来表示。终结符号、非终结符号例 赋值语句变量=表达式2.2.文法文法 文法是规则的非空有穷集合，通常表示成四元式 G=（VT，VN,S,P），其中：VT是一个非空有穷终结符号集合；VN是一个非空有穷的非终结符号集合，且VTVN；P是一个产生式的非空有穷集合，每个产生式的形式是A(或A:)，其中 AVN，（VTVN）*。S VN，称为开始符号，S必须至少在某个产生式的左部出现一次。左部相同的产生式可以缩写成：A 1|2|3文法是对语言结构的定义和描述，规则是其关键。例,定义一类含+、*的算术表达式如:“变量是一个算术表达式;若E1和E2是算术表达式，则E1+E2、E1*E2和(E1)也是算术表达式。”用产生式描述为：E iEE+E E E*E E(E)见课本p12-14，例2.12.4例2.1=a，b 语言 L=a2n,b2n|n1对应文法？例2.2 表示所有标识符的文法？例2.4=a，b语言L=abna|n0对应文法？语言对应的文法示例：语言对应的文法示例：等价文法2、推导如果存在一个直接推导序列：012n（n0）称为0至n的一个长度为n的推导，表示成0n2.3.32.3.3语言的形式定义语言的形式定义1、直接推导令G=(VT,VN,S,P),若AP,且,(VTVN)*,则称A直接推导出，表示成 A +3、广义推导0n表示0=n或者0n+*2.3.32.3.3语言的形式定义语言的形式定义4、句型和句子设有文法G（VT，VN，S,P）。如果S,则称是一个句型。*5、语言由文法G产生的所有句子所组成的集合就是语言L(G)。L(G)|S且VT*+仅含终结符号的句型是一个句子。注：L(G)是VT*的子集见课本p16，例2.72.9S 01|0S1S 0S|1S|A yB B xB|x 文法对应的语言示例：文法对应的语言示例：例 S aB|bA A a|aS|bAA B b|bS|aBB 2.3.42.3.4规范推导和规范归约规范推导和规范归约 最左推导：最左推导：推导中的每一步推导中的每一步,都是替换都是替换 中最中最左的非终结符号。左的非终结符号。例如：例如：EE+T T+T F+T a+T a+T*F a+F*F a+a*F a+a*a最右推导：推导中的每一步最右推导：推导中的每一步,都是替换都是替换 中最右中最右的非终结符号。的非终结符号。例如：例如：EE+T E+T*F E+T*a E+F*aE+a*a T+a*a F+a*a a+a*a 2.3.42.3.4规范推导和规范归约规范推导和规范归约最左推导：最左推导：推导中的每一步推导中的每一步,都是替换都是替换 中最左的非终结符号。中最左的非终结符号。最右推导：推导中的每一步最右推导：推导中的每一步,都是替换都是替换 中最右的非终结符号。中最右的非终结符号。规范归约（最左归约）规范归约（最左归约）规范推导、规范句型规范推导、规范句型归约：推导的逆过程归约：推导的逆过程 .A A2.3.52.3.5递归规则与文法的递归性递归规则与文法的递归性1、递归规则、递归规则规则形如：规则形如：A A 或或 A A 或或 A A 2、文法的递归性、文法的递归性 有推导有推导A A +A A+注：语言是无穷集合，描述的文法一定是递归的。注：语言是无穷集合，描述的文法一定是递归的。2.4短语、直接短语、句柄短语、直接短语、句柄短语：短语：设文法设文法(T，N，)若有若有 且且 ，句柄：一个句型的最左直接短语。句柄：一个句型的最左直接短语。则称则称是句型是句型相对于非终结符的短语。相对于非终结符的短语。若若 且且=，则称，则称是直接短语。是直接短语。*+*2.5语法树与二义性语法树与二义性2.5.1推导和语法树语法树有助于理解句子(句型)语法结构的层次。语法树通常表示成一颗倒立的树，根在上，枝叶在下。1、语法树：用一张图来表示一个句型的推导,这张图称为语法树,也称推导树。例 G=(VT,VN,S,P),其中P:SaASaASbASSba3124657891011SaASSbAaaba根据推导序列，对每步推导画相应分枝ASaSbSAabaaaSbASaabASaabbaSaabbaaaASS如何画出分析树如何画出分析树 (自顶向下）自顶向下）根据归约序列，对每步归约画相应分枝abaabaSASASaAaaSbAaaSbbaaaabbaaaASS 如何画出分析树如何画出分析树 (自底向上）自底向上）1.一个句型推导或分析用一棵树结构图示出来，它反应了一个句型语法结构的层次。2.对于一个句子的多种推导（若文法是无二义性的），采用各种推导过程，画出的分析树是一样的。分析树并未描述推导过程，它是不同推导过程的抽象共性。3.在书中，用画分析树的过程解释语法分析过程，用分析树图解语法结构。关于分析树的几点说明关于分析树的几点说明SAbSaSbaAaa一棵分析树中一个特有的结点连同它的全部后裔，连接这些后裔的边以及这些结点的标记。例如：2、子树子树3、简单、简单 子树子树与短语等概念与短语等概念的对应关系的对应关系一个句型是否只对应一颗语法树？考虑表达式下面的文法GE,其产生式如下：EE+EE*E(E)a对于句子a+a*a,有如下两个最左推导：EE+Ea+Ea+E*Ea+a*Ea+a*aEE*EE+E*Ea+E*Ea+a*Ea+a*a 2.5.2 文法的二义性（文法的二义性（ambiguity）的定义）的定义 EE+E a+E a+E*E a+a*E a+a*a E E*EE+E*E a+E*Ea+a*E a+a*aEE+EE*EaaaEE*E+EEaaa最左推导最左推导 EE+E E+E*E E+E*a E+a*a a+a*a E E*EE*a E+E*aE+a*a a+a*aEE+EE*EaaaEE*E+EEaaa最右推导最右推导结论：一个句型可能有不止一个最左（最右）推导，对应不同的语法树，可以用完全不同的办法生成一个句型。如果一个文法存在某个句子对应两棵不同的语法树，则称这个文法是二义的。也就是某个句子有两个不同的最左（最右）推导。人们已经证明，二义性问题是不可判定的。为无二义性找寻一组充分条件例如文法GE,其产生式如下：EE+EE*E(E)i是二义性文法，加上限制规则：*优先级高于+且都服从左结合，则有无二义文法如：ET|E+TTF|T*FF(E)|i例如,对于条件语句，经常使用二义性文法描述它：SifexprthenSifexprthenSelseSother二义性的句子:ifc1thenifc2thenS1elseS2下面是描述if语句的无二义性文法的产生式:Smathed_sunmathed_smathed_sifexprthenmathed_selsemathed_sotherunmathed_sifexprthenSifexprthenmathed_selseunmathed_s它显然比较复杂，因此：在能驾驭的情况下，可以使用二义性文法。化简了的文法（限制条件）1产生式：AAP；2.每个非终结符号A必须都有用处。即，SA，且A，VT*+2.7 文法的实用限制文法的实用限制2.6 文法和语言分类文法和语言分类语言的分类：语言的分类：对文法中的规则施加不同的限制四种类型：0型，1型，2型，3型0型(无限制)：G=(VT,VN,S,P)规则形式：,(VTVN)*,并且至少含有一个非终结符号；1型（上下文有关）：Auu(VTVN)+,Au，S除外；2型（上下文无关）：规则形式：AAVN，(VTVN)*；3型（右线性）：AB或A（左线性）AB或A，VT*，A,BVNL0 L1 L2 L3说明：说明：1型文法也称上下文有关文法，非终结符的替换要考虑上下文。规则形式如A2型文法也称上下文无关文法，非终结符的替换不考虑上下文。A3型文法等价于正规式，正规文法。上下文无关文法足够描述多数程序设上下文无关文法足够描述多数程序设计语言的语法结构。计语言的语法结构。考虑文法G:S AB A aA|a B bB|b定义的语言为：L(GS)=anbmn,m1是2型文法。这个是线性问题，也可以写3型文法：SaAAaA|bBBbB|本章小结：语言语法结构的形式化描述：上下文无关文法语法树句子句型推导短语、直接短语、句柄文法的二义性作业作业:1、为语言、为语言L1=ambm bnan|m1,n 0 语言语言L2=akbm bnan|km0,n 1各构造一各构造一个上下文无关文法。个上下文无关文法。作业2、有有文法文法 S aB|bA A a|aS|bAA B b|bS|aBB给出其句子给出其句子aabbba的最左和最右推导，构造其语法树，的最左和最右推导，构造其语法树，并并指出最右推导过程中形成的各句型的短语、直接短语和句指出最右推导过程中形成的各句型的短语、直接短语和句柄。柄。