编译原理语法分析.ppt

第3章 语法分析 语法分析是编译过程的核心部分。 语法分析的基本任务是在词法分析识别 出单词符号串的基础上，分析判断程序的语 法结构是否符合语法规则。 语言的语法结构用上下文无关文法来描 述，因此，语法分析器的任务本质上是按上 下文无关文法的产生式，确定整个单词串是 否构成语法上正确的程序。 语法分析的方法通常分为两类： 自上而下分析法和自下而上分析法 3.1 文法和语言 3.2 推导与语法树 3.3 自上而下分析方法 3.4 自下而上分析方法 3.5 LR分析法 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为非空非终结符集,且VTVN=; (3) S为文法开始符, SVN; (4)是产生式的非空有限集, 其中每个 产生式(规则)记作 或 := 左部(VTVN)+至少含一非终结符, 右部(VTVN)*。 产生式 (也称产生式规则或规则) 是 定义语法实体的一种书写规则。一个语 法实体的相关规则可能不止一个, 如: P1, P2 , Pn 相同左部的产生式可合并为一个: P 1| 2| n 其中, i(i=1,2,n)称为P的候选式。 例3.1 试构造产生标识符的文法。 分析: 用L表示字母,D表示数字,T表示字母或数字 , 则 Labz D019 TLD 用S表示字母数字串,则ST是字母数字串,即 ST | ST 标识符I或为单个字母, 或为一字母后 跟字母数字串, 即 ILLS 解: 产生标识符的文法GI为： G=(a,b,z,0,9,I,S,T,L,D,I,) 其中,: ILLS STST TLD Labz D019 例3.2 写一文法, 使其语言是奇数集, 但不允 许出现以0打头的奇数。 解: 将奇数划分为三个部分： 最高位允许出现19,用非终结符B表示; 中间部分可出现任意多位数字09, 每一位用非终结符D表示; 最低位只出现1,3,5,7,9, 用A表示。 由于中间部分可任意位,故需另引入一 非终结符M,它包括最高位和中间部分。 M B 最 高 位 中间位 DDDA 最 低 位 解: 奇数集文法GN为: G=(0,1,9,N,A,M,B,D,N,) : NA | MA MB | MD A1 | 3 | 5 | 7 | 9 B1|2|3|4|5|6|7|8|9 D0 | B 3. 文法产生的语言 设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 (2)若记1 1, 则1 n表示从1出发,经过 0步或若干步可推导出n, 即1 n意味着或1=n, 或1 n。 + 0 * * + 例如,考虑算术表达式文法GE： EE+EE*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的一个句子。 由上述定义知： 仅含终结符的句型是一个句子。 开始符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型文法或短语文法, 记为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型文法或上下文无关文法, 记为CFG。 2型文法相应的语言称为2型语言或 上下文无关语言。 它的识别系统是下推自动机。 4 3型文法与3型语言 (对应有限自动机) 若文法G的每个产生式具有下列形式： Aa 或 AaB 其中，A,BVN，aVT*， 则文法G称为3型文法或正规文法或右线 性文法，记为RG。 3型文法相应语言为3型语言或正规语言 。 它的识别系统是有限自动机。 3型文法还可呈左线性形式： Aa 或 ABa 5. 四类文法的关系与区别 从0型文法到3型文法逐步增加限制 。 一般地,13型文法属于0型文法，2,3 型文法属于1型文法,3型文法属于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型文法描述语法,用 下推自动机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| b b b b a a a a S A B 2 C 3.1.3 正规式与上下文无关文法 1. 正规式到上下文无关文法的转换 由正规式构造CFG的一种方法： (1)构造正规式的NFA； (2)若0为初始状态, 则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 3 a b abb GA0: A0aA0bA0aA1 A1bA2 A2bA3 A3 由正规式构造CFG的另一种方法： 通过分析正规式凭经验直接构造。 例如, 把(a|b)*abb看作(a|b)*和abb两部分,第 一部分是由0个或若干个a和b组成的字符 串,第二部分仅由abb字符串组成,由此得 到CFG GA0如下： GA0: AHT HaH|bH| Tabb 2. 正规式与CFG描述的对象 CFG既可描述语法,又可描述词法。 基于下述原因,通常用正规式描述词法: (1)词法规则简单,用正规式已足以描述; (2)正规式的表示比CFG更简洁、直观 和易于理解； (3) FA的构造比PDA(下推自动机)的构 造简单且效率高。 注意: (1)语言的描述和语言的识别是表示一 种语言的两个不同侧面, 二者缺一不可。 (2)正规式通常适合于描述线性结构, 如标识符、关键字和注释等; 上下文无关 文法通常适合于描述具有嵌套(层次)性质 的非线性结构, 如 if-else语句、while语句 。 3.2 推导与语法树 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 注意: 推导过程不唯一, 通常只考虑最左 推导或最右推导。 最右推导又称为规范推导。 规范推导的逆过程称为规范归约。 2. 短语 如果S A且A , 则称是句型关于非终结符A的一 个短语,简称是的一个短语。 如果S A且A , 则称为句型的一个直接短语或 简单短语。 注意: 短语的两个条件缺一不可。 考虑i+i*i, E i+i, 但i+i不是短语 * + * + 3. 句柄 句型的最左直接短语称为句柄。 注意, 一个句型的直接短语不唯一, 但最左直接短语唯一。 例如, 对S A , 若为终结符串, 则句型中的句柄为。 将句型中的句柄用产生式的左部 符号代替便得到新句型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)句子的识别或分析。 为便于分析句子而引入语法树。 语法树以图示化形式把句子分解成各 个组成部分,以分析句子的语法结构。 语法树表示法与文法规则完全一致,但 更为直观和完整。 满足下列条件的树称为文法G的语法树: (1)每个结点用G的一个终结符或非终结 符标记; (2)根结点用文法开始符S标记; (3)内部结点一定是非终结符,若某内部结 点A有n个分支, 且其所有子结点从左 至右依次标记为x1, x2, ,xn,则 Ax1x2xn一定是G的一条产生式; (4)若某结点标记为,则它必为叶结点且 是其父结点的唯一子结点。 一个句型对应的语法树以文法开始符 S作为根结点,并随着推导逐步展开。当某 非终结符被产生式右部的某候选式替换时 ,该非终结符对应的结点产生出下一代结 点,即候选式中从左至右的每个符号依次 顺序对应一个新结点,且每个新结点与其 父结点之间都有一连线。在一棵语法树生 长过程中的任何时刻,所有没有后代的叶 结点的自左至右排列是一个句型。 例如,句子i+i*i的语法树如下: E EE E*E ii i 第一代 第二代 第三代 第四代 构造语法树时, 一个句型的最左推导 及最右推导只决定先生长左子树还是先 生长右子树, 推导结束时相应的语法树已 看不出先生长的是哪个子树。 因此, 一棵语法树表示一个句型种种 可能的不同推导过程, 包括最左(最右)推 导。若坚持使用最左(最右)推导, 则一棵 语法树等价于一个最左(最右)推导, 这种 等价性包括语法树的每一步生长和推导 过程的每一步展开的完全一致性。 2. 子树和短语 语法树的某个结点连同它的所有后代组 成了一棵子树。 只含有单层分枝的子树称为简单子树。 子树与短语的关系: (1)短语: 子树的所有叶结点组成的符号 串是相对于子树根的短语； (2)直接短语: 简单子树的所有叶结点组 成的符号串是直接短语; (3)句柄: 最左简单子树的所有叶结点组 成的符号串为句柄; (4)素短语: 子树的所有叶结点组成的 含终结符的符号串, 且在该子树中 没有有包含终结符的更小子树。 显然, 从语法树出发寻找短语、直接 短语、句柄和素短语直观得多。但要注 意, 子树叶结点组成的符号串是指由该子 树根开始向下生长的所有叶结点,该子树 的部分叶结点并不是该子树的短语。 考虑句型E+E*i的语法树: 短语: i、E*i和E+E*i; 直接短语: i; 句柄: i; 素短语: i E EE E*E i 3. 文法的二义性 若文法G的一个句子能找到两种不 同的最左推导(最右推导), 即存在两棵不 同的语法树, 则称这个句子是二义性的 。 若一个文法包含二义性句子, 则这个文法是二义文法, 否则是无二义文法。 例如, 对文法(3.1), 句子i+i*i存在两种最左(右)推导: E EE E * E i E EE E * E i i i (a) i i (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是二义性文法。 S ifS (a)(b) B S ifS else B S B S ifS else ifSB 4. 文法二义性的消除 一个文法是二义性的, 并不说明文法 所描述的语言是二义性的。即对于一个二 义文法GS, 若能找到一个非二义文法 GS, 使得L(G)=L(G), 则该二义文法的二 义性可以消除。若找不到这样的GS,则 二义文法描述的语言为先天二义性的。 文法二义性的消除方法: (1)不改变文法中原有的语法规则, 仅加进 一些语法的非形式规定。 如对文法(3.1), 不改变已有产生式, 仅加 进运算符的优先顺序和结合规则, 即 *优先于+, 且*,+都服从左结合。 (2)构造一个等价的无二义文法。即把排除 二义性的规则合并到原文法中, 改写原 文法。 GE: EE+TT TT*FF F(E)i 此时,句子i+i*i只有 唯一 一棵语法树。 例如, 将文法(3.1)改写为无二义文法GE: E ET FT F i i T F i * 例3.6 将下述文法GS的二义性消除: GS: Sif b Sif b S else SA 解: 消除GS的二义性可采用两种方法: (1)不改变已有规则, 仅加 进一项非形式的语法规 定: else与离它最近的if 匹配, 这样, 句子if b if b A else A对应唯一的一 棵语法树。 S b S ifS else AA bif S (2)改写文法GS为GS: SS1| S2 S1if b S1 else S1|A S2if b S|if b S1else S2 由于引起二义性的原 因是if-else语句的if后可以 是任意if语句, 故改写文法 时规定if和else之间只能是if -else语句或其它语句。 S 1 bS 1 ifS 1 else AA bifS S 2 S 编译过程中希望一个文法是无二义 性的, 这样句子的分析可按唯一确定的 方式进行。但文法的二义性是不可判定 的, 即不存在一种算法能在有限步内判 定一个文法是否为二义性的。不过, 二 义文法有时也可带来一定好处, 如语法 分析中二义文法的应用。 3.3 自上而下分析方法 自上而下分析从文法开始符出发, 向下推导, 推出句子。即寻找一个推导 序列, 使推导出的句子恰为输入串; 亦即 ,从根结点出发向下生长出一棵语法树, 其叶结点组成的句子恰为输入串。 显然, 语法树的每一步生长(推导)都 以能否与输入串匹配为准。 1. 自上而下分析存在的不确定性 文法GS: SxAy Aaba 若输入串为xay, 则其分析过程如下: (1)首先建立根结点S。 (2)文法关于S的产生式只有一个。 yAx S 下一待分析字符a与A匹配。 (3)非终结符A有两个候选式, 先选用第一个候选式: yAx S ab (4)下一待分析字符y与b匹配, 失败。 (5)将A生成的子树注销, 指针回退到输 入串的第二个字符a。 (6) A选用第二个候选式: yAx S a 这时输入串中a与叶结点a匹配。 (7) 下一个待分析字符为y, 而语法树下 一个叶结点也为y, 匹配成功。 在上述分析过程中, 若有多个候选式 可供选择, 则逐一试探每个候选式。一次 试探失败时, 必须回溯到该试探的初始现 场, 包括注销已生长子树、指针回退到失 败前状态。这种带回溯的自上而下分析方 法是一种穷举法, 效率极低, 在实用编译程 序中很少使用。 2. 确定的自上而下分析 实现确定的自上而下分析需满足条件: (1)文法不含左递归。 左递归: AA 或 A A 左递归的存在可能使自上而下分析 过程陷入无限循环, 故使用自上而下分析 法必须消除文法的左递归。 (2)分析过程无回溯。 回溯的存在可能使已做的大量语法 和语义分析推倒重来, 这会严重影响效率 , 故使用自上而下分析法必须消除回溯。 + 3. 左递归的消除 直接左递归的消除 方法: 引入一个新的非终结符,把含有 左递归的产生式改写为右递归形式。 例如: AA | , 是任意串且不以A开头。 A的产生式可改写为: AA AA| 例如, 算术表达式文法GE为: GE: EE+T | T TT*F | F F(E) | i 消去直接左递归后得到文法GE: GE: ETE E+TE | TFT T*FT | F(E) | i 一般地, 设文法中A的产生式为: AA1|A2|Am| 1|2|n 其中,每个都不等于 每个都不以A开头 消除A的直接左递归, 文法可改写为: A1A | 2A | nA A1A | 2A |mA | 例如, 试消除EE+T|ET|T的左递归。 解: 消除左递归后变为 ETE E+TE | TE | 间接左递归的消除 例如, 文法GS: SQc | c QRb | b RSa | a 如何消除文法的间接左递归？ 间接左递归的存在是由于非终结符之 间形成了循环推导, 只要把循环推导中的 某个连接切断, 间接左递归就消除了。 切断循环推导中的某个连接的方法： Step1. 对n个产生式中的某一个进行至多 n-1次替换, 使间接左递归变成直 接左递归, 再消除之。 例如, 消除上述文法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; i 终结首符集FIRST() 令G是一个无左递归文法, 对G的所有 非终结符的每个候选式, 定义 FIRST()a | a, aVT 若 , 则FIRST() * * 即FIRST()是由所能推出的的所有 终结符串的首字符或。 A1| 2|n FIRST(A)=FIRST(1)FIRST(2) 对于A1| 2|n 若A有多个候选式的终结首符集含a, 则仍需进行试探, 此时只是减少了回溯次 数, 并未消除回溯。要消除回溯, 准确地指 派一个候选式去执行匹配任务, 则各个候 选式的终结首符集应互不相交, 即 FIRST(i)FIRST(j)= (ij) 如何使每个非终结符的候选终结首符 集互不相交? 方法是提取公共左因子。 提取公共左因子 例如, AabA | aB | ab 改写文法: AaA AbA | B | b 改写第2式: AbA | B AA | 一般地, 假设文法中关于A的产生式为 A1|2|i | i+1|j 提取公共左因子后, 改写为 AA | i+1| j A1| 2| | i 经过反复提取公共左因子,可使每个 非终结符的候选终结首符集互不相交。 消除左递归和提取公共左因子后, 文法不再含左递归且任一非终结符的候 选终结首符集互不相交。此时,若不属 于任一非终结符的候选终结首符集, 则可 进行有效的LL(1)分析了。然而,消除左 递归和提取左因子后, 文法中引进了大量 -生成式, 这就引出自动匹配问题。 3. 自动匹配问题 对于文法GE: ETE E+TE | TFT T*FT | F(E) | i 考虑输入串i+i # E ET FTT+E i FT i 当A面临输入符a时, 若aFIRST(A) 且FIRST(A), 则考虑自动匹配问题。 对于上述算术表达式文法,若输入串 为i/i, 即使让T自动匹配, “/”仍不能与后 面符号匹配, 此时没必要让T自动匹配。 结论: 只有在当前输入符能与A后的 第一个终结符匹配成功时,才让A自动得 到匹配。这就要求分析前先求出紧跟在 A后的终结符, 即FOLLOW(A)。 FOLLOW(A)的定义 对文法GS的任一非终结符A, 定义 FOLLOW(A)a|S Aa,aVT 若S A, 则规定#FOLLOW(A) * * 即FOLLOW(A)是所有句型中紧跟在 A之后的终结符 或 # 。 0 因S S, 故#FOLLOW(S) 自动匹配条件 当A面临输入符a时,若aFIRST(A)且 FIRST(A), 则只有当aFOLLOW(A)时 ,才使A自动得到匹配。缺少任一条件,均 不自动匹配。 若输入符aFIRST(A)且 aFOLLOW(A), 则当FIRST(A)时仍需进 行试探(回溯)。因此,对于存在-生成式的 非终结符A,若要进行不带回溯的自上而下 分析,则FIRST(A)与FOLLOW(A)应互不 相交。 5. 递归下降分析器 递归下降分析法是一种自上而下分析 法,文法的每个非终结符对应一个递归过程 。分析过程从文法开始符出发,执行一组递 归过程, 这样向下推导直到推出句子。 若文法不含左递归且每个非终结符的 候选式无公共左因子, 则可构造不带回溯 的递归下降分析程序, 该程序由一组过程 组成, 每个过程对应文法的一个非终结符 。这样的分析程序称为递归下降分析器。 例如, 考虑不含左递归的算术表达式, 其对应的递归下降分析器: void E( ) T( ); E( ); void E( ) 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面临输入符+ 时令第一个候选工作,当面临其它符号时 , E自动获得匹配。递归函数E根据这一 原则设计。 假定递归函数的调用以栈的形式 来模拟, 下面分析输入串 # i1*(i2+i3)# 的 语法分析过程, “#”为分隔符。 进行语法分析时,首先将“#”和文法 开始符E压入栈中,当语法分析进行到栈 中仅剩“#”而输入串扫描指针已指向输 入串尾部的“#”时,则语法分析成功。分 析过程如图3-12所示。 3.3.2 LL(1)分析法 LL(1)分析法又称预测分析法, 是一 种不带回溯的非递归自上而下分析法。 LL(1)的含义: 第一个L表明自左至 右扫描输入串; 第二个L表明最左推导; 1 表明向右查看一个符号。 类似地, 可有LL(k)文法, 即向前查看 k个符号才能确定选用哪个产生式, 不过 LL(k) (k1)在实际中极少使用。 1. 表驱动的LL(1)分析器 LL(1)分析法的基本思想: 根据输入 串的当前输入符确定选用某一个产生式 进行推导, 当该输入符与推导的第一个符 号相同时，再取输入串的下一个符号, 继 续确定下一个推导应选的产生式, 如此下 去, 直到推出被分析的输入串为止。 一个LL(1)分析器由一张LL(1)分析 表(预测分析表)、一个先进后出分析栈和 一个控制程序(表驱动程序)组成。 a1a2aian# 分析表M 控制程序 输入串： 栈顶 # x 1 x j 输出 分析栈 图314 LL(1)分析器 对图314的LL(1)分析器说明如下： (1)输入串是待分析的符号串,它以“#” 作为结束标志。(注: #VT但不是文法 符号, 是由分析程序自动添加的) (2)分析栈存放分析过程中的文法符 号。分析开始时栈底先放一个“#”,再压 入文法开始符; 当分析栈中仅剩“#”且输 入串指针指向串尾的“#”时, 分析成功。 (3)分析表用一个矩阵M(二维数组) 表示,它概括了文法的全部信息。矩阵的 每一行与文法的一个非终结符相关联,而 每一列与文法的一个终结符或“#”关联 。分析表元素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为空,则发现语法错误,调 用出错处理程序进行处理。 控制程序描述如下: 将“#”和文法开始符依次入栈; 把第一个输入符读入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#匹配,弹出栈顶符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)分析器实际上就是构造 文法的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,而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)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+TE | TFT T*FT | F(E) | i 解:1)FOLLOW(E)=#; 2)由ETE知, FIRST(E)属于 FOLLOW(T), 即FOLLOW(T)+; 由E+TE |, FIRST(E)属于 由TFT知, FIRST(T)属于 FOLLOW(F), 即FOLLOW(F)*; 由T *FT|知,FIRST(T)属于 由F(E) | i知, FIRST()属于 FOLLOW(E), 即FOLLOW(E),#; 3)由ETE知, FOLLOW(E)属于FOLLOW(E), 即FOL