编译原理与技术讲义-第3章

《编译原理与技术讲义-第3章》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、编译原理与技术第3章程序语言的语法描述青岛大学信息工程学院主要内容文法和语言文法的分类文法的等价变换语法分析概述编译原理与技术2程序语言的语法描述程序语言的定义程序语言通常是一个能完整、准确和规则地表达人们的意图，并用以指挥或控制计算机工作的“符号系统”。它完整的定义包括语法、语义及语用三个方面。一个程序语言的语法是指这样一组规则，使用它可以形成和产生一个合适的程序。这些规则一部分称为词法规则，另一部分称为语法规则（或产生规则）。编译原理与技术3程序语言的语法描述一个程序语言的语义是指这样一组规则

2、，使用它可以定义一个程序的意义。静态语义是一系列限定规则，确定哪些合乎语法的程序是合适的；动态语义也称作运行语义或执行语义，表明程序要做些什么，要计算什么。语用表示语言符号及其使用者之间的关系，涉及符号的来源、使用和影响。编译原理与技术43.1文法和语言文法的形式定义定义3.1:定义四元组G=(VN，VT，P，S)是一个文法。其中VN,VT和P都是非空有限集合，分别称为非终结符号集合、终结符号集合及产生式集合。S称作识别符号或开始符号，它是一个非终结符，至少要在一条产生式中作为左部出现。VN和VT

3、不含公共元素，即VN∩VT=。通常用V表示VN∪VT，称为文法G的字母表。编译原理与技术53.1文法和语言例3.1：文法G1=(VN,VT,P,S)，其中VN={S}，VT={0,1}，P={S→0S1,S→01}。该文法只有一个非终结符S，有两个终结符0和1，有两条产生式，开始符号是S。很多时候，不用将文法G的四元组显式地表示出来，而只将产生式写出。一般约定，第一条产生式的左部是开始符号，用尖括号括起来的是非终结符号，不用尖括号括起来的是终结符号，或者用大写字母表示非终结符号，小写字母表示终结

4、符号。另外也有一种习惯写法，将G写成G[S]，其中S是开始符号。因此，例3.1还可以写成：G：S→0S1或G[S]：S→0S1S→01S→01编译原理与技术63.1文法和语言有时，为书写简洁，常把相同左部的产生式，形如A→α1,A→α2,…,A→αn，缩写为：A→α1

5、α2

6、…

7、αn。这里的元符号

8、读做“或”。如，例3.1的产生式可以写成S→0S1

9、01。★注意元符号和源符号的区别：文法中使用的元符号→或∷=表示左部由右部定义，

10、表示定义同一个左部的几个可选择的右部。而源符号是指文法定义的语言中的

11、符号，全部由文法的终结符构成。编译原理与技术73.1文法和语言例3.2：文法G2=(VN,VT,P,S)，其中VN={标识符,字母,数字}，VT={a,b,c,…,x,y,z,0,1,…,9}，P={〈标识符〉→〈字母〉

12、〈标识符〉〈字母〉

13、〈标识符〉〈数字〉〈字母〉→a

14、b

15、…

16、z〈数字〉→0

17、1

18、…

19、9}S=〈标识符〉，这里使用尖括号〈和〉括起非终结符。编译原理与技术83.1文法和语言例3.3：一个文法的几种写法：①G=({S,A},{a,b},P,S)其中P={S→aAb,A→ab,A→aA

20、b,A→ε}②G:S→aAbA→abA→aAbA→ε③G[S]:A→abA→aAbA→εS→aAb④G[S]:A→ab

21、aAb

22、εS→aAb编译原理与技术93.1文法和语言推导与归约定义3.2:设α→β是文法G=(VN，VT，P，S)的产生式，γ和δ是V*中的任意符号。若有符号串v，w满足：v=γαδ，w=γβδ，则说v直接产生w，或者说，w是v的直接推导。记作vw。也可以说w直接归约到v。归约是推导的逆过程。编译原理与技术103.1文法和语言对例3.1文法G，可以给出直接推导的一些例子如下：①

23、v=0S1，w=0011，直接推导：0S10011，使用的规则：S→01，这里γ=0，δ=1。②v=S，w=0S1，直接推导：S0S1，使用的规则：S→0S1，这里γ=ε，δ=ε。③v=0S1，w=00S11，直接推导：0S100S11，使用的规则：S→0S1，这里γ=0，δ=1。编译原理与技术113.1文法和语言对例3.2文法G，直接推导的例子有：①v=〈标识符〉，w=〈标识符〉〈字母〉，直接推导：〈标识符〉〈标识符〉〈字母〉，使用的规则：〈标识符〉→〈标识符〉〈字母〉，这里γ=δ=ε。②v=

24、〈标识符〉〈字母〉〈数字〉，w=〈字母〉〈字母〉〈数字〉，直接推导：〈标识符〉〈字母〉〈数字〉〈字母〉〈字母〉〈数字〉，使用的规则：〈标识符〉→〈字母〉。这里γ=ε，δ=〈字母〉〈数字〉。③v=abc〈数字〉，w=abc5，直接推导：abc〈数字〉abc5,使用的规则：〈数字〉→5，这里γ=abc,δ=ε。编译原理与技术12定义3.3:如果存在直接推导的序列：v=w0w1w2…wn=w,(n＞0)，则称v推导出w，推导长度为n。或者称w归约到v。记作vw。若有vw，或v=w，则