《Part2高级语言及其语法描述课件.ppt》由会员分享，可在线阅读，更多相关《Part2高级语言及其语法描述课件.ppt（31页珍藏版）》请在三一办公上搜索。
1、Part2高级语言及其语法描述,授课：胡静,内容提要,预备知识形式语言基础文法和语言的定义（语法定义、语义定义）术语和概念文法的表示：正则表达式和语法树文法和语言的分类,预备知识,更多的概念和一些约定,A,B,C,用来表示非终结符a,b,c,表示终结符,X,Y,Z 可以用来表示终结符或者非终结符,w,x,y,z 表示终结符号串,表示由终结符或非终结符构成的符号串在产生式A中，A 是产生式的左边(lefthand side,LHS)是产生式的右边(righthand side,RHS)A1|n 表示产生式 A 1,A n,符号串和符号串集合的运算,符号串和符号串集合的运算,将字符看做符号，则单词
2、就是符号串，单词集合就是符号串的集合将单词看做符号，则句子就是符号串，而所有句子的集合（语言）就是符号串的集合,文法的直观概念,规则、字母表均为有限集合句子长度是有限的生成的句子个数是无限的,语法树,语法（推导）树来描述一个句子的语法结构,识别符号,关于文法的定义,定义3.1文法G定义为四元组（VN,VT,P,S）。其中VN为非终结符号（或语法实体，或变量）集；VT为终结符号集；P为产生式（也称规则）的集合；VN,VT和P是非空有穷集。S称做识别符号或开始符号，是一个非终结符（S VN），至少要在一条规则中作为左部出现。VN和VT不含公共元素，即VNVT=。通常V表示VNVT，V称为文法G的字
3、母表或字汇表。例3.1 文法G=（VN，VT，P，S）VN=S,VT=0,1 P=S0S1,S01 S为开始符号文法可以简写，只需要指出开始符号和产生式即可。,关于文法的定义（续）,定义3.2如是文法G=(VN,VT,P,S)的规则(或说是P中第一个产生式)，和是V*中的任意符号串，若有符号串v，w满足：v=，w=，则说v（应用规则）直接产生w，或说w是v的直接推导。（v=w）例：GS：S0S1，S01 S 0S1 00S11 000S111 00001111,G,关于文法的定义（续）,定义3.3如果存在直接推导的序列：v=w0=w1=w2=wn=w，(n0)，则称v推导出（产生）w（推导长度
4、为n）。记做v=+w。定义3.4若有v=+w，或v=w，则记做v=*w。规范推导（最右推导）最左推导：若规则右端符号串中有两个以上的非终结符时，先推导左边的。最右推导：若规则右端符号串中有两个以上的非终结符时，先推导右边的。,关于文法的定义（续）,定义3.5设GS是一文法，如果符号串x是从识别符号推导出来的，即有S=*x，则称x是文法GS的句型。若x只由终结符号组成，则称x为GS的句子。定义3.6文法G所产生的语言定义为集合x|S=*x，其中S为文法的开始符号，且xVT*。可用L(G)表示该集合。例：G：S0S1，S01S 0S1 00S11 000S111 00001111L(G)=0n1n
5、|n1,关于文法的定义（续）,定义3.7若L(G1)=L(G2)，则称文法G1和G2是等价的。例1：如文法G1A：A0R 与G2S：S0S1 等价 A01 S01 RA1例2：G1E:E i 与 G2E：E T|E+T等价 E E+E T F|T*F E E*E F（E）|i E(E),文法的类型,Chomsky将文法分为四种类型：0型文法：对任一产生式，都有(VNVT)+，(VNVT)*1型文法：对任一产生式，都有|，仅仅 S除外2型文法：对任一产生式，都有VN，(VNVT)*3型文法：任一产生式的形式都为AaB或Aa，其中AVN，BVN，aVT。上述叫做右线性文法，另有左线性文法，二者等价
6、。,文法的类型举例,1型（上下文有关）文法 文法GS：SCDAbbA CaCABaaB CbCBBbbBADaD CBDbD DAabDL(G)=ww|wa,b*,文法的类型举例,2型（上下文无关）文法 文法GS：SaB|bAAa|aS|bAABb|bS|aBB 文法GS：S0A|1B|0A0A|1B|0SB1B|1|0,文法的类型举例,定义标识符的3型（正规）文法 文法GI：I lTI lT lTT dTT lT d,文法和语言,0型文法0型文法（短语文法）的能力相当于图灵机，可以表征任何递归可枚举集，而且任何0型语言都是递归可枚举的1型文法（上下文有关文法）产生式的形式为1A212，即只有
7、A出现在1和2的上下文中时，才允许取代A。其识别系统是线性界限自动机。2型文法（上下文无关文法）产生式的形式为A，取代A时与A的上下文无关。其识别系统是不确定的下推自动机。3型文法（正则文法）产生的语言是有穷自动机（FA）所接受的集合,上下文无关文法,上下文无关文法有足够的能力描述现今程序设计语言的语法结构算术表达式语句赋值语句条件语句读语句文法G=(E,+,*,I,(,),P,E ifthen P:E i|ifthenelse E E+EE E*EE(E),上下文无关文法的语法树,用于描述上下文无关文法的句型推导的直观方法,例:GS:SaASASbAASSSaAba,S a A S S b A b a,句型aabbaa的语法树（推导树）,叶子结点：树中没有子孙的结点。从左到右读出推导树的叶子标记，所得的句型为推导树的结果。也把该推导树称为该句型的语法树。,a,a,上下文无关文法的语法树,推导过程中施用产生式的顺序,例:GS:SaASASbAASSSaAba,SaASaAaaSbAaaSbbaaaabbaaSaASaSbASaabASaabbaSaabbaaSaASaSbASaSbAaaabAaaabbaa,Thanks for your time!Questions&Answers,
