资源描述：
《编译原理2章ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第二章高级语言及其语法描述引言：关于形式语言2.1程序语言的定义1、词法规则、语法规则p12-132、语义P142.2高级语言的一般特性P14-25(关于算符的优先顺序p23、名字的左值和右值p24）2.3程序语言的语法描述p252.3程序语言的语法描述一、符号和符号串字母表：字母表Σ是符号元素的非空集合。符号：字母表中的元素。符号串：字母表中的符号所组成的任何有穷序列。例如，若有字母表Σ={a,b}则a，b是字母表Σ中的元素(符号)；a，b，aa，ab，ba…都是符号串。注意：符号串中的符号与顺序有关，ab和ba是不同的符号串特别定义:
2、空符号串——不含任何符号的符号串，用ε表示。设有字母表Σ={a…z,A…Z,0…9,…,各种运算符和其它特殊符号，…}，则，由这些字母表中的元素(符号)可以组成不同的符号串：Programexample;Varsum,I:integer;BeginSum:=0;ForI:=1to10dosum:=sum+I;12345:=sum;End.Write(‘sum=’,sum);A={…}符号串的运算：符号串的连接（联结、乘积）：符号串x和y的连接是指x和y的符号按先后顺序排列在一起组成一个新的符号串，用xy表示。例，若字母表Σ={a,b}，符
3、号串x=ab，y=ba则xy=abba符号串的长度：符号串中符号的个数为符号串的长度。注意:(1)连接运算不满足交换律，即xy≠yx (2)任何符号串x与空串ε的连接都等于x，即：εx=xε=x。若ab是符号串，则
4、ab
5、表示符号串的长度。
6、ab
7、=2同理：
8、aabb
9、=4注意：特别规定
10、ε
11、=0。若有两个符号串x=ab,y=cde那么，
12、xy
13、=?5符号串的前缀与后缀(头和尾)：若有符号串z=xy(x,y是符号串),我们称x为z的前缀，y为z的后缀。例z=abcd则：z的头有，ε,a,ab,abc,abcd z的尾有，ε,d,cd,bc
14、d,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。即：符号串的幂运算服从结合律符号串集合的运算：符号串集合的乘积运算：设A、B为符号串集合（集合中各元素都是字母表上的字符串），两个字符串集合的乘积定义为：AB={xy
15、x∈A,y∈B}（笛卡儿乘积）设有字母表Σ={a,b,c,d}，令A={aa,bb}，B={cc,dd}则AB={aacc,aadd,bbc
16、c,bbdd}，BA={ccaa,ccbb,ddaa,ddbb}。显然AB≠BA，即符号串集合乘积不满足交换律。注意：因εx=xε=x故，{ε}A=A{ε}=A特别定义：空符号串集合：{ε}空集合：φ={}Aφ=φA=φ符号串集合的幂运算：设A为符号串集合，则集合的幂运算定义如下:A0={ε}A1=AA2=AA…An=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,b
17、b,aaa,…}A*={ε,a,b,aa,ab,ba,bb,aaa,…}显然：A*=A0∪A+A+=AA*二、上下文无关文法(p26)文法(Grammar):是描述语言的语法结构的形式规则（即语法规则）。Thebigmonkeyateabanana.规则：规则又叫产生式(productionrule)，它是语法单位结构的一种表示，它引入了符号“::=”或“→”表示“由……组成”，上述句子的结构可以表示如下：<句子>→<主语><谓语><主语>→<冠词><形容词><名词><冠词>→the<形容词>→big<谓语>→<动词><直接宾语><动词>
18、→ate<直接宾语>→<冠词><名词><冠词>→a<名词>→monkey<名词>→banana句子的推导：用规则(产生式)按一定方式去推导或产生句子的过程。<句子>→<主语><谓语><主语>→<冠词><形容词><名词><冠词>→the<形容词>→big<谓语>→<动词><直接宾语><动词>→ate<直接宾语>→<冠词><名词><冠词>→a<名词>→monkey<名词>→banana<句子><冠词><形容词><名词><谓语>The<形容词><名词><谓语>Thebig<名词><谓语>Thebigmonkey<谓语>Thebigmonkey<
19、动词><直接宾语>Thebigmonkeyate<直接宾语>Thebigmonkeyate<冠词><名词>Thebigmonkeyatea<名词>Thebigmonkeyateabanana<
