第三章-文法和语言ppt课件.pptx

知识结构3.1文法的直观概念程序设计语言的描述：
语法：程序的结构或形式
语义：语言所代表的含义
语用：语言的实际应用例如，对于赋值语句x:=a+b*c的非形式描述是：
语法：赋值语句＝变量＋:=＋表达式
语义：先求右部，然后把结果给左部变量
语用：赋值语句可用来计算和保存表达式的值
形式化方法：用一整套带有严格规定的符号体系来描述问
题的理论和方法
形式语言：一种不考虑含义的符号语言程序设计语言的语义分成：
静态语义：是一系列限定规则，并确定哪些合乎语法的程
序是合适的
动态语义（运行语义、执行语义）：表明程序要做什么，
要计算什么以自然语言为例，人们无法列出全部句子，但是人们可以
给出一些规则，用这些规则来说明（或者定义）句子的组
成结构：例如,有一组规则:
<句子>::=<主语><谓语>
<主语>::=<冠词><形容词><名词>
<冠词>::=the
<冠词>::=a
<形容词>::=big
<谓语>::=<动词><直接宾语>
<动词>::=ate
<直接宾语>::=<冠词><名词>
<名词>::=cat
<名词>::=mouse
显然,由这一组规则可以产生句子:
Thebigcat/mouseateamouse/cat这样的语言描述称为文法
使用文法作为工具，不仅为了严格地定义句子的结构，
也是为了适当条数的规则把语言的全部句子描述出来，
可以说文法是以有穷的集合刻画无穷的集合的一个工具3.2符号和符号串重要约定：
小写字母a,b,c,•••,r表示符号
小写字母s,t,u,•••,z表示符号串
大写字母A,B,C,•••,Z表示符号串集合二.符号串的运算
1.符号串相等：设x、y是字母表上的两个符号串，若x
与y的诸符号依次相等，则该两符号串相等，记为x=y2.符号串长度：设x是字母表上的符号串，符号串中包含
符号的个数称为符号串x的长度，用x表示
例:(1).||=0;(2).|ax|=|xa|=|x|+1(a∈∑)3.符号串的连结：设x与y是字母表上的两个符号串，
把y的所有符号相继写在x的符号之后所得到的符号串
称为x与y的连结，用xy表示
注意:
|xy|=|x|+|y|
x=x=x
xy≠yx(一般说来)4.符号串的逆：设x是字母表上的符号串，其逆为符号串x
的倒置，记为。5.符号串的前缀、后缀和子串：设x、y、z是字母表上的
符号串，则称x为符号串xy的前缀，y是符号串xy的
后缀，x、y、z、xy、yz是符号串xyz的子串
例:abcd6.符号串集合的乘积：设A、B为两个符号串集合，其乘积为
AB={xy|xA,yB}
例:(1).若A={ab,cd},B={ef,gh}
则:AB={abef,abgh,cdef,cdgh}
(2).∵x=x=x∴{}A=A{}=A7.空集：不含任何元素的集合，记为Ø
注意:(1).ØA=AØ=Ø;(2).Ø8.符号串的幂：设x是字母表上的符号串，则x的幂运算
为x0=x1=xx2=xx••••••xn=xn-1x(xxn-1)
例:若x=ab则:x0=,x1=ab,x2=abab,••••••,
xn=abab•••ab9.符号串集合的幂：设A是符号串集合，则符号串A的幂运
算为：A0={}A1=AA2=AA••••••An=An-1A(AAn-1)
例:若A={ab,cd}
则:A0={},A1={ab,cd},A2={abab,abcd,cdab,
cdcd},••••••注意:
A*=A0∪A+
A+=AA*=A*A
若A={a,b}
则:A*={,a,b,aa,ab,ba,bb,aaa,•••}
A+={a,b,aa,ab,ba,bb,aaa,•••}3.3文法和语言的形式定义定义3.1：文法G定义为四元组（VN，VT，P，S）
VN：非终结符（语法实体、变量）集
VT：终结符集
P：规则（αβ）集合，α∈(VN∪VT)*且至少包含
一个非终结符，β∈(VN∪VT)*
VN、VT、P是非空有穷集
S：开始符（识别符），它是一个非终结符，至少要在一
条规则中作为左部出现
VN∩VT=Ø
V=VN∪VT，称为文法G的字母表（字汇表）例3.1文法G=（VN，VT，P，S），其中
VN={S}，
VT={0,1}，
P={S0S1,S01}例3.2文法G=（VN，VT，P，S），其中
VN={标识符，字母，数字}
VT={a,b,c,…x,y,z,0,1,…,9}
P＝{<标识符><字母>
<标识符><标识符><字母>
<标识符><标识符><数字>
<字母>a
┇
<字母>z
<数字>0
┇
<数字>9}
S=<标识符>很多时候，不用将文法G的四元组显式地表示出来，而
只将产生式写出一般约定：
第一条产生式的左部是识