高级语言及其语法描述2

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

1、第二章高级语言及其语法描述2.1程序语言的定义引言：关于形式语言1、词法规则、语法规则P12-132、语义P142.2高级语言的一般特性P14-152.3程序语言的语法描述P252.3程序语言的语法描述一、符号和符号串字母表：字母表Σ是符号元素的非空集合。符号：字母表中的元素。符号串：字母表中的符号所组成的任何有穷序列。例如，若有字母表Σ={a,b}则a，b是字母表Σ中的元素(符号);a，b，aa，ab，ba…都是符号串。注意：符号串中的符号与顺序有关，ab和ba是不同的符号串特别定义:空符号串——不含任何符号的符号串，用ε表示。符号串的运算：符号串的连接（联结、乘积）：符号

2、串x和y的连接是指x和y的符号按先后顺序排列在一起组成一个新的符号串，用xy表示。例，若字母表Σ={a,b}，符号串x=ab，y=ba则xy=abba符号串的长度：符号串中符号的个数为符号串的长度。注意:(1)连接运算不满足交换律，即xy≠yx(2)任何符号串x与空串ε的连接都等于x，即：εx=xε=x。若ab是符号串，则

3、ab

4、表示符号串的长度。

5、ab

6、=2同理：

7、aabb

8、=4注意：特别规定

9、ε

10、=0。符号串的前缀与后缀(头和尾)：若有符号串z=xy(x,y是符号串),我们称x为z的前缀，y为z的后缀。例z=abcd则：z的头有，ε,a,ab,abc,abcdz的尾有，ε

11、,d,cd,bcd,abcd符号串的幂运算：设X是一个符号串，则：X0=ε，X1=X，X2=XX，…，Xn=X…X=Xn例：若有符号串x=ab，则：x0=ε,x1=ab,x2=abab,x3=ababab显然，若n>0,则Xn=XXn-1=Xn-1X。即：符号串的幂运算服从结合律若有两个符号串x=ab,y=cde那么，

12、xy

13、=?5符号串集合的运算：符号串集合的乘积运算：设A、B为符号串集合（集合中各元素都是字母表上的字符串），两个字符串集合的乘积定义为：AB={xy

14、x∈A,y∈B}（笛卡儿乘积）设有字母表Σ={a,b,c,d}，令A={aa,bb}，B={cc,dd}则A

15、B={aacc,aadd,bbcc,bbdd}，BA={ccaa,ccbb,ddaa,ddbb}。显然AB≠BA，即符号串集合乘积不满足交换律。注意：因εx=xε故，{ε}A=A{ε}=A特别定义：空符号集合：{ε}空集合：φ={}Aφ=φA=φ符号串集合的幂运算：设A为符号串集合，则集合的幂运算定义如下:A0={ε}A1=AA2=AA…A=AA……An个=AAn-1=An-1A符号串集合的闭包：设A为符号串集合，则集合的闭包定义如下:A的正闭包：A+=A1∪A2∪…A的闭包：A*=A0∪A1∪A2∪…设集合A={a,b}，则A+={a,b,aa,ab,ba,bb,aaa,…

16、}A*={ε,a,b,aa,ab,ba,bb,aaa,…}显然：A*=A0∪A+A+=AA*设有字母表Σ={a…z,0…9,type,var,const,if,then,else,for,to,do,case,begin,end,…,各种运算符和其它特殊符号，…}，则，由这些字母表中的元素(符号)可以组成不同的符号串：Programexample;Varsum,I:integer;BeginSum:=0;ForI:=1to10dosum:=sum+I;12345:=sum;End.Write(‘sum=’,sum);A={…}二、上下文无关文法(p26)文法(Grammar)

17、:是描述语言的语法结构的形式规则（即语法规则）。Thebigelephantatethepeanut.语法树(ParseTree):句子结构的图形表示方式<句子><主语><谓语><名词><形容词><冠词><直接宾语><动词><名词><冠词>elephantbigTheatepeanutthe规则：规则又叫产生式(productionrule)，它是句子结构的另一种表示结构，它引入了符号“::=”或“→”表示“由……组成”，上述句子的结构可以表示如下：<句子>→<主语><谓语><主语>→<冠词><形容词><名词><冠词>→the<形容词>→big<谓词>→<动词><直接宾语><

18、动词>→ate<直接宾语>→<冠词><名词><名词>→elephant<名词>→peanut句子的推导：用规则(产生式)按一定方式去推导或产生句子的过程。<句子><冠词><形容词><名词><谓语>The<形容词><名词><谓语>Thebig<名词><谓语>Thebigelephant<谓语>Thebigelephant<动词><直接宾语>Thebigelephantate<直接宾语>Thebigelephantate<冠词><名词>Thebigelephantatethe<名词>Thebigelepha