1、 语法分析是编译过程的核心部分。 语法分析的基本任务是在词法分析识别出单词符号串的基础上，分析判断程序的语法结构是否符合语法规则。 语言的语法结构用上下文无关文法来描述，因此，语法分析器的任务本质上是按上下文无关文法的产生式，确定整个单词串是否构成语法上正确的程序。 语法分析的方法通常分为两类： 自上而下分析法和自下而上分析法3.1 文法和语言 3.2 推导与语法树 3.3 自上而下分析方法 3.4 自下而上分析方法 3.5 LR分析法 3.1 文法和语言文法和语言 文法文法是程序语言的生成系统。 自动机自动机是程序语言的识别系统。 用文法可精确定义一个语言,并依据文法构造出识别该语言的自动机
2、。因此,文法对程序语言和编译程序的构造具有重要意义,如程序语言的词法可用正规文正规文法法描述,语法可用上下文无关文法上下文无关文法描述,而语义可借助于上下文有关文法上下文有关文法描述。3.1.1 文法和语言的概念 1语言语言 通常用表示字母表。 由字母表中字符组成的有穷序列称为上的字符串字符串或字字。字母表上的所有字符串(包括空串)组成的集合用*表示。 对于字母表, *上的任一子集子集称为上的一个语言语言, 记为L, L*。语言L的每个字符串称为语言L的一个语句语句或句子句子。2. 文法文法 终结符终结符是语言不可再分的基本符号,通常为一个语言的字母表。终结符代表了语法的最小元素,是一种个体记
3、号。 非终结符非终结符也称语法变量, 它代表语法实体或语法范畴。一个非终结符是一个类、一个集合。 例如, 变量、常量、+、* 等为终结符终结符，而 “算术表达式”为非终结符非终结符, 它代表一定算术式组成的类类,如i*(i+i)、i+i+i等,即非非终结符终结符代表由终结符组成且满足一定规则的符号串的集合集合。 文法文法可表示为四元组G=(VT,VN,S,), 其中 (1) VT为非空终结符集终结符集; (2) VN为非空非终结符集非终结符集,且VTVN=; (3) S为文法开始符文法开始符, SVN; (4)是产生式的非空有限集产生式的非空有限集, 其中每个 产生式(规则)记作 或 := 左
4、部(VTVN)+至少含一非终结符, 右部(VTVN)*。 产生式 (也称产生式规则或规则) 是定义语法实体的一种书写规则。一个语法实体的相关规则可能不止一个, 如: P1, P2 , Pn 相同左部的产生式可合并为一个: P 1| 2| n 其中, i(i=1,2,n)称为P的候选式候选式。例例3.1 试构造产生试构造产生标识符标识符的文法的文法。分析: 用L表示字母,D表示数字,T表示字母或数字, 则 La b z D0 1 9 TL D 用S表示字母数字串字母数字串,则ST是字母数字串,即 ST | ST 标识符I或为单个字母, 或为一字母后 跟字母数字串, 即 IL LS解: 产生标识符
5、的文法产生标识符的文法GI为： G=(a,b,z,0,9,I,S,T,L,D,I,) 其中,: IL LS ST ST TL D La b z D0 1 9例例3.2 写一文法, 使其语言是奇数集, 但不允 许出现以0打头的奇数。解: 将奇数划分为三个部分： 最高位最高位允许出现19,用非终结符B表示; 中间部分中间部分可出现任意多位数字09, 每一位用非终结符D表示; 最低位最低位只出现1,3,5,7,9, 用A表示。 由于中间部分可任意位,故需另引入一 非终结符M,它包括最高位和中间部分。MB最高位中间位DDDA最低位解: 奇数集文法GN为: G=(0,1,9,N,A,M,B,D,N,)
6、: NA | MA MB | MD A1 | 3 | 5 | 7 | 9 B1|2|3|4|5|6|7|8|9 D0 | B3. 文法产生的语言文法产生的语言 设G=(VT,VN,S,)且, (VTVN)*, 若存在产生式A, (VTVN)*， 则称A可直接推出可直接推出, 记为 A 注意与的不同: 是产生式中的定义记号, 表示直接推导,是对文法符号串A 中A用产生式A的右部替换。关于推导的两点说明关于推导的两点说明：(1)若1可直接推出2, 2可直接推出3, 即存在一个自1至n的推导序列: 12 3 n (n0) 则称1可推导出可推导出n,记为1 n, 表示从1出发经1步或若干步可推导出n(
7、2)若记1 1, 则1 n表示从1出发,经过 0步或若干步可推导出n, 即1 n意味着或1=n, 或1 n。+0*+例如,考虑算术表达式文法GE： EE+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注意: 在每一步推 导中,只能对其中一个 非终结符用其对应的产生式右部的 一个候选式来替换。假定GS是一个文法, S是其开始符号,若S , (VTVN)*,则称是文法GS的一个句型句型 ;若S , VT*，则称是文法GS的一个句子句子。由上述定义知： 仅含终结符的句型是一
8、个句子。 开始符S是一个句型而不是一个句子。 i+i*i是一个句子, 也是一个句型, E+E*E、E+E*i和E+i*i是句型, 但不是一个句子。* 对于文法GS, 它所产生的句子的全句子的全体体称为由文法GS产生的语言语言,记为LG。 L(G)= | S 且VT*3.1.2 形式语言分类形式语言分类 Chomsky于1956年定义了四类文法及相应的四类形式语言形式语言, 它对程序语言的设计、编译方法、计算复杂性等方面都产生了重大影响。+1 0型文法与型文法与0型语言型语言 (短语文法) 若文法G的每个产生式具有下列形式: 其中至少含一个非终结符， 则称文法G为0型文法型文法或或短语文法短语文
9、法, 记为PSG。 0型文法相应的语言称为0型语言型语言, 它的识别系统是图灵机。21型文法与型文法与1型语言型语言 (对应自然语言) 若文法G的每个产生式均满足 | | 则称文法G为1型文法型文法或上下文有关文上下文有关文 法法, 记为CSG。 1型文法相应的语言称为1型语言型语言。 1型文法的另一种定义型文法的另一种定义: 文法G的每个产生式具有下列形式： A 其中, ,V*, AVN, V+ 它更明确地表达了上下文有关的特性。3 2型文法与型文法与2型语言型语言 (对应程序设计语言) 若文法G的每个产生式具有下列形式： A 其中, AVN, V* 称文法G为2型文法型文法或上下文无关文法
10、上下文无关文法, 记为CFG。 2型文法相应的语言称为2型语言型语言或 上下文无关语言。 它的识别系统是下推自动机。4 3型文法与型文法与3型语言型语言 (对应有限自动机) 若文法G的每个产生式具有下列形式： Aa 或 AaB 其中，A,BVN，aVT*， 则文法G称为3型文法型文法或正规文法正规文法或右线 性文法，记为RG。 3型文法相应语言为3型语言型语言或正规语言。 它的识别系统是有限自动机。 3型文法还可呈左线性形式： Aa 或 ABa5. 四类文法的关系与区别四类文法的关系与区别 从0型文法到3型文法逐步增加限制。 一般地,13型文法属于0型文法，2,3型文法属于1型文法,3型文法属
11、于2型文法。四类文法的区别四类文法的区别：(1)1型文法不允许有形如A的产生式, 2,3型文法允许形如A的产生式;(2)0,1型文法的产生式左部左部可以是含终结 符的符号串或两个以上的非终结符, 2,3型文法的产生式左部只允许是单个单个 非终结符非终结符。 anbncn|n1anbncm|m,n1 ambnck|m,n,k1 这说明对文法规则定义形式的限制虽加强了, 但相应的语言反而更大了。因此,不能主观认定文法限制越大则语言越小, 即下述结论不成立不成立： 3型语言 2型语言 1型语言 0型语言 编译方法中通常用3型文法型文法描述词法词法,用FA识别单词; 利用2型文法型文法描述语法语法,用
12、下推自动机PDA识别各种语法成分。例例3.4 给出=a,b上具有奇数个具有奇数个a和奇数和奇数 个个b的所有字符串集合的正规文法正规文法。解: 如图, 由S出发经奇数个a到达A, 或经奇数个b到达B。再由A出发经奇数个b到达C; 同样, 由B出发经奇数个a到达C。正规文法GS如下: SaA | bB AaS | bC BbS | aC CbA | aB| bbbbaaaaSAB2 C3.1.3 正规式与上下文无关文法正规式与上下文无关文法1. 正规式到上下文无关文法的转换正规式到上下文无关文法的转换 由正规式构造由正规式构造CFG的一种方法的一种方法： (1)构造正规式的NFA； (2)若0为
13、初始状态, 则A0为开始符； (3)若存在映射关系f(i,a)=j, 则定义产生式Ai aAj； (4)若存在映射关系f(i,)=j， 则定义产生式Ai Aj； (5) 若i为终态终态, 则定义产生式Ai 。例例3.5 用CFG描述正规式(a|b)*abb解: 先构造识别(a|b)*abb的NFA M:0122 3ababbGA0: A0aA0 bA0 aA1 A1bA2 A2bA3 A3由正规式构造由正规式构造CFG的另一种方法的另一种方法： 通过分析正规式凭经验凭经验直接构造。例如, 把(a|b)*abb看作(a|b)*和abb两部分,第一部分是由0个或若干个a和b组成的字符串,第二部分仅
14、由abb字符串组成,由此得到CFG GA0如下： GA0: AHT HaH|bH| Tabb2. 正规式与正规式与CFG描述的对象描述的对象 CFG既可描述语法,又可描述词法。 基于下述原因,通常用正规式描述词法: (1)词法规则简单,用正规式已足以描述; (2)正规式的表示比CFG更简洁、直观 和易于理解； (3) FA的构造比PDA(下推自动机)的构 造简单且效率高。 注意注意: (1)语言的描述描述和语言的识别识别是表示一种语言的两个不同侧面, 二者缺一不可。 (2)正规式正规式通常适合于描述线性结构线性结构, 如标识符、关键字和注释等; 上下文无关上下文无关文法文法通常适合于描述具有嵌
15、套(层次)性质的非线性结构非线性结构, 如 if-else语句、while语句。3.2.1 推导与短语1. 规范推导规范推导 最右推导最右推导: 在推导过程中,若每一步推导都是对句型中的最右非终结符最右非终结符用相应产生式的右部进行替换, 则称这种推导为最右推导。 最左推导最左推导: 在推导过程中,若每一步推导都是对句型中的最左非终结符最左非终结符用相应产生式的右部进行替换, 则称这种推导为最左推导。例如例如, 考虑句子 i+i*i 按文法GE的推导 最左推导最左推导: EE+Ei+Ei+E*E i+i*E i+i*i 最右推导最右推导: EE+EE+E*EE+E*i E+i*ii+i*i注意
16、注意: 推导过程不唯一, 通常只考虑最左 推导或最右推导。 最右推导最右推导又称为规范推导规范推导。 规范推导的逆过程称为规范归约规范归约。2. 短语短语 如果S A且A , 则称 是句型句型关于非终结符A的一 个短语短语,简称是的一个短语短语。 如果S A且A , 则称为句型的一个直接短语直接短语或 简单短语。注意注意: 短语的两个条件缺一不可。 考虑i+i*i, E i+i, 但i+i不是短语 *+*+3. 句柄句柄 句型的最左直接短语最左直接短语称为句柄句柄。 注意, 一个句型的直接短语不唯一, 但最左直接短语唯一。 例如, 对S A , 若为终结符串, 则句型中的句柄为。 将句型中的句
17、柄用产生式的左部 符号代替便得到新句型A, 这是一次 规范归约, 恰与规范推导相反。* 4. 素短语素短语 含有终结符的短语,如果它不存在具有 同样性质的真子串,则该短语为素短语素短语。 例如,在E E+E*i中, i、E*i、E+E*i是句型E+E*i的短语, 其中, i为素短语素短语, E*i虽含终结符, 但其 真子串i含终结符, 故E*i不是素短语不是素短语, 同样E+E*i也不是素短语。+3.2.2 语法树与二义性语法树与二义性1. 语法树语法树 对于程序语言, 有两个问题需要解决: (1)判别程序在语法上是否正确; (2)句子的识别或分析。 为便于分析句子而引入语法树语法树。 语法树
18、语法树以图示化形式把句子分解成各 个组成部分,以分析句子的语法结构。 语法树表示法与文法规则完全一致,但 更为直观和完整。满足下列条件的树称为文法满足下列条件的树称为文法G的的语法树语法树:(1)每个结点用G的一个终结符或非终结 符标记;(2)根结点用文法开始符S标记;(3)内部结点一定是非终结符,若某内部结 点A有n个分支, 且其所有子结点从左 至右依次标记为x1, x2, ,xn,则 Ax1x2xn一定是G的一条产生式;(4)若某结点标记为,则它必为叶结点且 是其父结点的唯一子结点。 一个句型句型对应的语法树语法树以文法开始符S作为根结点,并随着推导逐步展开。当某非终结符被产生式右部的某候
19、选式替换时,该非终结符对应的结点产生出下一代结点,即候选式中从左至右的每个符号依次顺序对应一个新结点,且每个新结点与其父结点之间都有一连线。在一棵语法在一棵语法树生长过程中的任何时刻树生长过程中的任何时刻,所有没有后代所有没有后代的叶结点的叶结点的自左至右排列是一个的自左至右排列是一个句型句型。 例如,句子i+i*i的语法树如下:EEEE*Eiii第一代第二代第三代第四代 构造语法树时, 一个句型的最左推导及最右推导只决定先先生长左子树还是先先生长右子树, 推导结束时相应的语法树已看不出先生长的是哪个子树。 因此, 一棵语法树表示一个句型种种可能的不同推导过程, 包括最左(最右)推导。若坚持使
20、用最左坚持使用最左(最右最右)推导推导, 则一棵则一棵语法树等价于一个最左语法树等价于一个最左(最右最右)推导推导, 这种等价性包括语法树的每一步生长和推导过程的每一步展开的完全一致性。2. 子树和短语子树和短语 语法树的某个结点连同它的所有后代组 成了一棵子树子树。 只含有单层分枝的子树称为简单子树简单子树。 子树与短语的关系子树与短语的关系: (1)短语短语: 子树的所有叶结点所有叶结点组成的符号 串是相对于子树根子树根的短语短语； (2)直接短语直接短语: 简单子树的所有叶结点简单子树的所有叶结点组 成的符号串是直接短语直接短语; (3)句柄句柄: 最左简单子树最左简单子树的所有叶结点组
21、 成的符号串为句柄句柄; (4)素短语素短语: 子树的所有叶结点组成的 含终结符含终结符的符号串, 且在该子树中 没有没有有包含终结符的更小子树更小子树。 显然, 从语法树出发寻找短语、直接短语、句柄和素短语直观得多。但要注意, 子树叶结点组成的符号串子树叶结点组成的符号串是指由该子子树根树根开始向下生长的所有叶结点所有叶结点,该子树的部分叶结点并不是该子树的短语。考虑句型E+E*i的语法树:短语: i、E*i和E+E*i; 直接短语: i; 句柄: i; 素短语: iEEEE*Ei3. 文法的二义性文法的二义性 若文法G的一个句子能找到两种不同的最左推导(最右推导), 即存在两棵不同的语法树
22、, 则称这个句子句子是二义性是二义性的。 若一个文法包含二义性句子, 则这个文法是二义文法二义文法, 否则是无二义文法。 例如, 对文法(3.1),句子i+i*i存在两种最左(右)推导:EEEE*EiEEEE*Eiii(a)ii(b)再如,条件语句文法GS: GS: Sif B S Sif B S else S SA /A指其它语句 其中, VN =B,S,A, VT =if, else 文法GS的一个句型if B if B S else S对应两棵不同的语法树, 如下图所示, 因此,文法GS是二义性文法。SifS(a)(b)BSifS elseBSBSifS elseifSB4. 文法二义性
23、的消除文法二义性的消除 一个文法是二义性的, 并不说明文法所描述的语言是二义性的。即对于一个二义文法GS, 若能找到一个非二义文法GS, 使得L(G)=L(G), 则该二义文法的二义性可以消除。若找不到这样的GS,则二义文法描述的语言为先天二义性的。文法二义性的消除方法:(1)不改变文法中原有的语法规则, 仅加进 一些语法的非形式规定。 如对文法(3.1), 不改变已有产生式, 仅加 进运算符的优先顺序优先顺序和结合规则结合规则, 即 *优先于+, 且*,+都服从左结合。(2)构造一个等价的无二义文法。即把排除 二义性的规则合并到原文法中, 改写原改写原 文法文法。GE: EE+T T TT*
24、F F F(E) i此时,句子i+i*i只有唯一 一棵语法树。 例如, 将文法(3.1)改写为无二义文法GE:EETFTFiiTFi*例例3.6 将下述文法GS的二义性消除: GS: Sif b S if b S else S A解: 消除GS的二义性可采用两种方法:(1)不改变已有规则不改变已有规则, 仅加 进一项非形式的语法规 定: else与离它最近的if 匹配, 这样, 句子if b if b A else A对应唯一的一 棵语法树。SbSifS elseAAbifS(2)改写文法GS为GS: SS1| S2 S1if b S1 else S1|A S2if b S|if b S1el
25、se S2 由于引起二义性的原因是if-else语句的if后后可以是任意if语句, 故改写文法改写文法时规定时规定if和和else之间只能是之间只能是if-else语句或其它语句语句或其它语句。S1bS1ifS1elseAAbifSS2S 编译过程中希望一个文法是无二义性的, 这样句子的分析可按唯一确定的方式进行。但文法的二义性是不可判定的, 即不存在一种算法能在有限步内判定一个文法是否为二义性的。不过, 二义文法有时也可带来一定好处, 如语法分析中二义文法的应用。 自上而下分析自上而下分析从文法开始符出发, 向下推导, 推出句子。即寻找一个推导序列, 使推导出的句子恰为输入串; 亦即,从根结
26、点出发向下生长出一棵语法树,其叶结点组成的句子恰为输入串。 显然, 语法树的每一步生长(推导)都以能否与输入串匹配为准。1. 自上而下分析存在的不确定性 文法GS: SxAy Aab a 若输入串为xay, 则其分析过程如下: (1)首先建立根结点S。 (2)文法关于S的产生式只有一个。yAxS 下一待分析字符a与A匹配。 (3)非终结符A有两个候选式, 先选用第一个候选式:yAxSab (4)下一待分析字符y与b匹配, 失败。 (5)将A生成的子树注销, 指针回退到输 入串的第二个字符a。 (6) A选用第二个候选式:yAxSa 这时输入串中a与叶结点a匹配。 (7) 下一个待分析字符为y,
27、 而语法树下 一个叶结点也为y, 匹配成功。 在上述分析过程中, 若有多个候选式可供选择, 则逐一试探试探每个候选式。一次试探失败时, 必须回溯回溯到该试探的初始现场, 包括注销已生长子树、指针回退到失败前状态。这种带回溯的自上而下分析方法是一种穷举法, 效率极低效率极低, 在实用编译程序中很少使用。2. 确定的自上而下分析确定的自上而下分析 实现确定的自上而下分析需满足条件: (1)文法不含左递归文法不含左递归。 左递归: AA 或 A A 左递归的存在可能可能使自上而下分析过程陷入无限循环, 故使用自上而下分析法必须消除文法的左递归必须消除文法的左递归。 (2)分析过程无回溯分析过程无回溯
28、。 回溯的存在可能使已做的大量语法和语义分析推倒重来, 这会严重影响效率, 故使用自上而下分析法必须消除回溯必须消除回溯。+ 3. 左递归的消除左递归的消除直接左递归直接左递归的消除 方法: 引入一个新的非终结符,把含有 左递归的产生式改写为右递归形式。 例如: AA | , 是任意串且不以A开头。 A的产生式可改写为: A A A A| 例如, 算术表达式文法GE为: GE: EE+T | T TT*F | F F(E) | i消去直接左递归后得到文法GE: GE: ETE E+TE | TFT T*FT | F(E) | i一般地, 设文法中A的产生式为: AA 1|A 2|A m| 1|
29、 2| n 其中,每个都不等于 每个都不以A开头消除A的直接左递归, 文法可改写为: A 1A | 2A | nA A 1A | 2A | mA | 例如, 试消除EE+T|ET|T的左递归。解: 消除左递归后变为 ETE E+TE | TE | 间接左递归的消除间接左递归的消除 例如, 文法GS: SQc | c QRb | b RSa | a 如何消除文法的间接左递归？ 间接左递归的存在是由于非终结符之间形成了循环推导, 只要把循环推导中的某个连接切断, 间接左递归就消除了。切断循环推导中的某个连接的方法：Step1. 对n个个产生式中的某一个进行至多至多 n-1次次替换, 使间接左递归变
30、成直 接左递归, 再消除之。例如, 消除上述文法GS中S,Q间的连接间的连接: S Qc|c Rbc|bc|c Sabc|abc|bc|c 改写为: SabcS|bcS|cS SabcS| 消除左递归还需消除Q,R间的连接间的连接: Q Rb|b Sab|ab|Qab|b 再消除其直接左递归Step2. 对其余其余n-1个个产生式中的某一个进行 至多至多n-2次次替换,再消除直接左递归。 考虑上述文法的后两个产生式: QRb | b RSa | a | Qa消除左递归算法消除左递归算法:(1)文法的所有非终结符排序为A1,A2,An;(2)将间接左递归改为直接左递归,消除之; for (i=1
31、; i=n; i+) for (j=1; j=i1; j+) 把AiAj| 及Aj1|k 改写为Ai1|k| ; 消除Ai的直接左递归; (3)化简, 删去那些不可达元的产生式。通过例子熟悉消除左递归算法消除左递归算法执行过程:例如, GS: SQc | c QRb | b RSa | a(1) 将非终结符排序为R, Q, S;(2) 对于对于R (i=1, P1) 内层循环不执行; 消除R的直接左递归: RSa|a 对于对于Q (i=2, P2) 内层循环改写P2 P1: QSab|ab|b 消除Q的直接左递归: QSab|ab|b 对于对于S (i=3, P3) 内层循环改写P3P1和P3
32、P2: SSabc | abc | bc | c 消除S的直接左递归: SabcS | bcS | cS SabcS | 于是得文法GS: SabcS | bcS | cS SabcS | QSab | ab | b RSa | a(3) 化简, 删去关于Q和R的产生式。对消除左递归算法的两点说明: (1)消除左递归算法有两个限制条件:文法中不含回路不含回路(P P)和-生成式生成式。该限制不会影响消除左递归算法的使用,因为后续课程形式语言中将学到,对任一CFG G, 存在一个不含不含-生成式生成式和单一生成式单一生成式的CFG G, 使得L(G)=L(G)-。 (2) 对非终结符的不同排序会
33、导致文法形式上的不同, 但可证明它们等价。上例若排序为S,Q,R, 则得文法GS: SQc | c QRb | b RbcaR |caR |aR RbcaR | GS与GS等价的证明: 证明: Sabc(abc)*|bc(abc)*|c(abc)* L(G)=(abc|bc|c)(abc)i | i0 Sbca(bca)*bc|ca(bca)*bc| a(bca)*bc|bc|c L(G)=(abc|bc|c)(abc)i | i0 有兴趣的同学课后以下述文法为例熟悉消除左递归算法的执行过程: GS: SQc | c | Rc QRb | b | Sb RSa | a | Qa GS: SQc
34、 | c | Rc | Sc QRb | b | Sb | Qb RSa | a | Qa | Ra 2. 回溯的消除回溯的消除 要消除回溯,首先要清楚回溯存在的原因, 根除这些原因,自然就消除了回溯。 假设轮到用A去执行匹配任务, A 1| 2| n, 而A面临的第1个输入符为a1。首先, 用1的第1终结符与输入符a1匹配,若成功,再用1的第2终结符与下一输入符a2匹配, 当1的第n终结符与当前输入符an匹配不成功时,说明1与输入串不匹配, 此时需把关于1的分析过程推倒,回到用1匹配前的状态。同样地,用2与输入串匹配,。 可见, 回溯的存在是由于分析过程中需对产生式的多个候选式进行试探性匹配
35、。若能根据面临的输入符从产生式的多个候选式中选出一个作为全权代表全权代表,使得若该候选式与输入串匹配成功,则A与输入串匹配成功, 若该候选式与输入串匹配不成功,则A与输入串匹配不成功, 这样就可以消除回溯。如何从多个候选式中选出一个全权代表? 例如, AaA | bB | cC a A 1| 2| n a 若A的n个候选式中只有一个只有一个推出的终结符串的首字符包含a (设为 i), 则候选式 i可作为A的全权代表。 这就要求匹配前先求出各个候选候选式所能推出的所有终结终结符串的首字符首字符, 即候选式的终结首符终结首符集集FIRST( )。 终结首符集终结首符集FIRST( ) 令G是一个无
36、左递归文法, 对G的所有非终结符的每个候选式, 定义 FIRST( )a | a, aVT 若 , 则FIRST()* 即FIRST( )是由所能推出的的所有所有 终结符串的首字符或。 A 1| 2| n FIRST(A)=FIRST(1)FIRST(2) 对于A 1| 2| n 若A有多个候选式的终结首符集含a, 则仍需进行试探, 此时只是减少了回溯次数, 并未消除回溯。要消除回溯, 准确地指派一个候选式去执行匹配任务, 则各个候选式的终结首符集应互不相交, 即 FIRST( i)FIRST( j)= (ij) 如何使每个非终结符的候选终结首符集互不相交? 方法是提取公共左因子提取公共左因子
37、。 提取公共左因子提取公共左因子例如, AabA | aB | ab 改写文法: AaA AbA | B | b改写第2式: AbA | B AA | 一般地, 假设文法中关于A的产生式为 A 1| 2| i | i+1|j提取公共左因子后, 改写为 AA | i+1| j A 1| 2| | i 经过反复提取公共左因子反复提取公共左因子,可使每个非终结符的候选终结首符集候选终结首符集互不相交。 消除左递归和提取公共左因子后, 文法不再含左递归且任一非终结符的候选终结首符集互不相交。此时,若不属于任一非终结符的候选终结首符集, 则可进行有效的LL(1)分析了。然而,消除左递归和提取左因子后,
38、文法中引进了大量-生成式, 这就引出自动匹配自动匹配问题。3. 自动匹配问题自动匹配问题对于文法GE: ETE E+TE | TFT T*FT | F(E) | i考虑输入串i+i #EETFTT+Ei FTi 当A面临输入符a时, 若a FIRST(A)且FIRST(A), 则考虑自动匹配问题。 对于上述算术表达式文法,若输入串为i/i, 即使让T自动匹配, “/”仍不能与后面符号匹配, 此时没必要让T自动匹配。 结论: 只有在当前输入符当前输入符能与A后的后的第一个终结符第一个终结符匹配成功时,才让A自动得到匹配。这就要求分析前先求出紧跟在A后的终结符, 即FOLLOW(A)。 FOLLO
39、W(A)的定义的定义 对文法GS的任一非终结符A, 定义 FOLLOW(A)a|S Aa,aVT 若S A, 则规定#FOLLOW(A)* 即FOLLOW(A)是所有句型所有句型中紧跟在 A之后的终结符终结符 或 # 。0 因S S, 故#FOLLOW(S)自动匹配条件自动匹配条件 当A面临输入符a时,若a FIRST(A)且FIRST(A), 则只有当a FOLLOW(A)时,才使A自动得到匹配。缺少任一条件,均不自动匹配。 若输入符aFIRST(A)且aFOLLOW(A), 则当FIRST(A)时仍需进行试探(回溯)。因此,对于存在存在 -生成式生成式的非终结符A,若要进行不带回溯的自上而
40、下分析,则FIRST(A)与与FOLLOW(A)应互不相交应互不相交。 5. 递归下降分析器递归下降分析器 递归下降分析法是一种自上而下分析法,文法的每个非终结符非终结符对应一个递归过程递归过程。分析过程从文法开始符出发,执行一组递归过程, 这样向下推导直到推出句子。 若文法不含左递归不含左递归且每个非终结符的候选式无公共左因子, 则可构造不带回溯的递归下降分析程序, 该程序由一组过程组成, 每个过程对应文法的一个非终结符。这样的分析程序称为递归下降分析器递归下降分析器。例如, 考虑不含左递归的算术表达式, 其对应的递归下降分析器: void E( ) T( ); E( ); void E(
41、) if (lookahead = = +) match (+); T( ); E( ); void T() F(); T(); void T() if (lookahead = =*) match (*); F(); T(); void F() if (lookahead = = i) match (i); else if (lookahead = =() match (); E( ); if (lookahead = =) match (); else error (); error ();说明: 考虑E的产生式: E+TE | E有两个候选式,当E面临输入符+时令第一个候选工作,当面临其
42、它符号时, E自动获得匹配。递归函数E根据这一原则设计。 假定递归函数的调用以栈栈的形式来模拟, 下面分析输入串 # i1*(i2+i3)# 的语法分析过程, “#”为分隔符。 进行语法分析时,首先将“#”和文法开始符E压入栈中,当语法分析进行到栈中仅剩“#”而输入串扫描指针已指向输入串尾部的“#”时,则语法分析成功。分析过程如图3-12所示。 3.3.2 LL(1)分析法分析法 LL(1)分析法又称预测分析法预测分析法, 是一种不带回溯的非递归自上而下分析法。 LL(1)的含义的含义: 第一个L表明自左至自左至右扫描输入串右扫描输入串; 第二个L表明最左推导最左推导; 1表明向右查看一个符号
43、。 类似地, 可有LL(k)文法, 即向前查看k个符号才能确定选用哪个产生式, 不过LL(k) (k1)在实际中极少使用。1. 表驱动的表驱动的LL(1)分析器分析器 LL(1)分析法的基本思想分析法的基本思想: 根据输入串的当前输入符确定选用某一个某一个产生式进行推导, 当该输入符与推导的第一个符号相同时，再取输入串的下一个符号, 继续确定下一个推导应选的产生式, 如此下去, 直到推出被分析的输入串为止。 一个LL(1)分析器由一张一张LL(1)分析分析表表(预测分析表)、一个先进后出分析栈一个先进后出分析栈和一个控制程序控制程序(表驱动程序)组成。 a1a2aian#分析表M控制程序输入串
44、：栈顶#x1xj输出分析栈图314 LL(1)分析器对图314的LL(1)分析器说明如下： (1)输入串输入串是待分析的符号串,它以“#”作为结束标志。(注: #VT但不是文法符号, 是由分析程序自动添加的) (2)分析栈分析栈存放分析过程中的文法符文法符号号。分析开始时栈底先放一个“#”,再压入文法开始符; 当分析栈中仅剩“#”且输入串指针指向串尾的“#”时, 分析成功。 (3)分析表分析表用一个矩阵M(二维数组) 表示,它概括了文法的全部信息。矩阵的矩阵的每一行每一行与文法的一个与文法的一个非终结符非终结符相关联相关联,而而每一列每一列与文法的一个与文法的一个终结符终结符或或“#”关联。关
45、联。分析表元素MA,a中的内容为一条A的产生式,表明当A面临输入符a时应采用的候选式;当元素内容为空时,表明A不应面临输入符a,即输入串含语法错误。(4) 控制程序控制程序根据分析栈栈顶符号栈顶符号x和当当 前输入符前输入符a决定分析器的动作: 若xa“#”,则分析成功。 若xa“#”,即栈顶符号x与当前输入符a匹配,则将x从栈顶弹出,输入串指针后移, 继续对下一个字符进行分析。 若x为非终结符非终结符A,则查分析表MA,a: i.若MA,a为一产生式,则A自栈顶弹出,MA,a中产生式的右部符号逆序压栈逆序压栈;若MA,a为A,则只将A自栈顶弹出。 ii.若MA,a为空,则发现语法错误,调用出
46、错处理程序进行处理。控制程序控制程序描述如下: 将“#”和文法开始符依次入栈; 把第一个输入符读入a; do 把栈顶符号弹出并放入x中; if (xVT) if (xa) 将下一输入符读入a; else error( ); else if (Mx,a “xy1y2yk”) 把y1y2yk按逆序入栈逆序入栈; 输出“xy1y2yk”; else error( ); while(x!=“#”)例例3.7 一个文法的LL(1)分析表如下所示, 试给出输入串aadl的分析过程。输入串aadl的分析过程如下:符号栈当前输入符输入串说 明 #Aaadl#弹出栈顶符,将AaA右部反序压栈 #Aaaadl#匹
47、配,弹出栈顶符a,读出下一输入符a #Aa dl#弹出栈顶符,将AABl右部反序压栈 #lBAa dl# 弹出栈顶符,将AaA右部反序压栈#lBAaa dl# 匹配,弹出栈顶符a,读出下一输入符d #lBAd l# 由A仅弹出栈顶符号A #lBd l# 弹出栈顶符,将BdB右部反序压栈 #lBdd l#匹配,弹出栈顶符d,读出下一输入符l #lBl # 由B仅弹出栈顶符号B #ll # 匹配,弹出栈顶符l,读出下一输入符# # 匹配,分析成功2. LL(1)分析表的构造分析表的构造 LL(1)分析器中除分析表因文法的不同而不同外, 分析栈、控制程序都相同。因此构造一个LL(1)分析器实际上就是
48、构造文法的LL(1)分析表。构造分析表M, 需预先定义FIRST集和FOLLOW集。 假定是文法任一符号串,(VTVN)*, FIRST( )a| a, aVT 若 ,则规定 FIRST() 即FIRST()是的所有所有可能推出的首首 终结符终结符或可能的。*(1)FIRST集的构造方法集的构造方法 对任一终结符a, FIRST(a)=a。 对每个非终结符每个非终结符X连续使用下述规则 直到FIRST集不再增大为止。 若有Xa,把a加入FIRST(X); 若有X,把加入FIRST(X); 若有XY,YVN,把FIRST(Y)的 所有非所有非元素元素都加入FIRST(X); 若有XY1Y2Yk,
49、而Y1Yi1都有, 则把FIRST(Yj) (j=1,2,i)的所有非 元素都加入FIRST(X); 特别地,若Y1Yk均有产生式, 则把也加入到FIRST(X)。例例1 试构造文法GE的FIRST集。 GE: ETE E+TE | TFT T*FT | F(E) i 解: FIRST(E)=+,; FIRST(T)=*,; FIRST(F)(, i ; 由TF知,把FIRST(F)的所有非 元素加入FIRST(T),故FIRST(T)=(,i; 由ET知,把FIRST(T)的所有非 元素加入FIRST(E),故FIRST(E)=(,i 对文法GS的任何非终结符A, 定义定义 FOLLOW(A
50、)a | S Aa, aVT若S A, 则规定# FOLLOW(A)FOLLOW(A)是所有所有句型中出现在紧随A 之后的终结符终结符 或 # 。*(2) FOLLOW集构造方法集构造方法 对文法每个非终结符每个非终结符A构造FOLLOW(A)。 方法是连续使用下述规则,直到FOLLOW 集不再增大为止。 对文法开始符S,把#加入FOLLOW(S)。 (由语句括号“#S#”中的S#得到) 若有AB (可为空), 则将FIRST( )加入FOLLOW(B)。 若有AB或AB且 , 则把 FOLLOW(A)加入到FOLLOW(B)。*例例2 试构造文法GE的FOLLOW集。 GE: ETE E+T
