2第二章-文法与语言

编译原理CompilerPrinciples2013年9月闫雷鸣第二章文法与语言讨论问题：文法和语言的概念和定义文法和语言的分类文法等价变换句型分析简单回顾对程序的理解程序是计算机执行的一系列指令；程序是计算任务的处理对象和处理规则的描述。•对程序设计语言的理解程序设计语言是程序的书写规范；程序设计语言的要素：一组记号(符号)和一组规则。程序设计语言程序是程序设计语言之符号集合上的、按一定规则组成的符号串。•语言是一切句子的集合；程序设计语言是一切程序的集合；把程序看做程序设计语言的句子。•程序是(程序设计）语言的句子•如何系统地构造程序？或者，一般地，如何为一个(程序设计)语言生成句子？2.1符号串与符号串集合语言实际上是一个符号串集合；文法规定语言中句子的构造规则。句子是一个语言之字母表上按一定规则构造的符号串。2.1.1字母表字母表:有穷非空的符号集合。例A={a,b,c}∑={0,1}C语言字母表={字母，数字，界限符}不同的语言有不同的字母表。字母表上的元素（即符号）组成符号串。2.1.2符号串:1.符号串及其长度符号串:由字母表上的符号所组成的有穷序列。字母表A={a,b,c}上的符号串：a,b,c,ab,ba,aaa,aab,baa,abcab,ε(空串)注意：顺序是重要的,ab≠baC语言字母表上的符号串？长度：|aabcaca|=7|ε|=02.子符号串若u=xvy，其中|v|≠0（|u|=|v|）则v是u中的子符号串。（非空符号串）例a+(b-c)/d中的子符号串3.符号串的头与尾（前缀、后缀）abc的头：a,ab,abc,Ɛx=t…abc的尾：c,bc,abc,Ɛx=…t4.对符号串的运算联结（或并置）：x=aby=baxy=abbayx=baab对任何符号串x，有x=x=x。方幂：xn=xx…x(x自身联结n次)xn=xn-1x=xxn-1x0=Ɛx3=(ab)3=ababab|xy|=|x|+|y||xn|=n|x||x0|=02.1.3符号串集合（语言）1.符号串集合的定义1)它是一切元素都是某字母表上的符号串的集合。2)表示法枚举法{1，11，111，1111}省略法{1，11，111，1111，┅}描述法{1i|i≥1}或{x|x全由1组成,|x|≥1}注意：一定不能涉及含义,如{x|x=∑10i}。字母表∑上的一个语言就是∑上的一些符号串组成的集合。空集ф是一个语言，仅含一个空符号串集合{ф}也是一个语言。特别需要指出的是，Ɛ和{Ɛ}是不同的语言。2.对符号串集合的运算乘积：AB={xy|x∈A且y∈B}{1,0}{a,b,c}=?对任何符号串x有x=x=x，A0={ε}因此，{}A=A{}=A，但ØA=AØ=Ø。方幂：An=AA…A(n个A乘积）An=An-1A=AAn-1特例，字母表A的方幂，x∈An,|x|=n{1,0}3=?{1,0}n=?3.字母表的闭包与正闭包闭包A*=A0∪A1∪┅∪An∪┅{0，1，2}*正闭包A+=A1∪┅∪An∪┅=A*-{}{0，1，2}+x∈A+,则|x|=1x∈A*,则|x|=0任何一个语言是其字母表之正闭包的真子集。如何找出此真子集？或说，如何找出其句子？2.2文法与语言的形式定义2.2.1文法的形式定义1.重写规则（产生式规则）定义：有序对（U，u)或U::=uA→α（或A::=α）其中，A是一个符号，称为产生式规则的左部，而α是有穷非空符号串，称为产生式规则的右部，“→”和“::=”表示“定义为”或“由……组合成的”或“生成”，其含义是左部符号用右部的符号串定义或左部符号生成右部符号串。产生式规则可合写，如：A→α和A→β可写为A→α|β1.重写规则（产生式规则）规则表示法：通常的E::=E+TE::=T或E::=E+T|T扩充的E::=T{+T}术语：非终结符号，非终结符号集VN终结符号，（不会出现在规则左部）终结符号集VT（VN∩VT=ØV=VN∪VT）单规则：右部是单个非终结符{}用于指定重复次数标识符::=字母{字母数字}05[]内中符号至多出现一次整数::=[+|-]数字{数字}()提公因子E::=E+T|E-T可改写为E::=E(+|-)T16规则构造的例子C语言标识符的规则：标识符::=字母下划线标识符::=标识符字母下划线标识符::=标识符数字字母下划线::=A|…|Z字母下划线::=a|…|z字母下划线::=_数字::=0|…|917用规则产生句子的例子如：用标识符产生式规则产生句子area.标识符标识符字母下划线标识符a标识符字母下划线a标识符ea标识符字母下划线ea标识符rea字母下划线reaarea其中，“=”为推导。2.文法的定义文法G[Z]是非空有穷的重写规则集合，其中Z是识别符号（或称开始符号），G是文法名。例G1[E]：E::=E+TE::=TT::=T*FT::=FF:=(E)F::=iG2[E]：E::=E+T|TT::=T*F|FF::=(E)F::=iG[E]：E::=T{+T}T::=F{*F}F::=(E)|i文法的四要素：VN，VT，P，ZP有穷非空的重写规则集，识别符号ZVN3.应用文法产生语言的句子G[句子]:1.句子::=主语谓语状语2.主语::=名词3.谓语::=动词4.状语::=介词名词5.名词::=Peter6.名词::=Berry7.名词::=river8.动词::=swims9.介词::=in例试以文法G[句子]为例考察如何应用文法来生成句子。替换为‹句子›=‹主语›‹谓语›‹状语›(规则1)=‹名词›‹谓语›‹状语›(规则2)=Peter‹谓语›‹状语›(规则5)=Peter‹动词›‹状语›(规则3)=Peterswims‹状语›(规则8)=Peterswims‹介词›‹名词›(规则4)=Peterswimsin‹名词›(规则9)=Peterswimsinriver(规则7)应用文法生成句子的步骤：步骤1以识别符号为当前符号串；步骤2对当前符号串中的一个非终结符号进行替换，把它替换为以此非终结符号为左部的规则之右部符号串，生成新的当前符号串；步骤3重复步骤2,直到当前符号串中不包含非终结符号，最终不包含非终结符号的符号串就是所生成的句子。说明：每步的当前符号串将称为句型，最终的终结符号串称为句子。按上述步骤应用各个规则，可生成：Berryswimsinriver甚至可生成：riverswimsinPeter表明：语法上的正确性不能保证语义上的正确性。对当前句型中任一非终结符号进行替换，都将生成新的句型，最终生成句子。但宜用系统的方式进行推导，如，每步对最左的或最右的非终结符号进行替换。这时，分别称为最左推导与最右推导。引进句子生成中的两个重要概念：推导与归约。直接推导：=xUy=xuy‹句子›=‹主语›‹谓语›‹状语›‹主语›‹谓语›‹状语›=‹名词›‹谓语›‹状语›‹名词›‹谓语›‹状语›=Peter‹谓语›‹状语›Peter‹谓语›‹状语›=Peter‹动词›‹状语›Peter‹动词›‹状语›=Peterswims‹状语›Peterswims‹状语›=Peterswims‹介词›‹名词›Peterswims‹介词›‹名词›=Peterswimsin‹名词›Peterswimsin‹名词›=Peterswimsinriver直接推导时，给定v=xUy,找到规则U::=u，把u代替U，得到w=xuy称v直接推导到w，记为：v=w或xUy=xuy推导（直接推导序列）：=+句子=‹主语›‹谓语›‹状语›=‹名词›‹谓语›‹状语›=Peter‹谓语›‹状语›=Peter‹动词›‹状语›=Peterswims‹状语›=Peterswims‹介词›‹名词›=Peterswimsin‹名词›=Peterswimsinriver推导时，给定符号串v,找到v=u1=u2=…=un-1=w,得到符号串w,称v推导到w，记为：v=+w。一般，从识别符号开始推导，例如，句子=+Peter‹谓语›‹状语›句子=+Peterswimsinriver推导长度：直接推导的步数。直接推导:=直接推导时，给定v=xUy，在其中找出U，应用规则U::=u,得到w=xuy，称v直接推导到w,或w直接归约到v,记为v=w一般，总有：U::=uxUy=xuy推导:=+推导时，给定符号串v,找出直接推导序列：v=u1=u2=…=un-1=w得到符号串w,称v推导到w,或w归约到v,记为:v=+wn称为推导的长度。广义推导：=*若v=+w或v=w，则称v广义推导到w,或广义归约到v。对照：直接推导v=w(U::=uv=xUyw=xuy)(推导长度=1)推导v=+w(v=u1=…=un-1=w)(推导长度1)广义推导v=*w(v=+w或v=w)(推导长度0)通常考虑的都是从识别符号出发的推导：Z=*xx∈(VN∪VT)+直接归约：v=ww直接归约为v归约:v=+ww归约为v广义归约:v=*ww广义归约为v请对照比较推导与归约这两个概念。重要概念：句型、句子句型：Z=*x,x∈(VN∪VT)+句子：Z=*x,x∈VT+例Peterswimsinriver注意：句子和句子在概念上的区别注意：应用文法生成句子仅是形式上的。例riverswimsinPeter注：句子也是句型，但句型不一定是句子。文法产生句型和句子的例子【例】设有文法G[Z]:Z::=aZb|Ɛ有推导：Z=*ƐZ=*aZb=aaZbb=*aaabbb可见，符号串ε，aZb，aaZbb和aaabbb都是文法G[Z]的句型，而ε和aaabbb才是文法G[Z]的句子。30文法产生句型和句子的例子【例】设有文法G[E]:E::=E+T|E-T|TT::=T*F|T/F|FF::=(E)|i试证明i+i*i是它的一个句子。分析：只有证明i+i*i可由文法G从开始符号E推导出，即可证明i+i*i是它的一个句子。证明：EE+TE+T*FE+T*iE+F*iE+i*iT+i*iF+i*ii+i*i即有E*i+i*i又因i+i*i中的每个符号均为终结符号，故i+i*i是它的一个句子。思考设计编程语言时，是先设计语言形式，还是先设计BNF形式的文法？例如要表示形如i+i,i+i*i的表达式建议：学习时注意积累，何种典型文法可以得到某种典型的语言形式考试考查：能够由文法写出语言，也能由语言设计出文法为什么有穷规则集合的文法能定义无穷的语言？文法G[无正负号整数]：1）无正负号整数::=数字序列2）数字序列::=数字序列数字3）数字序列::=数字4）数字::=05)数字::=16）数字::=27)数字::=38)数字::=49)数字::=510)数字::=611)数字::=711)数字::=812)数字::=9VN={无正负号整数,数字序列,数字}VT={0,1,2,3,4,5,6,7,8,9}无正负号整数=数字序列=数字序列数字=数字序列数字数字=数字数字数字=1数字数字=12数字=123无正负号整数=数字序列=数字序列数字=数字序列数字数字=数字序列数字数字数字=…递归地定义规则，即，U::=U…,使得有穷个规则可能定义潜在地无穷的语言。重要概念：短语、简单短语已知w=xuy是文法G的句型,短语u