编译原理第三章.ppt

第3章文法和语言;语法

所谓一个语言的语法是指一组规那么，用它可以形成和产生一个适宜的程序。

目前广泛使用的是上下文无关文法，即用上下文无关文法作为程序设计语言语法的描述工具。

程序设计语言的描述

语法：程序的结构或形式

语义：语言所代表的含义

语用：语言的实际应用;例如，对于赋值语句x:=x+y*z的非形式描述为：

语法：赋值语句＝变量＋:=＋表达式

语义：先求右部，然后把结果给左部变量

语用：赋值语句可用来计算和保存表达式的值

形式化方法：是指用一整套带有严格规定的符号体系来描述问题的理论和方法。

形式语言：一种不考虑含义的符号语言。;;例如,有一组规那么:

句子::=主语谓语

主语::=冠词形容词名词

谓语::=动词直接宾语

直接宾语::=冠词名词

冠词::=the

冠词::=a

形容词::=small

动词::=ate

名词::=cat

名词::=mouse

显然,由这一组规那么可以产生句子:

Thesmallcat/mouseateamouse/cat;使用文法作为工具，不仅为了严格地定义句子的结构，也是为了适当条数的规那么把语言的全部句子描述出来，可以说文法是以有穷的集合刻画无穷的集合的一个工具。

有穷的〔规那么〕集合；

无穷的〔句子/程序〕集合;语言

可以看成在一个根本符号集上定义的，按一定规那么构成的一切根本符号串组成的集合。

字母表〔符号集Σ〕

是一个非空有穷集合。

符号〔字符〕

字母表中的元素。

符号串

符号的有穷序列。

注意：?表示空符号串，表示什么符号也不含的符号串。;符号串的前缀(头)、后缀(尾)、固有头、固有尾

设x、y、z是字母表?上的符号串，那么称x为符号串xy的前缀〔头〕，y是符号串xy的后缀〔尾〕；

?、x、xy、xyz是符号串xyz的前缀〔头〕，?、x、xy是符号串xyz的固有前缀〔头〕；

?、z、yz、xyz是符号串xyz的后缀〔尾〕，?、z、yz是符号串xyz的固有后缀〔尾〕。;符号串集合

字母表上假设干个符号串组成的集合。

空集：不含任何元素的集合，记为?。

注意:(1).?A=A?=?;(2).???

例：Σ={a,b,c,d,……z}。

a、b、c……都称为符号。

hello、stri、aezfg、main都是Σ上的符号串。

{hello、stri、aezfg}称为符号串集合。;符号串和符号串集合的运算;符号串的连结

设x与y是字母表∑上的两个符号串，把y的所有符号相继写在x的符号之后所得到的符号串称为x与y的连结，用xy表示。注意:

|xy|=|x|+|y|

x=?x=x?

xy≠yx(一般情况);符号串的逆

设x是字母表?上的符号串，其逆为符号串x的倒置，记为。

假设x=abcd,那么=dcba.

=??

符号串的方幂

设x是符号串，x自身的连接称为符号串的方幂，有:

例：x=ba,=ε,=ba,=bababa;符号串集合的乘积

假设A、B均为Σ上的符号串集合，那么：

AB={xy|x∈A,y∈B}

例：设A={ab,cd},B={ef,jh}，那么：

AB={abef,abjh,cdef,cdjh}

A{ε}=A，φA=Aφ=φ;符号串集合的幂

设A是符号串集合，那么符号串A的幂运算为：

A0={?}

A1=A

A2=AA

??????

An=An-1A=AAn-1)

例:假设A={ab,cd}，那么:

A0={?},A1={ab,cd},A2={abab,abcd,cdab,

cdcd},??????;符号串集合的正闭包

设符号串集合A，A的正闭包记为A+那么：

符号串集合的闭包

设符号串集合A，A的闭包记为A*,那么：

例：设Σ={0，1}，那么：

={0，1，00，01，10，11，000，001……}。

={ε,0,1,00,0