文档介绍：温故知新温故知新上下文无关文法上下文无关文法自上而下自上而下自下而上自下而上LL(1)LL(1)文法文法22个函数个函数递归下降递归下降预测分析预测分析非递归的非递归的预测分析预测分析最左推导最左推导最右推导最右推导!LRLR文法文法输输入入LRLR分析程序分析程序输输出出栈栈LRLR分析器的模型分析器的模型actionactiongotogotossmmXXmmssmm-1-1XXmm-1-1……ss00……aa11aaii……aann$$移进移进--规约分析规约分析规约规约移进移进--规约冲突规约冲突规约规约--规约冲突规约冲突句柄句柄活前缀活前缀右句型的前缀,右句型的前缀,该前缀不超过最该前缀不超过最右句柄的右端右句柄的右端11。句柄与某个产生式的右部。句柄与某个产生式的右部符号串相同符号串相同22。句柄是句型的一个子串。句柄是句型的一个子串33。把句柄归约成非终结符代。把句柄归约成非终结符代表了最右推导逆过程的表了最右推导逆过程的一步一步简单的简单的LRLR方法(方法(SLRSLR))规范的规范的LRLR方法方法向前看的向前看的LRLR方法方法(LALR(LALR))1/411/ 构造构造SLRSLR分析表分析表LR(0)LR(0)项目项目(简称(简称项目项目))在右部的某个地方加点的产生式在右部的某个地方加点的产生式例:例:AA??XYZXYZ对应有四个项目对应有四个项目A A ??··XYZXYZA A ??XX··YZYZA A ??XYXY··ZZA A ??XYZXYZ··例:例:AA????只有一个项目和它对应只有一个项目和它对应A A ??··点的左边代表历史信点的左边代表历史信息,右边代表展望信息。息,右边代表展望信息。直观地讲,项目表示在直观地讲,项目表示在分析过程的某一阶段,分析过程的某一阶段,已经看到了产生式的多已经看到了产生式的多大部分,以及希望看到大部分,以及希望看到的部分。的部分。. . 拓广文法拓广文法E E ????EEE E ??E E + + T T || T TT T ??T T ** F F | | FFF F ??( ( E E ) | id) | id当且仅当分析器当且仅当分析器使用使用E E ????EE规约规约时,宣告分析成时,宣告分析成功功E E ??rmrmE+TE+T??rmrmE+F E+F ??rmrmE+idE+id??rmrmT+idT+id??rmrmF+idF+id??rmrmid+idid+idid + idid + idF + id F + id T+idT+idE+idE+idE+F E+F E+TE+. 2. 构造构造LR(0)LR(0)项目集规范族项目集规范族II00::E E ????··EE5/415/41闭包函数闭包函数closure(Iclosure(I))11、、II的每个项目均加入的每个项目均加入closure(Iclosure(I))22、如果、如果AA??αα··BBββ在在closure(Iclosure(I))中,中,且且BB??γγ是产生式,那么如果项目是产生式,那么如果项目BB??··γγ还不在还不在closure(Iclosure(I))中的话,那中的话,那么把它加入。么把它加入。E E ????EEE E ??E E + + T T || T TT T ??T T ** F F | | FF F F ??( ( E E ) | id) | idE E ??··E E + + T T E E ??··TTT T ??··T T ** F F T T ??··FFF F ??··(E)(E)F F ??··. 2. 构造构造LR(0)LR(0)项目集规范族项目集规范族II00::E E ????··EE((核心项目核心项目))E E ??··E E + + T T E E ??··TT((非核心项目,非核心项目,T T ??··T T **FF通过对核心项目求闭包通过对核心项目求闭包T T ??··FF而获得)而获得)F F ??··((EE))F F ??··ididE