文档介绍：复习:程序语言的语法描述
几个概念:
考虑一个有穷字母表∑字符集
其中每一个元素称为一个字符
∑上的字(也叫字符串) 是指由∑中的字符所构成的一个有穷序列
不包含任何字符的序列称为空字,记为ε
用∑*表示∑上的所有字的全体,包含空字ε
复习:程序语言的语法描述
∑*的子集U和V的连接(积)定义为
UV={ | U & V }
V自身的 n次积记为
Vn=VV…V
规定V0={},令
V*=V0∪V1∪V2∪V3∪…
称V*是V的闭包;
记 V+=VV* ,称V+是V的正规闭包。
复习:程序语言的语法描述
上下文无关文法的定义:
一个上下文无关文法G是一个四元式
G=(VT,VN,S,P),其中
VT:终结符集合(非空)
VN:非终结符集合(非空),且VT  VN=
S:文法的开始符号,SVN
P:产生式集合(有限),每个产生式形式为
P, PVN, (VT  VN)*
开始符S至少必须在某个产生式的左部出现一次。
复习:程序语言的语法描述
定义:称A直接推出,即
A
仅当A 是一个产生式,
且, (VT  VN)* 。
如果1 2 n,则我们称这个序列是从1到n的一个推导。若存在一个从1到n的推导,则称1可以推导出n 。
通常,用表示:从1出发,经过一步或若干步,可以推出n。
用表示:从1出发,经过0步或若干步,可以推出n。
所以: 即或
定义:假定G是一个文法,S 是它的开始符号。如果,则称是一个句型。仅含终结符号的句型是一个句子。文法G所产生的句子的全体是一个语言,将它记为 L(G)。
复习:程序语言的语法描述
最左推导:任何一步都是对中的最左非终结符进行替换。
最右推导:任何一步都是对中的最右非终结符进行替换。
复习:程序语言的语法描述
用一张图表示一个句型的推导,称为语法树。
E (E)
(E+E)
(E*E+E)
(i*E+E)
(i*i+E)
(i*i+i)
E (E)
(E+E)
(E+i)
(E*E+i)
(E*i+i)
(i*i+i)
复习:程序语言的语法描述
定义:如果一个文法存在某个句子对应两颗不同的语法树,则说这个文法是二义的。
语言的二义性:一个语言是二义性的,如果对它不存在无二义性的文法。
复习:程序语言的语法描述
形式语言鸟瞰
0型(短语文法,图灵机):
产生式形如: 
其中:(VT  VN)*且至少含有一个非终结符;(VT  VN)*
1型(上下文有关文法,线性界限自动机):
产生式形如: 
其中:|| ||,仅 S例外。
复习:程序语言的语法描述
形式语言鸟瞰
2型(上下文无关文法,非确定下推自动机):
产生式形如: A 
其中:A VN;(VT  VN)*。
3型(正规文法,有限自动机):
产生式形如: A B 或 A 
其中:  VT*;A,BVN
产生式形如: A  B或 A 
其中:  VT*;A,BVN