part2高级语言及其语法描述

《part2高级语言及其语法描述》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、Part2高级语言及其语法描述授课：胡静内容提要预备知识——形式语言基础文法和语言的定义（语法定义、语义定义）术语和概念文法的表示：正则表达式和语法树文法和语言的分类预备知识更多的概念和一些约定A,B,C,…用来表示非终结符a,b,c,…表示终结符…,X,Y,Z可以用来表示终结符或者非终结符…,w,x,y,z表示终结符号串α,β,γ,δ,…表示由终结符或非终结符构成的符号串在产生式A→α中，A是产生式的左边(lefthandside,LHS)α是产生式的右边(righthandside,RHS)A→α1

2、…

3、αn表示产生式A→α1,…,A→αn符号串和符号

4、串集合的运算符号串和符号串集合的运算将字符看做符号，则单词就是符号串，单词集合就是符号串的集合将单词看做符号，则句子就是符号串，而所有句子的集合（语言）就是符号串的集合文法的直观概念规则、字母表均为有限集合句子长度是有限的生成的句子个数是无限的语法树语法（推导）树来描述一个句子的语法结构识别符号关于文法的定义定义3.1文法G定义为四元组（VN,VT,P,S）。其中VN为非终结符号（或语法实体，或变量）集；VT为终结符号集；P为产生式（也称规则）的集合；VN,VT和P是非空有穷集。S称做识别符号或开始符号，是一个非终结符（S∈VN），至少要在一条规则中作为左

5、部出现。VN和VT不含公共元素，即VN∩VT=Φ。通常V表示VN∪VT，V称为文法G的字母表或字汇表。例3.1文法G=（VN，VT，P，S）VN={S},VT={0,1}P={S→0S1,S→01}S为开始符号文法可以简写，只需要指出开始符号和产生式即可。关于文法的定义（续）定义3.2如α→β是文法G=(VN,VT,P,S)的规则(或说是P中第一个产生式)，γ和δ是V*中的任意符号串，若有符号串v，w满足：v=γαδ，w=γβδ，则说v（应用规则α→β）直接产生w，或说w是v的直接推导。（v=>w）例：G[S]：S→0S1，S→01S0S100S11

6、000S11100001111G关于文法的定义（续）定义3.3如果存在直接推导的序列：v=w0=>w1=>w2…=>wn=w，(n>0)，则称v推导出（产生）w（推导长度为n）。记做v=>+w。定义3.4若有v=>+w，或v=w，则记做v=>*w。规范推导（最右推导）最左推导：若规则右端符号串中有两个以上的非终结符时，先推导左边的。最右推导：若规则右端符号串中有两个以上的非终结符时，先推导右边的。关于文法的定义（续）定义3.5设G[S]是一文法，如果符号串x是从识别符号推导出来的，即有S=>*x，则称x是文法G[S]的句型。若x只由终结符号组成，则称x为

7、G[S]的句子。定义3.6文法G所产生的语言定义为集合{x

8、S=>*x，其中S为文法的开始符号，且x∈VT*}。可用L(G)表示该集合。例：G：S→0S1，S→01S0S100S11000S11100001111L(G)={0n1n

9、n≥1}关于文法的定义（续）定义3.7若L(G1)=L(G2)，则称文法G1和G2是等价的。例1：如文法G1[A]：A→0R与G2[S]：S→0S1等价A→01S→01R→A1例2：G1[E]:E→i与G2[E]：E→T

10、E+T等价E→E+ET→F

11、T*FE→E*EF→（E）

12、iE→(E)文法的类型Chomsky将文法

13、分为四种类型：0型文法：对任一产生式α→β，都有α∈(VN∪VT)+，β∈(VN∪VT)*1型文法：对任一产生式α→β，都有

14、β

15、≥

16、α

17、，仅仅S→ε除外2型文法：对任一产生式α→β，都有α∈VN，β∈(VN∪VT)*3型文法：任一产生式α→β的形式都为A→aB或A→a，其中A∈VN，B∈VN，a∈VT。上述叫做右线性文法，另有左线性文法，二者等价。文法的类型举例1型（上下文有关）文法文法G[S]：S→CDAb→bAC→aCABa→aBC→bCBBb→bBAD→aDC→εBD→bDD→εAa→bDL(G)={ww

18、w∈{a,b}*}文法的类型举例2型（上下

19、文无关）文法文法G[S]：S→aB

20、bAA→a

21、aS

22、bAAB→b

23、bS

24、aBB文法G[S]：S→0A

25、1B

26、0A→0A

27、1B

28、0SB→1B

29、1

30、0文法的类型举例定义标识符的3型（正规）文法文法G[I]：I→lTI→lT→lTT→dTT→lT→d文法和语言0型文法0型文法（短语文法）的能力相当于图灵机，可以表征任何递归可枚举集，而且任何0型语言都是递归可枚举的1型文法（上下文有关文法）产生式的形式为α1Aα2→α1βα2，即只有A出现在α1和α2的上下文中时，才允许β取代A。其识别系统是线性界限自动机。2型文法（上下文无关文法）产生式的形式为A→β，β取代

31、A时与A的上下文无关。其识别系统是不确定的下推自动机。3型文法（正