编译原理第2章编译基础.ppt

资源描述

《编译原理第2章编译基础.ppt》由会员分享，可在线阅读，更多相关《编译原理第2章编译基础.ppt（53页珍藏版）》请在三一办公上搜索。

1、1,第二章编译基础,2,2.0 概述,对程序设计语言的描述是从语法、语义和语用三个因素来考虑。,语法是对语言结构的定义。,语用则是从使用的角度去描述语言。,语义是描述了语言的含义。,3,2.0 概述,例如赋值语句s2*3.1416*r 的非形式化的描述为：,语法：赋值语句由一个变量，后随一个赋值号“”，再在其后面跟一个表达式构成。,语义：首先计算语句右部表达式的值，然后把所得结果送给左部变量中。,语用：赋值语句可用来计算和保存表达式的值。这种非形式化的描述,不够清晰和准确,为了精确定义和描述程序设计语言,需采用形式化的方法。,4,形式化方法：是用一整套带有严格规定的符号体系来描述问题的

2、方法。,2.1 符号表,一符号串与字母表 1字母表：元素的非空有穷集合。两含义：字母表中至少包含一个元素。字母表中元素可以是字母、数字或其它符号。例如：=a,b,c,5,2.符号（字符）：字母表中元素。3.符号串：用字母表中的符号组成的任何有穷序列，也称字。例如：a,ab,bba,acab,注意：符号串中符号的顺序是很重要的。不包含任何符号的符号串称空串，记为。|=0一个字母表上全部符号的集合是无穷的。,6,4.符号串的前缀、后缀以及子串：设x是一符号串，例如：x=abc符号串的前缀：从x的尾部删除若干个（=0）符号后所余下的部分。例如：，a，ab，abc符号串的后缀：从x的头部删除若干个（

3、=0）符号后所余下的部分。例如：，c，bc，abc子串：从x中删除前缀和后缀之后所余下的部分。例如：，a，b，ab，bc，abc,7,二.符号串的运算1符号串的连接：设x，y是符号串，则串xy称为它们的连接。例如：设x=my y=computerxy=mycomputeryx=computermy注意：对任意xX=X=X2集合的和与乘积：设A，B是符号串的集合，则：AB=|A或BAB=xy|xA且yB例如：设A=a,bB=c,d则：AB=a,b,c,dAB=ac,ad,bc,bd注意：A=A=AA=A=A=A=A=,8,3.符号串的幂运算：若x是符号串，则 x0=,x1=x,x2=xx,例如：

4、设 x=abc则：x0=,x1=abc,x2=abcabc,4.集合的幂运算：若A是符号串的集合，则 A0=,A1=A,A2=AA,例如：设 A=a,b则：A0=,A1=a,b,A2=aa,ab,ba,bb,5.集合的A(正闭包)和A*（自反传递闭包）:设A为任一集合，则：A=A1A2A3 An（A上所有符号串所组成的集合）A*=A0 A=A例如：设A=a,b,cA=a,b,c,aa,ab,ac,ba,bb,bc,A*=,a,b,c,aa,ab,ac,ba,bb,bc,9,2.2 文法和语言的形式定义,一形式语言：是一字母表上按某种规则构成的所有符号串的集合。反之，任一字母表上符号串的集合均可

5、定义为一个形式语言。二形式语言的描述：（三种方法）1当语言为有穷集合时，用枚举法。,例如：设有字母表 A=a,b,c则：L1=a,bL2=a,aa,ab,ac L3=c,cc,10,2用文法描述语言例如：设有字母表=0，1+=0，1，00，01，11，10，000，100，用A表示+，A0（定义为，生成，导出）用产生式表示+：A0 A1 AA0 AA13用自动机识别语言：构造一种装置来识别语言，它可以判断某符号串是否是该语言的句子。例如：1100 是（接收）11ab 不是（不接收）,自动机,11,三文法的形式定义,1 规则（产生式）：是一个符号与一个符号串的有序对（A，），通常写作：A或 A

6、=2非终结符与终结符：非终结符：出现在规则左部能派生出符号或符号串的那些符号。通常用大写字母表示。终结符：是组成语言不可再分的基本符号，通常用小写字母表示。,12,3文法的形式定义：是规则的非空有穷集合，通常定义为四元组：GS=（Vn，Vt，P，S）其中：Vn：规则中非终结符的集合。Vn=AVt：规则中终结符的集合。Vt=0，1P：文法规则式的集合。P:A0 A1 AA0 AA1S：文法的开始符号（识别符号）由它开始识别我们所定义的语言。S=A 例1例2例3例4例5继续,13,例1设有字母表=a，b，请为语言 L=a2n,b2n|n=1 设计一个文法。首先分析语言中串的结构特征：L=aa,bb

8、1AA1C B0C文法：GL=（A,B,C,S,0,1,P，S）P:S0A|1BA0S|1C|0B1S|0C|1C0B|1A返回,16,例3.试给出不以0开头的正奇数文法（作业P36.7)分析：奇数集合1，3，5，7，9，11，易错：A1|2*A+1P:Sd1A|d3Ad2A|d3d11|2|3|4|5|6|7|8|9d20|1|2|3|4|5|6|7|8|9d31|3|5|7|9返回,17,例4.用文法定义一个含+，*的算术表达式，定义用自然语言（非形式化）描述：变量是一个算术表达式若E1和E2是算术表达式，则E1+E2,E1*E2,(E1)也是算术表达式。分析：符号串的集合i,i+i,i

9、*i,(i),i+i*i,GE=(E,i,+,*,(,),P,E）P:EiEE+EEE*E返回E(E)说明：并不是做加法和乘法运算，仅描述哪些符号串是该文法的句子（算术表达式），如 ii+i,i*i+都不是该文法的句子。,18,例5.设计一个表示所有标识符的文法。（标识符的定义：以字母开头的字母数字串）I标识符L字母D数字P:IL|I L|I DLa|b|c|x|y|zD 0|1|2|3|4|5|6|7|8|9 比较：P1:IL|I D(以字母开头的数字串，缩小了语言范围）P2:IL|I L|I D|D(有可能以数字开头，扩大了语言范围）P3:IL|L I|D I(有可能以数字开头，扩大了语言

10、范围）,19,四.语言的形式定义,1.直接推导：设x和y是符号串，若用一次规则式可以从x推导出y，则称y为x的直接推导，并记为x=y例如：设有文法GS:S0S1|01S=01S=0S10S1=0011 注意：推导和规则的区别形式上不一样=推导的依据是规则有A 才有 A=,20,2.推导（+推导）：设x和y是符号串，如果使用若干次（=1次）规则式可以从x推导出y，则称y为x的推导，并记为x=y。例如：设有文法：GS:S0S1|01则：S=01S=0S1 S=0S1=00S11=000111 S=000111 3.广义推导（*推导）：设x和y是符号串，如果使用若干次（=0次）规则式可以从x推导出

11、y，则称y为x的广义推导，并记为x=y。x=y 等价于x=y 或 x=y,+,+,*,*,+,21,4.句型句子：设有文法GS，能从文法开始符号S推导出来的符号串称为G的一个句型。A=，（VNVT）*仅由终结符号组成的句型称为句子。S=01（句子）S=0S1（句型）S=000111（句子）例如：已知文法GE:E E+E|E*E|(E)|i,试证明符号串(i*i+i)是该文法的一个句子。分析：只要证明符号串对文法G存在一个推导。解:E=(E)=(E+E)=(E*E+E)=(i*E+E)=(i*i+E)=(i*i+i)E=(i*i+i)(i*i+i)是文法G的一个句子。,*,*,*,*,22,5.

12、语言的定义：文法G全体句子所组成的集合。L(GS)=w|S=w 且 wVt*定义式意义如下：w是从文法开始符号推导出来的w仅由终结符号组成，称为该语言的句子L(G)是由所有这样的句子组成的语言L(G)是Vt*的子集，但反过来不一定成立对一给定的文法，可以唯一地确定语言；反过来，给定一语言，可以由不同的文法来描述。,+,23,例1：文法：GS:S0S1|01 所描述的语言是什么？分析：从文法开始符号出发，将推导出什么样的句子，找出句子的规律，用式子或自然语言描述出来。解：S=0S1=00S11=0n-1 S 1n-1=0n 1n L(GS)=0n 1n|n1即:L=01,0011,000111,

14、Ab2=anAbn=an 0 bn S=B=aBbb=a2B(bb)2=an B(bb)n=an 1b2n S=an 0 bn|an 1b2n L(GS)=an 0 bn,an 1b2n|n 0,26,五.规范推导和规范归约,问题：对一个句子的推导过程是不是唯一的？（回答是否定的。）例如：文法GN1:N1 N,N ND|D,D 0|1|2(由0，1，2 组成的无符号正整数）看22的推导过程：N1=N=ND=N2=D2=22(最右推导）N1=N=ND=DD=2D=22(最左推导）N1=N=ND=DD=D2=22(左右推导）同一句子可以通过不同的推导序列推出，为确定推导序列，只考虑两种特殊推导。,

15、27,1.最左（或最右）推导：在推导过程中任何一步，被替换的总是当前符号串中的最左（或最右）非终结符。最右推导也称规范推导，用规范推导推出的句型称规范句型。例如：已知文法GS，给出句子babaab的最左，最右推导。GS:S ABA Aa|bBB a|Sb最右推导:S=AB=ASb=AABb=AAab=AbBab=Abaab=bBbaab=babaab 最左推导:S=AB=bBB=baB=baSb=baABb=babBBb=babaBb=babaab,28,2.归约：句型中某子串用一个非终结符来替换的过程。对规则式：A 则 xAy=xy是推导 xy=xAy是归约例1：22=D2=N2=ND=N=

16、N1(最右推导的逆过程最左归约规范归约）例2：设有文法：GS:S a|(T)T T,S|S 请给出符号串（a,(a,a)的规范归约。（a,(a,a)=（S,(a,a)=（T,(a,a)=（T,(S,a)=（T,(T,a)=（T,(T,S)=（T,(T)=（T,S)=(T)=S,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,29,六.递归性,1.规则递归:若文法中有规则式：A A，称规则左递归。若文法中有规则式：A A，称规则右递归。若文法中有规则式：A A，称规则递归。2.文法递归：若有推导 A=A,称文法左递归。若有推导 A=A,称文法右递归。若有推导 A=A,称文法递归。

17、举例：文法GN1:N1 N,N ND|D,D 0|1|2(由0，1，2 组成的无符号正整数）N ND 规则左递归，文法左递归（正因为递归，使得有限的文法规则式能刻画一个无穷的语言）文法GU:U Vx,V Uy|a 无规则左递归，但文法左递归 U=Vx=Uyx 即U=Uyx,+,+,+,+,30,2.3 句型的分析,句型的分析：构造一种算法，用以判断所给的符号串是否为该文法的句型（或句子）。两种方法：自顶向下分析法：从文法的开始符号出发，以给定的符号串为目标，根据文法规则，正向推导出给定符号串的一种方法。自底向上分析法：从给定的符号串出发，反复使用文法中有关产生式的左部去替换当前符号串中的相应子

18、串，逐步归约成文法开始符号的一种方法。,31,一、短语与句柄,1 短语：设有文法GS，w=是它的一个句型，如果有S=A，且A=，则称是句型w相对于非终结符A的短语。2 直接短语：设有文法GS，w=是它的一个句型，如果有S=A，且A=，则称是句型w相对于非终结符A的直接短语。3 句柄：最左边的直接短语是句柄。特征：它是直接短语（某个产生式的右部）具有最左性,*,*,+,32,例：设有文法：SABAAa|bBBa|Sb求句型baSb的全部短语，直接短语和句柄。解：首先建立句型baSb的推导过程最左：S=AB=bBB=baB=baSb最右：S=AB=ASb=bBSb=baSbS=S 且 S=baSb

19、句型本身是一个短语S=baB 且 B=SbSb是句型baSb的直接短语S=ASb 且 A=baba是句型baSb的短语S=bBSb 且 B=aa是句型baSb的直接短语,*,*,*,*,+,+,33,二.语法树,1.语法树：对句型的推导过程给出一种图形表示。也称推导树。例如：已知文法GE,证明T/(E-T)*F+i是它的一个句型,并画出相应的语法树。GE:E E+T|E-T|TT T*F|T/F|FF(E)|i证明：E=E+T=E+F=E+i(最右推导）=T+i=T*F+i=T/F*F+i=T/(E)*F+i=T/(E-T)*F+i,E E+T T*F FT/F i(E)E-T,34,子树：由

20、某一结点及其分枝组成，是原树的一棵子树。简单子树：只有单层分枝的子树。说明：语法树的构造过程是从文法的开始符号出发，构造一个推导过程。每个句型都有一棵语法树一棵语法树等价于一个最左推导,35,2.语法树与短语：每棵子树（某一结点及其分枝组成）的叶子形成的符号串组成一个短语。每棵简单子树（单层分枝）的叶子形成的符号串组成一个直接短语。最左边简单子树的叶子组成一个句柄。,36,例1：设有文法：GS:SaAcBeAbAAbBd解：句型aAbcde的语法树为：,若有句型aAbcde，试问b是它的直接短语吗？它的短语是什么？句柄是什么？,Sa A c B e A b d,显然，b不是句型的直接短语。该

22、*F F(E)(E)E-TE+T T F F i,由语法树可知，短语有：F直接短语，句柄i直接短语F+i(F+i)E-T直接短语(E-T)T*(E-T)(F+i)-T*(E-T),39,三.文法的二义性,若一个文法的某个句子对应两棵不同的语法树，或者有两个不同的最左（或最右）推导，则称这个文法是二义的。,40,例1：证明文法GE:E E+E|E*E|(E)|i是二义性文法。证明：对句型(i*i+i)有两个最左推导推导1：E=(E)=(E+E)=(E*E+E)=(i*E+E)=(i*i+E)=(i*i+i)推导2：E=(E)=(E*E)=(i*E)=(i*E+E)=(i*i+E)=(i*i+i)

23、该文法是二义性文法改写文法：构造一个等价的无二义性文法规定：*优先于+并且+、*左结合（文法左递归-左结合）P:E E+E|TT T*F|FF(E)|i,E(E)E+E E*E i i i,E(E)E*E i E+E i i,41,例2.条件语句：C if B then C|if B then C else C|S证明该文法是二义性文法没。证明：句子if B then if B then S else S 有两棵语法树,C If B then C if B then C else C S S,C if B then C else C if B then C S S,改写文法：规定：else与最

24、近的then匹配C C1|C2C1 if B then C1 else C1|SC2 if B then C|if B then C1 else C2,42,例3：已知文法：GN:N SE|ES SD|DE 0|2|4|6|8|10D 0|1|2|3|4|5|6|7|8|9 问题：证明该文法是二义的。该文法所描述的语言是什么？构造一个无二义性文法G，使L(G)=L(G)解：句子10有两棵语法树（10结尾的都行）语言为所有无符号偶数改写文法：E 0|2|4|6|8,N S E D 0 1,NE1 0,43,2.4 文法的化简和改造,一.无用符号和无用产生式的删除1.无用符号和无用产生式：我们说

25、文法G中的一个符号xV是有用的，是指x必须同时满足两个条件：存在,V*有S=x(x至少出现在某句型中）存在 tVt*,使 x=t(从x能推出终结符号串）否则，x是无用符号，如果一个产生式含有无用符号，则该产生式称为无用产生式。2.删除方法：（直观看）删除P P形式的产生式删除不能导出终结符号串的产生式删除在推导中永远不使用的产生式,*,+,+,44,例如：化简下述文法，其中S是文法的开始符号。S BeS EcA AeA eA AB CeB AfC CfD fG b解：根据原则，可消去根据原则，可消去根据原则，可消去化简后文法为：S Be B Af A Ae A e,45,二.单产生式的消除

26、,1.单产生式：右部仅含一个非终结符的产生式。例如：A B(文法含单产生式，增加编译程序的时间和空间，要删除）2.算法：构造非终结符号集，对文法G中的每个非终结符A，求：A=B|A=B,BVN 若有A=B，且文法G中有B x,则在文法中扩充规则：A x,并且删除单产生式和无用产生式,+,+,46,例如：设有文法G1A:A B|dEB A|D|bD B|dE e|Ea求：不含单产生式的文法G2，使得L(G1)=L(G2)。解：A=A=dEA=B=bA=D=d A=A,B,D 同理：B=A=dEB=B=bB=D=d D=A=dED=B=bD=D=d B=A,B,D D=A,B,D E=扩充规则：A

27、 b|d,B dE|d,D dE|b 删除单产生式得文法G2A:A dE|b|d,B dE|b|d,D dE|b|d,E e|Ea删除无用产生式：由于B,D均不在任何句型中出现，故删除文法G2A:A dE|b|d E e|Ea,+,+,+,+,+,+,+,+,+,47,2.5 文法和语言的分类,一.0型文法（PSG，短语文法，无限制文法）：若文法G中任一产生式具有如下形式：V+，V*，则称为0型文法。0型文法所描述的语言称为0型语言或递归可枚举语言。0型语言可以用图灵机TM（Turing Maching)来识别。例如：GS=(S,A,B,C,D,E,a,P,S)P:S ACaB,Ca aaC,

28、CB DB,CB E aD Da,AD AC,aE Ea,AE 以上文法是一个0型文法，所产生的语言为：L(G)=ai|i是2的正整数次方=aa,aaaa,aaaaaaaa,特点：没有对产生式作更多的限制，仅要求中至少含有一个非终结符。,48,二.1型文法（上下文有关文法）简写CSG(Context Sensitive Grammar),若文法G中任一产生式具有如下形式：A U AVN,UV+，,V*，则称为1型文法。1型文法所描述的语言称为1型语言或上下文有关语言。1型语言可以用线性界限自动机LBA（Linear Bounded Automata)来识别。例如：GS=(S,A,B,C,D,a

29、,b,c,P,S)P:S A,A aABD,A abD,DB CBCB CD,CD BD,bB bb,D c以上文法是一个1型文法，所产生的语言为：L(G)=an bn cn|n1 当n=1时：S=A=abD=abc当n=2时：S=aABD=a2 bDBD=a2 bCBD=a2 bCDD=a2 bBDD=a2 b2 DD=a2 b2 c2,49,三.2型文法（上下文无关文法）简写CFG(Context Free Grammar),若文法G中任一产生式具有如下形式：A AVN,V*，则称为2型文法。2型文法所描述的语言称为2型语言，或者上下文无关语言。2型语言可以用下推自动机PDA（Push D

30、own Automata)来识别。例如：GS=(S,a,b,P,S)P:SaSb,Sab 以上文法是一个2型文法，所产生的语言为：L(G)=an bn|n1 通常，利用2型文法描述高级语言的句法部分，然后用PDA来识别。,50,四.3型文法（正规文法）,若文法G中任一产生式具有如下形式：AaB,Aa右线性文法 ABa,Aa左线性文法其中：A,BVN,a VT，3型文法所描述的语言称为正规语言，或者有限状态语言。3型语言可以用有穷自动机FA（Finite Automata)来识别。,51,例如，用左线性正规文法和右线性正规文法定义标识符,用I代表标识符;l代表任意一个字母;d代表任意一个数字;则定义标识符的文法为：,左线性文法:P:I l|Il|Id,右线性文法:P:I l|lT Tl|d|lT|dT,52,例如，用左线性正规文法和右线性正规文法定义无符号整数,用N代表无符号整数;d代表任意一个数字；则定义的无符号整数文法为：,左线性文法:P:N Nd|d,右线性文法:P:N dN|d,53,由上述四类文法的定义可知,从0型文法到3型文法,是逐渐增加对规则的限制条件而得到的，因此每一种正规文法都是上下文无关的文法，每一种上下文无关的文法都是上下文有关的文法，而每一种上下文有关的文法都是0型文法,而由它们所定义的语言类是依次缩小的，有 L0 L1 L2 L3。,

展开阅读全文