版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、第第3 3章章文法和语言文法和语言教学要求:本章是编译原理课程的理论基教学要求:本章是编译原理课程的理论基础,要求理解文法、语言、规范推导、规础,要求理解文法、语言、规范推导、规范归约和短语、简单短语、句柄的基本概范归约和短语、简单短语、句柄的基本概念;掌握语言的求解方法、文法的二义性念;掌握语言的求解方法、文法的二义性的判断方法及句型的分析方法。的判断方法及句型的分析方法。教学重点:上下文无关文法,语言定义教学重点:上下文无关文法,语言定义 一、语言一、语言 语言是由句子组成的集合,是由一组记号语言是由句子组成的集合,是由一组记号所构成的集合。所构成的集合。汉语汉语-所有符合汉语语法的句子的
2、全体所有符合汉语语法的句子的全体英语英语-所有符合英语语法的句子的全体所有符合英语语法的句子的全体程序设计语言程序设计语言-所有该语言的程序的全体所有该语言的程序的全体“我是大学生我是大学生”是否是该语言的句子?是否是该语言的句子?句子句子:=:=主语谓语主语谓语主语主语:=:=代词代词| |名词名词代词代词:= := 你你 | | 我我 | | 他他名词名词:= := 王明王明 | | 大学生大学生 | | 工人工人 | | 英语英语谓语谓语:=:=动词直接宾语动词直接宾语动词动词:= := 是是 | | 学习学习直接宾语直接宾语:=:=代词代词| |名词名词二、文法二、文法句子句子 主语谓
3、语主语谓语 代词谓语代词谓语 我谓语我谓语 我动词直接宾语我动词直接宾语 我是直接宾语我是直接宾语 我是名词我是名词 我是大学生我是大学生句子句子:=:=主语谓语主语谓语主语主语:=:=代词代词| |名词名词代词代词:= := 你你 | | 我我 | | 他他名词名词:= := 王明王明 | | 大学生大学生 | | 工人工人 | | 英语英语谓语谓语:=:=动词直接宾语动词直接宾语动词动词:= := 是是 | | 学习学习直接宾语直接宾语:=:=代词代词| |名词名词三、符号和符号串三、符号和符号串 字母表字母表 :元素的:元素的非空有穷非空有穷集合。(符号集)集合。(符号集):字母表中的元
4、素。:字母表中的元素。任何一种语言可看成是某个符号集上定义的,按任何一种语言可看成是某个符号集上定义的,按一定规则构成的一切基本符号串组成的集合。一定规则构成的一切基本符号串组成的集合。:由字母表:由字母表 中的符号组成的中的符号组成的任何任何有穷序列称有穷序列称为该字母表上的符号串。为该字母表上的符号串。形式定义形式定义: :1.1.空符号串空符号串(没有没有符号的符号串符号的符号串) )是是 上的符号串上的符号串 2.2.若若x x是是 上的符号串上的符号串, ,a a是是 的元素的元素, ,则则xaxa是是 上的符号上的符号串串 3.3.y y是是 上的符号串上的符号串, ,当且仅当它可
5、以由当且仅当它可以由1 1和和2 2导出。导出。 例如:例如: =a,b =a,b ,a,b,aa,ab,aabba,a,b,aa,ab,aabba,都都是是 上的符号串上的符号串例:例: =0,1=0,1,0,1,00,01,11,1001110,0,1,00,01,11,1001110等等都都是是 上的符号串上的符号串. .例:例: =a,b,c=a,b,c上的符号串有:上的符号串有:,a,b,c,ab,ba,aaca,acaa,a,b,c,ab,ba,aaca,acaa等等. .注意:注意: 符号串中的符号排列是有顺序的。符号串中的符号排列是有顺序的。1.1.常用大写字母表示符号串,如常
6、用大写字母表示符号串,如 x=aacax=aaca如果如果 z = xy 是一符号串是一符号串,那么那么:1、x 是是 z 的头的头,y 是是 z 的尾的尾;2、如果如果 x 非空非空,那么那么 y 是固有尾是固有尾;如果如果 y 非空非空,那么那么 x 是固有头是固有头。例例:设设 z = abc, 那么那么z 的头是的头是: ,a ,ab , abc,a ,ab , abc(除除 abc abc 外都是固有头外都是固有头)z 的尾是的尾是: ,c ,bc , abc,c ,bc , abc(除除 abc abc 外都是固有尾外都是固有尾)4 4、符号串的运算、符号串的运算符号串的长度符号串
7、的长度:符号串中符号的个数:符号串中符号的个数. .符号串符号串s s的长度的长度记为记为| |s|s|。 的长度为的长度为0 0符号串的连接符号串的连接:符号串:符号串x x、y y的连接的连接, ,是把是把y y的符号写在的符号写在x x的符号之后得到的符号串的符号之后得到的符号串xyxy例例 x=ST,y=abu x=ST,y=abu 则则 xy=STabuxy=STabu |x|=2,|y|=3,|xy|=5 |x|=2,|y|=3,|xy|=5 x = x= x x = x= x方幂方幂:符号串:符号串x x自身连接自身连接n n次得到的符号串次得到的符号串 xxxx(nxxxx(n
8、个个x)x)定义为定义为 x xn n x x0 0=, x=, x1 1=x, x=x, x2 2=xx, x=xx, x3 3=xxx=xxxx=AB, x=AB, 则则 x x0 0=, x=, x1 1=AB, x=AB, x2 2=ABAB, x=ABAB, x3 3=ABABAB=ABABAB对于对于 n0, xn0, xn n = xx= xxn-1 n-1 = x= xn-1n-1x x 5 5、符号串集合、符号串集合 若集合若集合A A中一切元素都是某字母表中一切元素都是某字母表 上的符号串,上的符号串,则称则称A A为字母表为字母表 上的符号串集合。上的符号串集合。 两个符
9、号串集合两个符号串集合A A和和B B的乘积定义为的乘积定义为 若集合若集合A=A= a,ba,b B=B= c,dc,d 则则 AB=AB= ac,ad,bc,bdac,ad,bc,bd (x=x=x)(x=x=x) 使用使用 * *表示表示 上的所有有穷长的串(包括上的所有有穷长的串(包括)的集合。的集合。* *称为称为的的。 从从 * *中除去中除去得到的集合记为得到的集合记为 + + 。 + +称为称为的的。* = 0 1 2 n + = 1 2 n * = 0 + = * = *+ = * -设设=0,1,则则* =, 0, 1, 00, 01, 10, 11, 000, 001,
10、010,设设=a,b=a,b,则则 * *=,a,b,aa,ab,ba,bb,aaa,aab,=,a,b,aa,ab,ba,bb,aaa,aab, + +=a,b,aa,ab,ba,bb,aaa,aab,=a,b,aa,ab,ba,bb,aaa,aab,四、文法和语言的形式定义四、文法和语言的形式定义1 1、文法的形式定义、文法的形式定义1 1)规则(重写规则、产生式或生成式):是)规则(重写规则、产生式或生成式):是一个有序对(一个有序对(,)。)。记为记为或或=,其中其中VV+ +,VV* * 。 称为规则的左部称为规则的左部( (或生成式的左部或生成式的左部) )。 称为规则的右部称为规
11、则的右部( (或生成式的右部或生成式的右部) )。2 2)文法)文法GSGS:文法为文法为(V VN N,V VT T,P P,S S) V VN N :非终结符集非终结符集 V VT T :终结符集终结符集 P P:产生式(规则)集合产生式(规则)集合 S S:开始符号(识别符号)开始符号(识别符号)V VN N、V VT T 和和 P P 是非空有穷集。是非空有穷集。S S 至少在一条规则至少在一条规则中作为左部出现。中作为左部出现。V VN NVVT T=, SV SVN NV=VV=VN NVVT T,称为文法称为文法G G的字母表(字汇表)的字母表(字汇表) 例例: : 文法文法G=
12、G=(V VN N,V VT T,P P,S S)V VN N = S , V = S , VT T = 0, 1 = 0, 1 P= S0S1, S01 P= S0S1, S01 S S为开始符号为开始符号例例: : 文法文法G=G=(V VN N,V VT T,P P,S S)V VN N = =标识符,字母,数字标识符,字母,数字 V VT T =a,b,c,x,y,z,0,1,9 =a,b,c,x,y,z,0,1,9P=P= a, a, z z 0, 0, 99S=S= 习惯上只将产生式写出。并有如下约定:习惯上只将产生式写出。并有如下约定:第一条产生式的左部是开始符号第一条产生式的左
13、部是开始符号用尖括号括起的是非终结符,否则为终结用尖括号括起的是非终结符,否则为终结符。或者大写字母表示非终结符,小写字符。或者大写字母表示非终结符,小写字母表示终结符母表示终结符G G可写成可写成GSGS,其中其中S S是开始符号是开始符号 例例:文法文法G=(VN,VT,P,S)VN = S , VT = 0, 1 P= S0S1, S01 S为开始符号为开始符号 可写成:可写成: G:S0S1 S01 或写成:或写成: GS:S0S1 S013 3、推导的定义、推导的定义 1 1)直接推导)直接推导“” 是文法是文法G G的产生式,的产生式,,V,V* *,若将,若将作用于作用于 v=v
14、=得到得到 w=,w=,则则记作记作 v vw w,读作读作v v(应用规则应用规则)直接产生直接产生w w(w w是是v v的的或或w w到到v v)例:例:G G:S0S1S0S1,S01S01直接推导:直接推导:0 0S1S100110011(v=0S1v=0S1,w=0011w=0011,使用规则使用规则S01S01,=0=0,=1=1)S S0S10S1(v=Sv=S,w=0S1w=0S1,使用规则使用规则S0S1S0S1,= =,= =)0 0S1S100S1100S11(v=0S1v=0S1,w=00S11w=00S11,使用规则使用规则S0S1S0S1,=0=0,=1=1)例例
15、 文法文法G=(VN,VT,P,S)VN =标识符,字母,数字标识符,字母,数字VT =a,b,c,x,y,z,0,1,9P= a, z z 0,0,99S=指出下面直接推导所使用的规则:指出下面直接推导所使用的规则: abcabc abc5abc52)长度为长度为n的推导(有限次推导)的推导(有限次推导) 若存在若存在v =w0 w1 . wn=w, (n0), 则称则称v出出w(或或w到到v). 记作记作 v w。3)若有若有v w,或或v=w, 则记为则记为v w+*例:例:G G: S0S1 S0S1, S01 S010S10S100S1100S11000S111000S1110000
16、1111 00001111 即即 0S1 000011110S1 00001111也记作也记作 0S1 000011110S1 00001111+*1 1)句型)句型 设设GS是一文法是一文法,如果符号串如果符号串x是从是从识别符号识别符号推推导出来的,即导出来的,即S x,则称则称x是文法是文法GS的句型。的句型。*例:例:G G: S0S1, S01S 0S1 00S11 000S111 00001111*2 2)句子)句子x仅由仅由终结符号终结符号组成组成(即即S x,且且xVVT T* *),),则称则称x是是GS的句子的句子。3 3)语言)语言 由文法由文法G G产生的所有句子组成的
17、集合叫做文法产生的所有句子组成的集合叫做文法G G所成描述的语言,记为所成描述的语言,记为L(G)L(G)。 例:例:G G: S0S1, S01 L(G)=0n1n|n1 注:产生式中含有递归式,产生的句子是无穷的注:产生式中含有递归式,产生的句子是无穷的*L(G)=x|S x,其中其中S为文法的开始符号为文法的开始符号,且且x VVT T* * 例例: :文法文法GS:(1)SdAdAB(2)AaA(3)Aaa(4)BBBb(5)BL(G)=?G G生成的每个串都在生成的每个串都在L(G)L(G)中中L(G)L(G)中的每个串确实能被中的每个串确实能被G G生成生成例:构造生成语言例:构造
18、生成语言L= 的文的文法。法。分析:分析:n n1 1,所以必须用递归规则。所以必须用递归规则。a a和和b b的的个数个数 一样多,但一样多,但c c的个数不同,所以将生成的个数不同,所以将生成含含 a,b a,b的部分与生成含的部分与生成含e e的部分分开,的部分分开,A A生成生成 abab,B B生成生成e.e. GZ:ZAB GZ:ZAB AaAb|ab AaAb|ab BeB| BeB|0, 1|inebainn4)4)文法的等价文法的等价 若若L L(G G1 1)=L=L(G G2 2),),则称文法则称文法G G1 1和和G G2 2是等价的。是等价的。如文法如文法G G1
19、1AA:A0R A0R 与与 G G2 2SS:S0S1 S0S1 等价等价 A01 S01A01 S01 RA1 RA1五五 文法的类型文法的类型 (1)0型文法型文法(短语文法短语文法):对任一产生式对任一产生式,都有都有(V(VN NVVT T) )+ +, (V (VN NVVT T) )* * (2 2)1 1型文法型文法( (上下文有关文法上下文有关文法) ): 对任一产生式对任一产生式,都有都有| |, 仅仅仅仅 SS除除外。即外。即1 1AA2 21 12 2( (A A在在V VN N中中,其他在其他在V V* *中中,) )(3 3)2 2型文法型文法(上下文无关文法上下文
20、无关文法): 对任一产生式对任一产生式,都有都有VVN N , (V (VN NVVT T) )* * 即即AA( (A A在在V VN N中中,在在V V* *中中,) )(4 4)3 3型文法型文法(正规文法正规文法):):任一产生式任一产生式的形式都的形式都为为AaBAaB或或AaAa,其中其中AVAVN N ,BVBVN N ,aVaVT T 例:例:1 1型(上下文有关)文法型(上下文有关)文法 文法文法GS:SaSBESaBEEBBEaBabbBbbbEbeeEee 例:例:2 2型(上下文无关)文法型(上下文无关)文法 文法文法GS: SaB|bAaB|bAAa|aS|bAAa|
21、aS|bAABb|bS|aBBb|bS|aBB 文法文法GS: S0A|1B|00A|1B|0A0A|1B|0S0A|1B|0SB1B|1|01B|1|0 例:定义标识符的例:定义标识符的3 3型(正规)文法型(正规)文法 文法文法GI:I lT lTI l lT lT lTT dT dTT l lT d d文法和语言文法和语言 0 0型文法产生的语言称为型文法产生的语言称为0 0型语言型语言 1 1型文法或上下文有关文法(型文法或上下文有关文法( CSG CSG )产生的语产生的语言称为言称为1 1型语言或上下文有关语言(型语言或上下文有关语言(CSLCSL) 2 2型文法或上下文无关文法(
22、型文法或上下文无关文法( CFG CFG )产生的语产生的语言称为言称为2 2型语言或上下文无关语言(型语言或上下文无关语言( CFL CFL ) 3 3型文法或正则(正规)文法(型文法或正则(正规)文法( RG RG )产生的语产生的语言称为言称为3 3型语言或正则(正规)语言(型语言或正则(正规)语言( RL RL )六六 上下文无关文法及其语法树上下文无关文法及其语法树 上下文无关文法有足够的能力描述现今程上下文无关文法有足够的能力描述现今程序设计语言的语法结构。序设计语言的语法结构。 算术表达式算术表达式 语句语句 赋值语句赋值语句 条件语句条件语句 循环语句循环语句 用于描述上下文无
23、关文法的用于描述上下文无关文法的句型推导句型推导的的直观方法直观方法 例例: : GS:SaASASbAASSSaAba S a A S S b A a a b a句型句型aabbaa的语法树(推导树)的语法树(推导树)叶子结点:树中没有子孙的结点。叶子结点:树中没有子孙的结点。从左到右读出推导树的叶子标记,所得的句从左到右读出推导树的叶子标记,所得的句型为推导树的结果。也把该推导树称为该句型为推导树的结果。也把该推导树称为该句型的语法树。型的语法树。推导过程中施用产生式的推导过程中施用产生式的顺序顺序 例例: GS:SaASASbAASSSaAba S a A S S b A a a b a
24、句型句型aabbaa的语法树(推导树)的语法树(推导树)SaASaAaaSbAaaSbbaaaabbaa在推导的任何一步在推导的任何一步,其中其中、是句型,是句型,都是对都是对中的最左(右)非终结符进行替换。中的最左(右)非终结符进行替换。 最右推导被称为最右推导被称为。 由规范推导所得的句型称为由规范推导所得的句型称为SaASaAaaSbAaaSbbaaaabbaa(最右推导最右推导)SaASaSbASaabASaabbaSaabbaa(最左推导最左推导)SaASaSbASaSbAaaabAaaabbaa 例例: GS:SaASASbAASS Sa Aba问题:一个句型是否对应唯一的一棵语法
25、树?问题:一个句型是否对应唯一的一棵语法树? 例:例:GE:GE:E iE iE E+EE E+EE EE E* *E EE (E)E (E) E E E + E E + E E E * * E i E i i i i i E E E E * * E E i E + E i E + E i i i i句型句型 i*i+i 的两个不同的最左推导的两个不同的最左推导:推导推导2:E E*E i*E i*E+E i*i+E i*i+i推导推导1:E E+E E*E+E i*E+E i*i+E i*i+i3 3、二义文法、二义文法若一个文法存在若一个文法存在某个某个句子对应两棵不同的语法句子对应两棵不
26、同的语法树,则称这个文法是树,则称这个文法是二义二义的。的。或者,若一个文法存在或者,若一个文法存在某个某个句子有两个不同的句子有两个不同的最左(右)推导,则称这个最左(右)推导,则称这个文法文法是是二义二义的。的。产生某上下文无关语言的每一个文法都是二义产生某上下文无关语言的每一个文法都是二义的,则称此的,则称此语言语言是是先天二义先天二义的。的。排除文法二义性的两种方法:排除文法二义性的两种方法:(1 1)在语义上加些限制(如优先顺序和结)在语义上加些限制(如优先顺序和结合律)。合律)。(2 2)重构无二义性的文法。)重构无二义性的文法。GE: E IGE: E I E E+E E E+E
27、 E EE E* *E E E (E) E (E)GE: E T|E+TGE: E T|E+T T F|T T F|T* *F F F F (E E)|i|i 练习:有文法练习:有文法GN: NSE|E S SD|D E 0|2|4|6|8|10 D 0|1|2|3|4|5|6|7|8|9(1)证明此文法有二义性证明此文法有二义性(2)此文法描述的语言是什么?)此文法描述的语言是什么?(3)试写出另一文法,其产生的语言和)试写出另一文法,其产生的语言和GN产产生的语言等价且是无二义性的。生的语言等价且是无二义性的。七、句型的分析七、句型的分析就是识别一个符号串是否为某文法的就是识别一个符号串是
28、否为某文法的句型,是某个推导的构造过程。句型,是某个推导的构造过程。在语言的编译实现中,把完成句型分析的程序在语言的编译实现中,把完成句型分析的程序称为称为或或。分析算法又称。分析算法又称识别识别算法算法。从左到右的分析算法从左到右的分析算法,即总是从左到右地识别,即总是从左到右地识别输入符号串,首先识别符号串中的最左符号,输入符号串,首先识别符号串中的最左符号,进而依次识别右边的一个符号。进而依次识别右边的一个符号。1、自上而下的语法分析:从文法的开始符号出发,、自上而下的语法分析:从文法的开始符号出发,反复使用各种产生式,寻找与输入符号串匹配的推反复使用各种产生式,寻找与输入符号串匹配的推
29、导。导。 例:文法例:文法G:S cAd A ab A a识别输入串识别输入串 w = cabd 是否该文法的句子是否该文法的句子SSScAdcAd a b推导过程推导过程:cabdcAd S2、自下而上的语法分析自下而上的语法分析:从输入符号串开始,逐从输入符号串开始,逐步进行归约,直至归约到文法的开始符号。步进行归约,直至归约到文法的开始符号。 例:文法例:文法G:S cAd A ab A a识别输入串识别输入串 w = cabd 是否该文法的句子是否该文法的句子SAA c a b d c a b d c a b d 规约过程规约过程:cabdcAd S3 3、句型分析的有关问题、句型分析
30、的有关问题1 1)如何选择使用哪个产生式进行推导?)如何选择使用哪个产生式进行推导?假定要被代换的最左非终结符号是假定要被代换的最左非终结符号是V V,且有且有n n条条规则:规则:VA1|A2|AnVA1|A2|An,那么如何确定用哪个那么如何确定用哪个右部去替代右部去替代V V?2 2)如何识别可归约的串?如何识别可归约的串?在自下而上的分析方法中,在分析程序工作的在自下而上的分析方法中,在分析程序工作的每一步,都是从当前串中选择一个子串,将它每一步,都是从当前串中选择一个子串,将它归约到某个非终结符号,该子串称为归约到某个非终结符号,该子串称为“可归约可归约串串”(“4 4、短语、直接短语、句柄的定义:、短语、直接短语、句柄的定义:文法文法GS,是是G的一个句型的一个句型,如果如果: S A且且A 则称则称是句型是句型相对于非终结符相对
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 二零二五年度智能交通管理系统采购意向合同3篇
- 2025年度环境卫生应急物资储备承包合同3篇
- 2025年度企业资源规划软件许可与集成实施服务合同2篇
- 二零二五年度虚拟现实技术研发人员劳动合同3篇
- 2025年度台球室租赁与电子竞技比赛组织合同3篇
- 2025年度特种养殖场工人劳动合同3篇
- 2025年度定制木门产品定制与家居一体化解决方案合同3篇
- 2025年度顶级篮球运动员专属转会合同3篇
- 二零二五农机作业与维修一体化服务合同3篇
- 二零二五年度企业内部廉洁自律管理实施合同3篇
- 【西平李氏】忠武郡王李晟后裔分布及部分家谱
- 水库回水计算(实用)
- 人力资源管理概论全套课件
- 伊索寓言-狗和影子课件
- 卸船机用行星减速机的设计-毕业设计
- 中班美术活动美丽的蝴蝶教案【含教学反思】
- 北师大版九年级数学上册教学教学工作总结
- 光储电站储能系统调试方案
- (完整)小学语文考试专用作文方格纸
- 管理供应商 供应商绩效评估
- 烟花爆竹工程设计安全规范
评论
0/150
提交评论