编译原理语法分析(1).doc

第3章语法分析
语法分析是编译过程的核心部分。语法分析的基本任务是在词法分析识别出单词符号串的基础上，分析判断程序的语法结构是否符合语法规则。语言的语法结构用上下文无关文法来描述，因此，语法分析器的任务本质上是按上下文无关文法的产生式，确定整个单词串是否构成语法上正确的程序。语法分析的方法通常分为两类：自上而下分析法和自下而上分析法

3.1文法和语言

3.2推导与语法树
3.3自上而下分析方法

3.4自下而上分析方法
3.5LR分析法

3.1文法和语言
文法是程序语言的生成系统。自动机是程序语言的识别系统。用文法可精确定义一个语言,并依据文法构造出识别该语言的自动机。因此,文法对程序语言和编译程序的构造具有重要意义,如程序语言的词法可用正规文法描述,语法可用上下文无关文法描述,而语义可借助于上下文有关文法描述。

3.1.1文法和语言的概念1．语言通常用Σ表示字母表。由字母表Σ中字符组成的有穷序列称为Σ上的字符串或字。字母表Σ上的所有字符串(包括空串)组成的集合用Σ*表示。对于字母表Σ,Σ*上的任一子集称为Σ上的一个语言,记为L,L?Σ*。语言L的每个字符串称为语言L的一个语句或句子。

2.文法终结符是语言不可再分的基本符号,通常为一个语言的字母表。终结符代表了语法的最小元素,是一种个体记号。非终结符也称语法变量,它代表语法实体或语法范畴。一个非终结符是一个类、一个集合。例如,变量、常量、+、*等为终结符，而“算术表达式”为非终结符,它代表一定算术式组成的类,如i*(i+i)、i+i+i等,即非终结符代表由终结符组成且满足一定规则的符号串的集合。

文法可表示为四元组G=(VT,VN,S,ξ),其中(1)VT为非空终结符集;(2)VN为非空非终结符集,且VT∩VN=Φ;(3)S为文法开始符,S∈VN;(4)ξ是产生式的非空有限集,其中每个产生式(规则)记作?→?或?::=?左部?∈(VT∪VN)+至少含一非终结符,右部?∈(VT∪VN)*。

产生式(也称产生式规则或规则)是定义语法实体的一种书写规则。一个语法实体的相关规则可能不止一个,如: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???9T→L?D
用S表示字母数字串,则ST是字母数字串,即

S→T|ST标识符I或为单个字母,或为一字母后跟字母数字串,即I→L?LS

解:产生标识符的文法G[I]为：G=({a,b,?,z,0,?,9},{I,S,T,L,D},I,ξ)其中,ξ:I→L?LSS→T?STT→L?DL→a?b???zD→0?1???9

例3.2写一文法,使其语言是奇数集,但不允许出现以0打头的奇数。解:将奇数划分为三个部分：最高位允许出现1～9,用非终结符B表示;中间部分可出现任意多位数字0～9,每一位用非终结符D表示;最低位只出现1,3,5,7,9,用A表示。由于中间部分可任意位,故需另引入一非终结符M,它包括最高位和中间部分。

MBDD

…

D

A

中间位
最高位最低位

解:奇数集文法G[N]为:G=({0,1,?,9},{N,A,M,B,D},N,ξ)ξ:N→A|MAM→B|MDA→1|3|5|7|9B→1|2|3|4|5|6|7|8|9D→0|B

3.文法产生的语言设G=(VT,VN,S,ξ)且?,?∈(VT∪VN)*,若存在产生式A→δ,δ∈(VT∪VN)*，则称?A?可直接推出?δ?,记为?A???δ?注意?与→的不同:→是产生式中的定义记号,?表示直接推导,是对文法符号串?A?中A用产生式A→δ的右部δ替换。

关于推导的两点说明：(1)若?1可直接推出?2,?2可直接推出?3,…,即存在一个自?1至?n的推导序列:?1??2??3?…??n(n>0)+?,则称?1可推导出?n,记为?1?n表示从?1出发经1步或若干步可推导出?n
0*(2)若记?1??1,则?1??n表示从?1出发,经过

0步或若干步可推导出?n,
+*即?1??n意味着或?1=?n,或?1??n。

例如,考虑算术表达式文法G[E]：E→E+E?E*E?(E)│i非终结符E代表一类算术表达式,从E出发可进行一系列推导,表达式i+i*i的推导如下：E?E+E?E+E*E?E+E*i?E+i*i?i+i*I注意:在每一步推导中,只能对其中一个非终结符用其对应的产生式右部的一个候选式来替换。

假定G[S]是一个文法,S是其开始符号,*若S??,?∈(VT∪VN)*,则称?是文法G[S]的一个句型;*若S??,?∈VT*，则称?是文法G[S