Part2高级语言及其语法描述课件

Part2Part2高级语言及其语法描述高级语言及其语法描述授课：胡静授课：胡静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更多的概念和一些约定A,B,C,用来表示非终结符符号串和符号串集合的运算符号串和符号串集合的运算符号串和符号串集合的运算符号串和符号串集合的运算符号串和符号串集合的运算符号串和符号串集合的运算Part2高级语言及其语法描述课件Part2高级语言及其语法描述课件将字符看做符号，则单词就是符号串，单将字符看做符号，则单词就是符号串，单词集合就是符号串的集合词集合就是符号串的集合将单词看做符号，则句子就是符号串，而将单词看做符号，则句子就是符号串，而所有句子的集合（语言）就是符号串的集所有句子的集合（语言）就是符号串的集合合Part2高级语言及其语法描述课件文法的直观概念文法的直观概念文法的直观概念Part2高级语言及其语法描述课件规则、字母表均为有限集合规则、字母表均为有限集合句子长度是有限的句子长度是有限的生成的句子个数是无限的生成的句子个数是无限的Part2高级语言及其语法描述课件Part2高级语言及其语法描述课件Part2高级语言及其语法描述课件Part2高级语言及其语法描述课件语法树语法树语法（推导）树来描述一个句子的语法结构语法（推导）树来描述一个句子的语法结构识别符号识别符号语法树语法（推导）树来描述一个句子的语法结构识别符号关于文法的定义关于文法的定义定义定义3.1文法文法G定义为四元组（定义为四元组（VN,VT,P,S）。）。其中其中VN为非终结符号（或语法实体，或变量）集；为非终结符号（或语法实体，或变量）集；VT为终结符号集；为终结符号集；P为产生式（也称规则）的集合；为产生式（也称规则）的集合；VN,VT和和P是非空有穷集。是非空有穷集。S称做识别符号或开始符号，是一个非终结符称做识别符号或开始符号，是一个非终结符（S VN），至少要在一条规则中作为左部出现。），至少要在一条规则中作为左部出现。VN和和VT不含公共元素，即不含公共元素，即VNVT=。通常。通常V表示表示VNVT，V称为文法称为文法G的字母表或字汇表。的字母表或字汇表。例例3.1 文法文法G=（VN，VT，P，S）VN=S,VT=0,1 P=S0S1,S01 S为开始符号为开始符号文法可以简写，只需要指出开始符号和产生式即可。文法可以简写，只需要指出开始符号和产生式即可。关于文法的定义定义3.1关于文法的定义（续）关于文法的定义（续）定义定义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 00001111G关于文法的定义（续）定义3.2G关于文法的定义（续）关于文法的定义（续）定义定义3.3如果存在直接推导的序列：如果存在直接推导的序列：v=w0=w1=w2=wn=w，(n0)，则称，则称v推导出（产生）推导出（产生）w（推导长度为（推导长度为n）。）。记做记做v=+w。定义定义3.4若有若有v=+w，或，或v=w，则记做，则记做v=*w。规范推导（最右推导）规范推导（最右推导）最左推导：若规则右端符号串中有两个以上的非终结最左推导：若规则右端符号串中有两个以上的非终结符时，先推导左边的。符时，先推导左边的。最右推导：若规则右端符号串中有两个以上的非终结最右推导：若规则右端符号串中有两个以上的非终结符时，先推导右边的。符时，先推导右边的。关于文法的定义（续）定义3.3关于文法的定义（续）关于文法的定义（续）定义定义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|n1关于文法的定义（续）定义3.5关于文法的定义（续）关于文法的定义（续）定义定义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)关于文法的定义（续）定义3.7Part2高级语言及其语法描述课件文法的类型文法的类型 Chomsky将文法分为四种类型：将文法分为四种类型：0型文法：对任一产生式型文法：对任一产生式，都有，都有(VNVT)+，(VNVT)*1型文法：对任一产生式型文法：对任一产生式，都有，都有|，仅仅仅仅 S除外除外2型文法：对任一产生式型文法：对任一产生式，都有，都有VN，(VNVT)*3型文法：任一产生式型文法：任一产生式的形式都为的形式都为AaB或或Aa，其中其中AVN，BVN，aVT。上述叫做右线性文法，另有左线性文法，二者等价。上述叫做右线性文法，另有左线性文法，二者等价。文法的类型 Chomsky将文法分为四种类型：文法的类型举例文法的类型举例1型（上下文有关）文法型（上下文有关）文法 文法文法GS：SCDAbbA CaCABaaB CbCBBbbBADaD CBDbD DAabDL(G)=ww|wa,b*文法的类型举例1型（上下文有关）文法文法的类型举例文法的类型举例2型（上下文无关）文法型（上下文无关）文法 文法文法GS：SaB|bAAa|aS|bAABb|bS|aBB 文法文法GS：S0A|1B|0A0A|1B|0SB1B|1|0文法的类型举例2型（上下文无关）文法文法的类型举例文法的类型举例定义标识符的定义标识符的3型（正规）文法型（正规）文法 文法文法GI：I lTI lT lTT dTT lT d文法的类型举例定义标识符的3型（正规）文法文法和语言文法和语言0型文法型文法0型文法（短语文法）的能力相当于图灵机，可以表征任何递归型文法（短语文法）的能力相当于图灵机，可以表征任何递归可枚举集，而且任何可枚举集，而且任何0型语言都是递归可枚举的型语言都是递归可枚举的1型文法（上下文有关文法）型文法（上下文有关文法）产生式的形式为产生式的形式为1A212，即只有，即只有A出现在出现在1和和2的上下文中时，才允许的上下文中时，才允许取代取代A。其识别系统是线性界限自动机。其识别系统是线性界限自动机。2型文法（上下文无关文法）型文法（上下文无关文法）产生式的形式为产生式的形式为A，取代取代A时与时与A的上下文无关。其识别系的上下文无关。其识别系统是不确定的下推自动机。统是不确定的下推自动机。3型文法（正则文法）型文法（正则文法）产生的语言是有穷自动机（产生的语言是有穷自动机（FA）所接受的集合）所接受的集合文法和语言0型文法上下文无关文法上下文无关文法上下文无关文法有足够的能力描述现今程序设计语言的语法结构上下文无关文法有足够的能力描述现今程序设计语言的语法结构算术表达式算术表达式语句语句赋值语句赋值语句条件语句条件语句读语句读语句文法文法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 aa a上下文无关文法的语法树用于描述上下文无关文法的句型推导的直观上下文无关文法的语法树推导过程中施用产生式的顺序 例例:GS:SaASASbAASSSaAba S a A S S b A a a b aSaASaAaaSbAaaSbbaaaabbaaSaASaSbASaabASaabbaSaabbaaSaASaSbASaSbAaaabAaaabbaa上下文无关文法的语法树推导过程中施用产生式的顺序 例:G Thanks for your time!Questions&AnswersPart2高级语言及其语法描述课件