编译原理第3讲(上).pptVIP

第三讲 语法分析; 基本思想：从文法的开始符号出发，推 导出句子 回溯→避免条件 First(x), Follow(u) 基本问题 无限循环→消除左递归 递归子程序法 分析方法 LL(1)分析法 ; 基本思想：从输入串开始逐步归约 基本问题：归约的问题 简单优先 优先分析法 算符优先 优先函数的构造 分析方法 规范句型活前缀 基础知识 LR(0)项目及项目集 LR(1)项目及项目集 LR分析法 LR分析器 分析栈、分析表 分析方法 LR分析表的构造 二义性文法的分析 实现技术——移进归约 ;§1.语法分析概述;二、分析方法;§2.自上而下的语法分析; 2.问题： ·这是一种自上而下的试探法，有时免不了要走回头路——回溯。 ·自左向右建立子树—左递归文法会造成死循环。 3.解决办法： (1)左递归问题：改写产生式，变左递归为右递归。 ①直接左递归：直接见诸于产生式的左递归，如 P→Pα,P∈VN, α∈(VT∪VN)* 这种直接左递归可以通过直接扫描产生式发现，也容易解决——改写产生式即可。;如： P→Pα1∣Pα2∣…∣Pαm∣β1∣β2∣…∣βn 其中P∈VN,αi,βj ∈(VT∪VN)* 且α≠?, β不以P开头 改写成 P→β1 P ∣β2 P ∣…∣βn P P →α1 P ∣α2 P ∣…∣αm P∣ε 例：文法G[E]: E →E+T∣T 改写成 E→TE E→+TE∣ε T →T*F ∣ F 改写成 T→FT T→*FT∣ε ; ②消除左递归：通过改写产生式我们可以消除直接左递归，但不能完全消除左递归，因为还存在着间接左递归的问题。 例如文法G[P]: P→Qc∣c Q→Rb∣b R→Pa∣a 表面上并看不出它的左递归性，但是仔细观察时不难发现P,Q,R都是左递归的，因为 P? Qc? Rbc? Pabc，即P ?+Pabc； Q ?+Qcab,R ?+Rbca亦然。 对这种左递归的消除就稍微麻烦一些。首先，从产生式中找这种形式的左递归。其思想也就是通过推导来寻找左递归、并进一步修改产生式。为此，我们设计以下算法：;消除左递归算法： Ⅰ.按任一顺序把文法G的所有非终结符排序成P1,P2,…Pn，按此顺序执行： Ⅱ.FOR i=1 TO n DO BEGIN FOR j=1 TO i-1 DO 把形如Pi→Pjγ的产生式改写成 Pi→δ1γ∣δ2γ∣…∣δkγ，其中 Pj →δ1∣δ2∣…∣δk是关于Pj的所 有产生式； 消除关于Pi的直接左递归性 END Ⅲ.化简由Ⅱ所得的文法——去除无用的非终结符。;例如上述文法G[P]： P→Qc∣c Q→Rb∣b R→Pa∣a Ⅰ.排序：R,Q,P Ⅱ. R无直接左递归。将R代入Q的候选式中得Q→Pab∣ab∣b，也无直接左递归；Q代入P得P→Pabc∣abc∣bc∣c，出现左递归了！消除P的直接左递归后得P→abcP‘∣bcP’ ∣cP‘, P’→abcP‘∣ε 。 如此可得文法为：  P→abcP∣bcP∣cP, P →abcP∣ε ，Q→Pab∣ab