第3章__语法分析.ppt

第3章 语法分析 3.1 文法和语言 3.2 推导与语法树 3.3 自上而下分析方法 3.4 自下而上分析方法 3.5 LR分析法 3.1 文?法?和?语?言 文法是程序语言的生成系统，而自动机则是程序语言的识别系统；用文法可以精确地定义一个语言，并依据该文法构造出识别这个语言的自动机。因此，文法对程序语言和编译程序的构造具有重要意义，如程序语言的词法可用正规文法描述，语法可用上下文无关文法描述，而语义则要借助于上下文有关文法描述。 3.1.1 文法和语言的概念 1．语言 通常我们用Σ表示字母表，字母表中的每个元素称为字符或符号。不同语言的字母表可能是不同的，程序语言的字母表通常是ASCII字符集。由字母表Σ中的字符所组成的有穷系列称为Σ上的字符串或字，字母表Σ上的所有字符串(包括空串)组成的集合用Σ*表示。那么，对字母表Σ来说，Σ*上的任意一个子集都称为Σ上的一个语言，记为L(LΣ*)，该语言的每一个字符串称为语言L的一个语句或句子。 2．文法 文法通常表示成四元组G=(VT，VN，S，ξ)，其中： (1)VT为终结符号集，这是一个非空有限集，它的每个元素称为终结符号； (2)VN为非终结符集，它也是一个非空有限集，其每个元素称为非终结符号，且有VT∩VN=Φ； (3)S为一文法开始符，是一个特殊的非终结符号，即S∈VN； (4)ξ是产生式的非空有限集，其中每个产生式(或称规则)是一序偶(α，β)，通常写作 α→β或α::=β 读作“α是β”或“α定义为β”。在此，α为产生式的左部，而β为产生式的右部，α、β是由终结符和非终结符组成的符号串，α∈(VT∪VN)+且至少有一个非终结符，而β∈(VT∪VN)*。 终结符号是指语言不可再分的基本符号，通常是一个语言的字母表；终结符代表了语法的最小元素，是一种个体记号。非终结符号也称语法变量，它代表语法实体或语法范畴；非终结符代表一个一定的语法概念，因此，一个非终结符是一个类、一个集合。例如，在程序语言中，可以把变量、常数、“+”、“*”等看作是终结符，而像“算术表达式”这个非终结符则代表着一定算术式组成的类，如i*(i+i)、i+i+i等；也即每个非终结符代表着由一些终结符和非终结符且满足一定规则的符号串组成的集合。 文法开始符号是一个特殊的非终结符，它代表文法所定义的语言中我们最终感兴趣的语法实体，即语言的目标，而其它语法实体只是构造语言目标的中间变量；如表达式文法的语言目标是表达式，而程序语言的目标通常为程序。 产生式(也称产生规则或规则)是定义语法实体的一种书写规则。一个语法实体的相关规则可能不止一个。例如，有： P→α1 P→α2 P→αn 为书写方便，可将这些有相同左部的产生式合并为一个，即缩写成 P→α1∣α2∣…∣αn 其中，每个αi(i=1,2,…,n)称为P的一个候选式，直竖“∣”读为“或”，它与“→”一样是用来描述文法的元语言符号(即不属于Σ的字符)。 例3.1试构造产生标识符的文法。 [解答]首先，标识符是以字母开头的字母数字串，我们用L表示“字母”类非终结符，用D表示“数字”类非终结符，而用T表示“字母或数字”类非终结符，则有： L→a∣b∣…∣z D→0∣1∣…∣9 T→L∣D 其次，如果用S表示“字母数字串”类，则T是一字母或数字，ST也是字母数字串，即有 S→T∣ST 其中，产生式S→T∣ST是一种左递归形式，由它可以产生一串T。 最后，作为“标识符”的非终结符I，它或者是一单个字母，或者为一字母后跟字母数字串，即 I→L∣LS 因此，产生标识符的文法G[I]为： ? G=({a,b,…,z,0,…,9},{I,S,T,L,D},I,ξ) ξ:I→L∣LS S→T∣ST T→L∣D L→a∣b∣…∣z D→0∣1∣…∣9 例3.2写一文法，使其语言是奇数集合，但不允许出现以0打头的奇数。 [解答]根据题意，我们可以将奇数划分为如图3–1所示的三个部分，即最高位允许出现1～9，用非终结符B表示；中间部分可以出现任意多位数字0～9，每一位用非终结符D表示；最低位只允许出现1、3、5、7、9等奇数，用A表示。 由于中间部分可出现任意位，所以另引入了一个非终结符M，它包括最高位和中间位部分。假定开始符为N，则可得到文法G[N]为： G=({0,1,…,9},{N,A,M,B,D},N,ξ) ξ:N→A∣MA /*一位数字│多位数字*/ M→B∣MD /*仅两位数字(无中间位)│多于两位数字*/ A→1∣3∣5∣7∣9 B→1∣2∣3∣4∣5∣6∣7∣8∣9 D→0∣B 3．文法产生的语言 设文法G=(VT,VN,S,ξ)且α、β∈(VT∪VN)*，如果存在产生式A→δ