文档介绍：第3章语法分析
文法和语言
推导与语法树
自顶向下的语法分析
自底向上的语法分析
规范规约的自底向上语法分析方法<br****题三
语法分析的基本任务:根据语言的语法规则进行语法分析,若不存在语法错误则给出正确的语法结构并为语义分析和代码生成做准备。
描述语言的语法结构需借助上下文无关文法。
语法分析的方法
自上而下分析法
自下而上分析法
文法和语言
文法和语言的概念
形式语言分类
正规表达式与上下文无关文法
文法和语言的概念
语言
文法
文法产生的语言
通常我们用Σ表示字母表,字母表中的每个元素称为字符或符号。不同语言的字母表可能是不同的,程序语言的字母表通常是ASCII字符集。由字母表Σ中的字符所组成的有穷系列称为Σ上的字符串或字,字母表Σ上的所有字符串(包括空串)组成的集合用Σ*表示。那么,对字母表Σ来说,Σ*上的任意一个子集都称为Σ上的一个语言,记为L(LΣ*),该语言的每一个字符串称为语言L的一个语句或句子。
例如,设Σ={a,b,c},则L={ε,a,aa,ab,aaa,aab,aba,abb,…}为Σ上的一个语言。如果a表示字母、b表示数字、c看作其它符号,则L即是程序语言中的标识符集,其中的每个标识符就是标识符集中的一个句子。
文法通常表示成四元组G[S]=(VT,VN,S,ξ),其中:
(1) VT为终结符号集,这是一个非空有限集,它的每个元素称为终结符号;
(2) VN为非终结符集,它也是一个非空有限集,其每个元素称为非终结符号,且有VT∩VN=Φ;
(3) S为一文法开始符,是一个特殊的非终结符号,即S∈VN;
(4) ξ是产生式的非空有限集,其中每个产生式(或称规则)是一序偶(α,β),通常写作
α→β或α::=β
读作“α是β”或“α定义为β”。在此,α为产生式的左部,而β为产生式的右部,α、β是由终结符和非终结符组成的符号串,α∈(VT∪VN)+且至少有一个非终结符,而β∈(VT∪VN)*。
产生式需要满足下面的条件:
1)α可以是VN 和VT 上的任意字符串,但其中必须至少包含一个非终结符,并且不能是空字符串(空字);
2)β可以是VN 和VT 上的任意字符串,也可以是空字;
3)ξ中至少有一个产生式中的α得由S 来充当;
终结符号是指语言不可再分的基本符号,通常是一个语言的字母表;终结符代表了语法的最小元素,是一种个体记号。非终结符号也称语法变量,它代表语法实体或语法范畴;非终结符代表一个一定的语法概念,因此,一个非终结符是一个类、一个集合。例如,在程序语言中,可以把变量、常数、“+”、“*”等看作是终结符,而像“算术表达式”这个非终结符则代表着一定算术式组成的类,如i*(i+i)、i+i+i等;也即每个非终结符代表着由一些终结符和非终结符且满足一定规则的符号串组成的集合。
文法开始符号是一个特殊的非终结符,它代表文法所定义的语言中我们最终感兴趣的语法实体,即语言的目标,而其它语法实体只是构造语言目标的中间变量。如表达式文法的语言目标是表达式,而程序语言的目标通常为程序。
产生式(也称产生规则或规则)是定义语法实体的一种书写规则。一个语法实体的相关规则可能不止一个。例如,有:
P→α1
P→α2
P→αn
为书写方便,可将这些有相同左部的产生式合并为一个,即缩写成
P→α1∣α2∣…∣αn
其中,每个αi (i=1,2,…,n) 称为P的一个候选式,直竖“∣”读为“或”,它与“→”一样是用来描述文法的元语言符号(即不属于Σ的字符)。
试构造产生标识符的文法。
[解答] 首先,标识符是以字母开头的字母数字串,我们用L表示“字母”类非终结符,用D表示“数字”类非终结符,而用T表示“字母或数字”类非终结符,则有:
L→a∣b∣…∣z
D→0∣1∣…∣9
T→L∣D
其次,如果用S表示“字母数字串”类,则T是一字母或数字,ST也是字母数字串,即有
S→T∣ST
其中,产生式S→T∣ST是一种左递归形式,由它可以产生一串T。