知识结构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=xxy≠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的四元组显式地表示出来，而只将产生式写出一般约定：第一条产生式的左部是识