基本方法(续) 规约中的动作有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…