编译原理讲义 (第五章:语法分析 自底向上分析技术) 南京大学计算机系 赵建华
编译原理讲义 (第五章:语法分析-- 自底向上分析技术) 南京大学计算机系 赵建华
概论 从输入符号出发,试图把它规约成识别 符号。每一步都寻找特定得某个类型的 短语(一般是简单短语)进行规约 在分析过程中,每次规约的都是最左边 的简单短语(或其它短语) 从语法树的角度,以输入符号为树的末 端结点,试图向根结点方向往上构造语 法树
概论 • 从输入符号出发，试图把它规约成识别 符号。每一步都寻找特定得某个类型的 短语（一般是简单短语）进行规约。 • 在分析过程中，每次规约的都是最左边 的简单短语（或其它短语）。 • 从语法树的角度，以输入符号为树的末 端结点，试图向根结点方向往上构造语 法树
基本问题 如何找出进行直接规约的简单短语? 将找到的简单短语规约到哪个非终结符 号
基本问题 • 如何找出进行直接规约的简单短语？ • 将找到的简单短语规约到哪个非终结符 号？
讨论前提 和自顶向下技术同样,不考虑符号的具 体构成方式 文法是压缩了的 识别过程是从左到右,自底向上进行的。 般都采用规范规约:每一步都是对句 柄进行规约(特例除外)
讨论前提 • 和自顶向下技术同样，不考虑符号的具 体构成方式。 • 文法是压缩了的。 • 识别过程是从左到右，自底向上进行的。 一般都采用规范规约：每一步都是对句 柄进行规约（特例除外）
基本方法 基本都采用移入规约方法 使用一个栈来存放规约得到的符号 在分析的过程中,识别程序不断地移入 符号。移入的符号暂时存放在一个栈中 日在已经移入的(和规约得到的)符 号串中包含了一个句柄时,将这个句柄 规约成为相应的非终结符号
基本方法 • 基本都采用移入-规约方法。 • 使用一个栈来存放规约得到的符号。 • 在分析的过程中，识别程序不断地移入 符号。移入的符号暂时存放在一个栈中。 一旦在已经移入的（和规约得到的）符 号串中包含了一个句柄时，将这个句柄 规约成为相应的非终结符号
基本方法(续) 规约中的动作有4类 移入:读入一个符号并把它规约入栈 规约:当栈中的部分形成一个句柄(栈顶的 符号序列)时,对句柄进行规约 接受:当栈中的符号仅有#和识别符号的时 候,输入符号也到达结尾的时候,执行接受 动作 当识别程序觉察出错误的时候,表明输入符 号串不是句子。进行错误处理
基本方法（续） • 规约中的动作有4类 – 移入：读入一个符号并把它规约入栈。 – 规约：当栈中的部分形成一个句柄（栈顶的 符号序列）时，对句柄进行规约。 – 接受：当栈中的符号仅有#和识别符号的时 候，输入符号也到达结尾的时候，执行接受 动作。 – 当识别程序觉察出错误的时候，表明输入符 号串不是句子。进行错误处理
例子 文法G5.1E]:E:=E+E*E(E 输入符号串 已处理符号未处理符号句型句柄规则 *1+1i E∴=i EE i+1 E*+i E*i+i E E*+i1 E∷=1 ERE +++ EE+I EE E:EE E E+ E+i E+i E∷=1 E+E E+EE+EE∷三E+E E
例子 i *i+i i*i+i i E::=i E *i+i E*i+i E* i+i E*i+i E*i +i E*i+i i E::=i E*E +i E*E+i E*E E::=E*E E +i E+i E+i E+i i E::=i E+E E+E E+E E::=E+E E 文法G5.1[E]: E::=E+E|E*E|(E) 输入符号串：i*i+i 已处理符号 未处理符号 句型 句柄 规则
例子的解释 当栈中的符号的栈顶部分还不能形成句柄时, 进行移入操作。 旦发现栈顶部分形成了句柄的时候,对该句 柄进行规约。将句柄出栈,然后将规约得到的 非终结符号压栈。 如果输入是句子,则栈中的符号(从底到上) 和未处理的符号组成句型。 在例子中,发现句柄和规约是人为干预的结果。 所以移入-规约不是实际可运行的技术,而是技 术的模板
例子的解释 • 当栈中的符号的栈顶部分还不能形成句柄时， 进行移入操作。 • 一旦发现栈顶部分形成了句柄的时候，对该句 柄进行规约。将句柄出栈，然后将规约得到的 非终结符号压栈。 • 如果输入是句子，则栈中的符号（从底到上） 和未处理的符号组成句型。 • 在例子中，发现句柄和规约是人为干预的结果。 所以移入-规约不是实际可运行的技术，而是技 术的模板
简单优先分析技术 基本思想: 每次察看句型中相邻的两个符号。通过两个符号 的关系判定出前一个符号是句柄的尾。然后,反 向找出句柄的头。这样我们就找到了一个句柄 S0…S}:1SS+1Sj+2……S:1SS+1…Sn
简单优先分析技术 • 基本思想： – 每次察看句型中相邻的两个符号。通过两个符号 的关系判定出前一个符号是句柄的尾。然后，反 向找出句柄的头。这样我们就找到了一个句柄。 S0…Sj-1SjSj+1Sj+2… …Si-1SiSi+1…Sn U
简单优先分析技术(基本思想续) 我们要通过两个相邻符号SS1之间的关系来找到 句柄: SS1在句柄内:必然有规则U∷=.S;S1 S在句柄内部,但是S1在句柄之后:必然有规 则U:=S1,且存在规范句型.US1 如果S1在句柄内,而S在句柄外,那么必然存 在规范句型..SU.,且U:=S1…
简单优先分析技术(基本思想续） • 我们要通过两个相邻符号SiSi+1之间的关系来找到 句柄： – SiSi+1在句柄内：必然有规则U::=…SiSi+1… – Si在句柄内部，但是Si+1在句柄之后：必然有规 则U::=…Si，且存在规范句型…USi+1…。 – 如果Si+1在句柄内，而Si在句柄外，那么必然存 在规范句型…SiU…，且U::=Si+1…