编译原理 文法和语言.ppt
《编译原理 文法和语言.ppt》由会员分享,可在线阅读,更多相关《编译原理 文法和语言.ppt(59页珍藏版)》请在三一文库上搜索。
1、1,第三章 文法和语言,语言是一个记号系统,完整的定义包括语法和语义两方面。语法是一组规则,用它可以形成和产生一个合适的程序。文法就是阐明语法的一个重要的形式工具。语义包括静态语义和动态语义,阐明语义要比语法困难的多。 本章主要讨论文法和语言的概念,上下文无关文法及其句型的分析。,2,本章内容,3.1 文法的直观概念 3.2 符号和符号串 3.3 文法和语言的形式定义 3.4 文法的类型 3.5 上下文无关文法及其语法树 3.6 句型的分析 3.7 有关文法实用中的一些说明 3.8 典型例题及解答,3,3.1 文法的直观概念,如何来描述一种语言? 如果语言是有穷的(只含有有穷多个句子),可以将
2、句子逐一列出来表示; 如果语言是无穷的,语言的有穷表示有两个途经: 生成方式(文法):语言中的每个句子可以用严格定义的规则来构造。 识别方式(自动机):用一个过程,当输入的一任意串属于语言时,该过程经有限次计算后就会停止并回答“是”,若不属于,要么能停止并回答“不是”,要么永远继续下去。 参见课本句子组成的实例。,4,3.2 符号和符号串,1、字母表,字母表是符号的非空有穷集合。任何程序语言都有自己的字母表,例如: 1.计算机语言:由符号“0”和“1”组成的字母表, =0,1 2. ASCII字符集; 3. Pascal字母表为: =AZ, az, 09, +, -, *, /, ,:, ,
3、; ,., , (, ), , , , ,5,3.2 符号和符号串,2、符号串,一. 符号串的定义 (1)是上的一个符号串。 (2)若x是上的符号串,而a是的元素,则xa是 上的符号串。 (3)y是上的符号串,当且仅当它由(1)和(2)导出。 由字母表中的符号所组成的的任何有穷序列被称之为该字母表上的符号串,也称作“字“。,6,3.2 符号和符号串,二 术语 设s是符号串 前缀: 移走s的尾部的零个或多于零个符号 后缀: 删去s的头部的零个或多于零个符号 子串: 从s中删去一个前缀和一个后缀 子序列: 从s中删去零个或多于零个符号(这些符号不要求是连续的) 逆转: 将s中的符号按相反次序写出而
4、得到的符号串。 长度: 是该符号串中的符号的数目。例|aab|=3,|=0。,7,例 :符号串s=banana 前缀:,b,ba,ban,bana,banan,banana 后缀:banana,anana,nana,ana,na,a, 子串: banana,anana,banan,anan, 真前缀,真后缀,真子串: xsx 子序列: baa(这些符号不要求是连续的) 逆转:ananab 长度:banana=6,3.2 符号和符号串,8,三、符号串的运算 1.连接:设x和y是符号串,它们的连接 xy是把y的符号写在x的符号之后得到的符号串。例如,x=ba,y=nana,xy=banana. 2
5、.方幂:x0=; x1=x; x2=xx; ; xn=xn-1x; 例: x=ba 则 x1= ba; x2=baba; x3=bababa;,3.2 符号和符号串,9,四. 符号串集合(语言)的运算 设L和M是两个符号串集合,则 1.合并:LMs|sL or sM 2.连接:LM st|sL and tM 3.方幂: L0=, L1L, L2LL, ., LnLn-1L 4. 语言L的闭包,记作L*, L*Li(i=0) =L0L1L2L3 5语言L的正闭包,记作L+(L+L L*) L+Li(i =1) =L1L2L3L4,3.2 符号和符号串,10,例如:L=AZ,az D=09 1LD
6、=AZ,az ,09 2LD是由所有用一个字母后跟一个数字组成的符号串所构成的集合。 3L4是由所有的四个字母的符号串构的集合。 4L(LD)* 是由所有的字母打头的字母和数字组成的符号串所构成的集合. 5D+是由所有的长度大于等于1的数字串所构成的集合.,3.2 符号和符号串,11,文法的定义 推导的概念 句型、句子和语言的定义,3. 3 文法和语言的形式定义,12,文法定义,文法G 定义为四元组(VN,VT,P,S),其中VN :非终结符号集;VT :终结符号集;P: 规则的集合;并且VN,VT和P是非空有穷集。S:称作开始符(识别符),是一个非终结符,它至少要在一条产生式中作为左部出现。
7、 注:VN和VT不含公共的元素,即VN VT = ,用V表示VN VT ,称为文法G的字母表 规则(重写规则、产生式或生成式),是形如的(,)有序对,其中是字母表V的正闭包V+中的一个符号,是V*中的一个符号。 称为规则的左部, 称作规则的右部。,13,文法的定义,例: 文法G=(VN,VT,P,S) VN = S , VT = 0, 1 P= S0S1, S01 S为开始符号,例: 文法G=(VN,VT,P,S) VN =标识符,字母,数字 VT =a,b,c,x,y,z,0,1,9 P= a z 0 9 S=,15,元符号: | 一般不用将文法G的四元组显式的写出来,只写出产生式即可,并约
8、定第一条产生式的左部为识别符。习惯上大写字母表示非终结符,小写字母表示终结符,有时也将G写为GS,(1) G:SaAb Aab AaAb A,(2) GS:Aab AaAb A SaSb (3) GS: Aab|aAb| SaSb,文法的写法,16,推导的定义,直接推导“” 是文法G的产生式,若有v,w满足v=,w=,其中V*,V*,则称v直接推导到w,记作 v w 也称w直接归约到v 例:G:S0S1,S01 0S1 00S11 00S11 000S111 000S111 00001111 S 0S1,17,推导的定义,例: . ( . ) . . ( ) VAR;BEGIN READ()E
9、ND. VAR A;BEGIN READ( ) END. ( A) VAR A;BEGIN READ( ) END. VAR A;BEGIN READ( A) END. ( A),18,推导的定义,若存在v =w0 w1 . wn=w,(n0) 则记为v +w,称作v推导出w,或w归约到v 若有v =+w 或 v=w, 则记为v =* w,19,例: G: S0S1, S01 0S1 00S11 00S11 000S111 000S111 00001111 S 0S1 00S11 000S111 00001111 S =+ 00001111 S =* S 00S11 =* 00S11,20,句
10、型、句子的定义,句型 有文法G,若S =*x,则称x是文法G的句型。 句子 有文法G,若S =*x,且xVT*,则称x是文法G的句子。 例: G:S0S1, S01 S 0S1 00S11 000S111 00001111 G的句型S,0S1 ,00S11 ,000S111,00001111 G的句子00001111, 01,21,句型、句子,例:GE: EE+T|T TT*F|F F(E)|a EE+T T+T F+T a+T a+T*F a+F*F a+a*F a+a*a 句子:用符号a,+,*,(和)构成的算术表达式,22,(文法生成的)语言的定义,由文法G生成的语言记为L(G),它是文
11、法G的一切句子的集合: L(G)=x|S =* x,其中S为文法的开始符号,x VT* 例:G: S0S1, S01 L(G)=0n1n|n1,例 文法GS: (1)SaSBE (2)SaBE (3)EBBE (4)aBab (5)bBbb (6)bEbe (7)eEee L(G)= anbnen | n1 G生成的每个串都在L(G)中 L(G)中的每个串确实能被G生成 分析参见课本P37.,24,文法的等价,若L(G1)=L(G2),则称文法G1和G2是等价的。 例:文法G1A:A0R 与 G2S:S0S1 等价 A01 S01 RA1,25,3.4 文法的类型,通过对产生式施加不同的限制,
12、文法可分为以下四类: 0型文法:对任一产生式,都有(VNVT)+, (VNVT)*。 0型文法的能力相当于图灵机,可以表征任何递归可枚举集,且任何0型语言都是递归可枚举的。 0型文法描述的语言为0型语言,用L0表示。 例如 : aSbcAd,26,3.4 文法的类型,1型文法:对任一产生式,都有|, 仅仅 S除外。 1型文法又称作上下文有关文法(context-sensitive): 其产生式的形式为1A212,即只有A出现在1和2的上下文中时,才允许取代A。其识别系统是线性界限自动机。 该文法描述的语言为1型语言或上下文有关语言,用L1表示。 例如:aUbaABBaab,27,3.4 文法的
13、类型,2型文法:对任一产生式,都有VN , (VNVT)* 2型文法又称作上下文无关文法(context-free): 该文法相当于对1型文法中的规则形式加以限制,即要求1和2必须为空。 2型文法描述的语言为2型语言或上下文无关语言,用L2表示。其识别系统是不确定的下推自动机。,28,3.4 文法的类型,例:2型(上下文无关)文法 文法GS: SAB ABS|0 BSA|1,29,3型文法:任一产生式的形式都为AaB或Aa,其中AVN ,BVN ,aVT* 3型文法又叫正规文法,产生的语言为3型语言(正规语言),是有穷自动机所接受的集合。 高级程序设计语言的单词符号,如标识符、无符号整数等都是
14、采用3型文法来描述的。,3.4 文法的类型,30,3.4 文法的类型,GS: S0A|1B|0 A0A|1B|0S B1B|1|0,GI: I lT I l T lT T dT T l T d,例: 3型文法,31,3.4 文法的类型,0型文法,四类文法之间的逐级“包含”关系,3型文法,32,3.5 上下文无关文法及其语法树,上下文无关文法有足够的能力描述程序设计语言的语法结构 实例参见课本P39-40 例3.6(描述表达式及各种语句) 语法树:是描述上下文无关文法句型推导的直观工具。,33,语法树的定义 设G=( VN,VT,P,S)为一上下文无关文法,若一棵树满足下列4个条件,则此树为G的
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 编译原理 文法和语言 编译 原理 文法 语言
链接地址:https://www.31doc.com/p-2258576.html