编译原理ppt3_5.ppt

3 5LR分析器 LR k L表示从左至右扫描输入串 R表示构造一个最右推导的逆过程 k指的是在决定语法分析动作时需要向前看的符号个数 LR分析法的缺点 手工实现工作量大构造LR分析表的方法简单LR方法 SLR 规范的LR方法向前搜索的LR文法 LALR 描述能力 规范LR LALR SLR实现代价 规范LR LALR SLR 3 5 1LR分析算法 LR分析程序 LR分析器模型 栈 语法分析表 分析表构成 动作表 action 和转向表 goto 注 Si表示状态 ai表示终结符 Ai表示非终结符 actiongoto action s a 规定了状态s面临输入符号a时应该采取什么动作 移进 把 s a 的下一状态s goto s a 和输入符号a推进栈 下一输入符号变成现行输入符号 归约 指用某一产生式A 进行归约 接受 宣布分析成功 停止分析器的工作 报错 报告发现错误 调用出错处理程序 扫描输入串就可以发现错误位置 goto s X 则指出状态s面对文法符号X 终结符或非终结符 时下一状态是什么 goto s X 若X VT 表示在当前状态下 读入X应转向什么状态 若X VN 表示当前栈顶句柄归约成X后 应转向什么状态 soX1s1 Xmsm aiai 1 an 分析器根据action sm ai 确定下一步动作1 若action sm ai 为移进 且s goto sm ai 则二元式格局变为 s0X1s1 Xmsmais ai 1 an 2 若action sm ai 为按A 归约 二元式变为 s0X1s1 Xm rsm rAs aiai 1 an 此处 s goto sm r A r为 的长度 Xm r 1 Xm3 若action sm ai 为 接受 则二元式不再变化 变化过程终止 宣布分析成功 4 若action sm ai 为 报错 则二元式变化过程终止 报告错误 算法3 3LR分析算法 令a指向 的第一个符号 while 1 令s是栈顶的状态 if action s a 移进t 把a和t依次压入栈顶 a指向下一个输入符号 elseif action s a 按文法产生式A 归约 从栈顶弹出2 个符号 令t是现在的栈顶状态 把A和goto t A 依次压入栈顶 输出产生式A elseif action s a 接受 break 分析完成 elseerror 例 文法G E 1 E E T 2 E T 3 T T F 4 T F 5 F E 6 F id分析id id id的识别过程 其LR分析表为 si表示把当前符号和状态i压入栈rj表示按第j个产生式归约acc表示接受空白表示出错 栈输入动作输出0id id id s50id5 id id 用F id归约F id0F3 id id 用T F归约T F0T2 id id s70T2 7id id s50T2 7id5 id 用F id归约F id0T2 7F10 id 用T T F归约T T F0T2 id 用E T归约E T0E1 id s60E1 6id s50E1 6id5 用F id归约F id0E1 6F3 用T F归约T F0E1 6T9 用E E T归约E E T0E1 接受 3 5 2LR文法和LR分析方法的特点 对于给定文法G 如果能为G构造出LR语法分析表 则称G是LR文法 LR语法分析器不需要扫描整个栈就可以知道什么时候句柄出现在栈顶 栈顶的状态符号包含了所需要的一切信息 goto s X 定义了一个以文法符号为字母表的DFA 每步需要向前看k个符号的LR语法分析器所分析的文法称为LR k 文法一般k 0或k 1 LR分析方法的特点栈中的文法符号总是形成一个活前缀分析表的转移函数本质上是识别活前缀的DFA栈顶的状态符号包含了确定句柄所需要的一切信息是已知的最一般的无回溯的移进 归约方法能分析的文法类是预测分析法能分析的文法类的真超集LR分析法的缺点 手工实现工作量大 3 5 3构造SLR分析表 构造分析表的基本策略 构造文法G的一个有限自动机 它能识别文法中的所有活前缀 字的前缀是指该字的任意首部 例如 字ABC的前缀有 A AB ABC 活前缀 ViablePrefix 是指规范句型的一个前缀 这种前缀不含句柄之后的任何符号 活前缀有两种类型 1 归态活前缀活前缀的尾部正好是句柄之尾 这时可以进行归约 归约之后又成为另一句型的活前缀 2 非归态活前缀句柄尚未形成 需要继续移进若干符号之后才能形成句柄 在LR分析过程中的任何时候 栈里的文法符号 自栈底向上 X1X2 Xm应该构成活前缀 把输入串的剩余部分配上之后即应成为规范句型 当然 这个输入串必须确实是文法的一个句子 反过来说 只要输入串的已扫描部分保持可归约成一个活前缀 那就意味着扫描过的部分没有错误 构造出一个FA 它能识别某文法G的所有活前缀可以文法的终结符和非终结符都看成有穷自动机的输入符号 每次把一个符号进栈看成已识别过了该符号 同时状态进行转换 当识别到可归前缀时 相当于在栈中形成句柄 认为达到了识别句柄的终态 项目 项目 item 在每个产生式的右部适当位置添加一个圆点构成项目例如 产生式A XYZ对应有4个项目A XYZA X YZA XY ZA XYZ 产生式A 只有一个项目A 有限自动机的每一个状态由一个项目构成 项目圆点的左部表示分析过程的某个时刻用该产生式归约时句柄已识别的部分 圆点右部表示待识别的部分 拓广文法 如果文法G的开始符号是S 那么G的拓广文法G 是在文法G的基础上增加一个新的开始符号S 和产生式S S 将文法进行拓广 保证文法开始符号不出现在任何产生式右部 即增加产生式S S 并令S S作为初态项目 闭包运算closure 如果I是文法G的一个项目集 定义和构造I的闭包closure I 如下 1 I的项目都在closure I 中2 若A B 属于closure I 则每一形如B 的项目也属于closure I 3 重复2 直到closure I 不再扩大 closure的计算 functionclosure I beginJ I repeatforJ的每个项目A B 和G的每个产生式B 若B 不在J中do把B 加入J until没有新项目可加入J returnJend 例 对于以下文法 计算closure E E E EE E TE TT T FT FF E F id closure E E E EE E TE TT T FT FF E F id 核心项目 初始项目和所有圆点不在左端的项目非核心项目 圆点在左端的非初始项目 goto函数 定义转换函数如下 goto I X closure J 其中 I为某项目集 X为文法符号J 任何形如A X 的项目 A X 属于I 如果I是对某个活前缀 有效的项目集 那么goto I X 是对活前缀 X有效的项目集 例 若I E E E E T 则goto I 为E E TT T FT FF E F id 项目集的构造 procedureitems G beginC closure S S repeatforC中的每个项目集I和G 中的每个符号XDOIFgoto I X 非空且不属于CTHEN把goto I X 放入C中untilC不再增大end 文法3 11的项目集规范族 I0 E EE E TE TT T FT T FT FF E F i I1 E E E E T I2 E T T T F I3 T F I4 F E E E TE TT T FT FF E F i I5 F i I6 E E TT T FT FF E F i I7 T T FF E F i I8 F E E E T I9 E E T T T F I10 T T F I11 F E 文法3 11的goto函数 SLR语法分析表 1 构造G 的LR 0 项目集规范族C I0 I1 In 2 从Ii构造状态i 它的分析动作如下 a 若项目 A a 属于Ii且GO Ii a Ij a为终结符 则置action i a 为 sj b 若项目A 属于Ii 那么 对任何终结符a a FOLLO