编译原理并第五章.pptVIP

注意：在调用子程序时，已读入一个TOKEN字，因此每个子程序在返回时应把后面的TOKEN字读入（即调用GETNEXT（TOKEN）） 递归子程序数等于文法中非终结符数，减少文法中非终结符数就可减少子程序数目。 l?? 递归子程序的优缺点： 1.?优点：简单、易懂，子程序编写速度快，容易保证分析的正确性。 2.?缺点：对文法要求高，必须满足LL（1）文法；递归调用速度慢，占用空间多；有的高级语言不允许递归。 ?5.5.2 预测分析法 也称LL（1）分析法，这种方法由三部分组成： 预测分析程序 2. 分析栈：存放替换当前非终结符的某个候选式的符号串（倒放在栈中） 3. 预测分析表（即LL（1）分析表），它是一个二维矩阵，根据SELECT集构造 表的每一行对应一个非终结符 每一列对应一个终结符或# 分析表可用数组M[A，a]表示，A∈VN，a∈VT或#。 M[A，a]的内容（值）存放关于A的一条产生式，表明非终结符A和终结符a匹配时，应选择的候选式。当M[A，a]无内容时，表明出错。 一、预测分析程序的框图 (P94 –图5.11) BEGIN INITIAL： PUSH ‘#’ ； PUSH 文法开始符 S； 读入第一个字符送 a； ? REPEAT POP X； {弹栈，送入X} IF X∈VT THEN IF X=a THEN 读入下一个字符送a ELSE ERROR IF X∈VN THEN CASE M[X，a] OF ‘X→X1X2…Xn’：PUSH XnXn-1…X1； ‘X→ε’： SKIP； {空操作} ‘空白或错误码’：ERROR ENDCASE UNTIL X=‘#’ IF X=a=‘#’ THEN 正确接收输入串并停止 ELSE ERROR END； 二、分析表的构造算法 对给定文法，先求各产生式的SELECT集，判断是否为LL（1）文法，是，则构造LL（1）分析表。 假定初始时分析表为空。 i：=n； { n是最大产生式编号，即产生式数} REPEAT FOR i： A→ ? DO FOR 每个a∈SELECT（A→ ? ） DO 把 A→? 填入M[A，a]中 {填α即可} i：=i-1 UNTIL i=0 其余空白M[A，a]填入‘出错码’{也可用空白表示出错} 三、举例 1、书中例子 2、对下面的文法G： S→aBc | bAB A→aAb | b B→b |ε 分析babb# 是否为G的句子 （1）??? 判断G是否为LL（1）文法 SELECT（S→aBc）={a} SELECT（S→bAB）={b} SELECT（A→aAb）={a} SELECT（A→b）={b} SELECT（B→b）={b} SELECT（B→ε）=FOLLOW（B）={c，#} 显然是LL（1）文法。 S→aBc | bAB A→aAb | b B→b |ε (2) 构造LL（1）分析表 A b c ? A→aAb A→b ? S→bAB S→aBc # B→ε B A S B→ε B→b (3) 分析输入串babb#的过程 步骤 分析栈 剩余输入串 所用产生式 栈顶元素与输入符 1 #S babb# S→bAB （S，b） 2 #BAb babb# b匹配 （b，b） 3 #BA abb# A→aAb （A，a） 4 #BbAa abb# a匹配 （a，a） 5 #BbA bb# A→b （A，b） 6 7 8 9 #Bbb #Bb #B # bb# b# # # b匹配 b匹配 B→ε 接受 （b，b） （b，b） （B，#） （#，#） 步骤 分析栈 剩余输入串 所用产生式 栈顶元素与输入符 分析输入串bac#的过程 步骤 分析栈 剩余输入串 所用产生式 栈顶元素与输入符 1 2 3 4 5 #S #BAb #BA #BbAa #BbA bac# bac