第04章 语法分析——自上而下分析(4).ppt
School of Computer ScienceSchool of Computer Science ZhongyuanZhongyuan University of Technology University of Technology4.5.1 预测分析程序预测分析程序工作过程工作过程 任课教师：孙飞显任课教师：孙飞显编译原理第三章 词法分析预测分析程序提出的背景预测分析程序提出的背景n n递规下降分析程序：递规下降分析程序：递规下降分析程序：递规下降分析程序：是实现是实现是实现是实现LLLL（1 1）文法分析的）文法分析的）文法分析的）文法分析的途径之一。途径之一。途径之一。途径之一。n n递规下降分析器存在的问题：递规下降分析器存在的问题：递规下降分析器存在的问题：递规下降分析器存在的问题：如果用高级语言的如果用高级语言的如果用高级语言的如果用高级语言的递规过程描述递规下降分析器，只有当具有实现递规过程描述递规下降分析器，只有当具有实现递规过程描述递规下降分析器，只有当具有实现递规过程描述递规下降分析器，只有当具有实现这种过程的编译系统时才有实际意义。这种过程的编译系统时才有实际意义。这种过程的编译系统时才有实际意义。这种过程的编译系统时才有实际意义。中原工学院中原工学院 计算机学院计算机学院内容提要内容提要n n预测分析程序的功能预测分析程序的功能n n预测分析表的定义预测分析表的定义n n预测分析程序的总控程序设计算法预测分析程序的总控程序设计算法n n预测分析过程举例预测分析过程举例中原工学院中原工学院 计算机学院计算机学院1、预测分析程序的功能、预测分析程序的功能n n功能：功能：功能：功能：实现实现实现实现LL(1)LL(1)分析的另一种有效途径分析的另一种有效途径分析的另一种有效途径分析的另一种有效途径n n方法：方法：方法：方法：使用预测分析表和堆栈进行联合控制使用预测分析表和堆栈进行联合控制使用预测分析表和堆栈进行联合控制使用预测分析表和堆栈进行联合控制中原工学院中原工学院 计算机学院计算机学院2、预测分析表、预测分析表n n预测分析表预测分析表预测分析表预测分析表是一个是一个是一个是一个MA,aMA,a 形式的矩阵。其中形式的矩阵。其中形式的矩阵。其中形式的矩阵。其中A A为非终为非终为非终为非终结符，结符，结符，结符，a a是终结符或是终结符或是终结符或是终结符或#。n n矩阵元素矩阵元素矩阵元素矩阵元素MA,aMA,a 中存放着一条关于中存放着一条关于中存放着一条关于中存放着一条关于A A的产生式，指出的产生式，指出的产生式，指出的产生式，指出当当当当A A面临输入符号面临输入符号面临输入符号面临输入符号a a时所应采用的候选；时所应采用的候选；时所应采用的候选；时所应采用的候选；MA,aMA,a 中也中也中也中也可能存放一个可能存放一个可能存放一个可能存放一个“出错标志出错标志出错标志出错标志”，指出，指出，指出，指出A A根本不该面临输根本不该面临输根本不该面临输根本不该面临输入符号入符号入符号入符号a a。中原工学院中原工学院 计算机学院计算机学院预测分析表举例预测分析表举例LL(1)文法文法EE+T|TTT*F|F F(E)|iETEE+TE|TFTT*FT|F(E)|i中原工学院中原工学院 计算机学院计算机学院3、预测分析程序的总控程序设计、预测分析程序的总控程序设计n n 栈栈栈栈STACKSTACK的功能的功能的功能的功能n n 栈栈栈栈STACKSTACK的初始化的初始化的初始化的初始化n n 必要的假设必要的假设必要的假设必要的假设中原工学院中原工学院 计算机学院计算机学院栈栈STACK的功能的功能n n当使用当使用当使用当使用预测分析程序预测分析程序预测分析程序预测分析程序对对对对LLLL（1 1）文法进行分析时，）文法进行分析时，）文法进行分析时，）文法进行分析时，要用到两种数据结构：要用到两种数据结构：要用到两种数据结构：要用到两种数据结构：预测分析表：预测分析表：预测分析表：预测分析表：存放产生式存放产生式存放产生式存放产生式栈栈栈栈STACKSTACK：存放文法符号存放文法符号存放文法符号存放文法符号中原工学院中原工学院 计算机学院计算机学院栈栈STACK的初始化的初始化n n当使用当使用当使用当使用预测分析程序预测分析程序预测分析程序预测分析程序对对对对LLLL（1 1）文法进行分析时，）文法进行分析时，）文法进行分析时，）文法进行分析时，要对要对要对要对STACKSTACK进行初始化，方法如下：进行初始化，方法如下：进行初始化，方法如下：进行初始化，方法如下：步骤步骤步骤步骤1 1：栈底放：栈底放：栈底放：栈底放“#”#”；步骤步骤步骤步骤2 2：放入文法开始符号。：放入文法开始符号。：放入文法开始符号。：放入文法开始符号。中原工学院中原工学院 计算机学院计算机学院必要的假设必要的假设n n假设假设假设假设输入串之后总有一个输入串之后总有一个输入串之后总有一个输入串之后总有一个“#”#”n n“#”“#”标志标志标志标志输入串的结束输入串的结束输入串的结束输入串的结束n n该假设该假设该假设该假设与与与与STACKSTACK初始化时栈底的初始化时栈底的初始化时栈底的初始化时栈底的“#”#”相互对应相互对应相互对应相互对应中原工学院中原工学院 计算机学院计算机学院预测分析器模型预测分析器模型n n预测分析程序的总控程预测分析程序的总控程预测分析程序的总控程预测分析程序的总控程序序序序在任何时候都是在任何时候都是在任何时候都是在任何时候都是按按按按STACKSTACK的栈顶符号的栈顶符号的栈顶符号的栈顶符号X X和和和和当前的输入符号当前的输入符号当前的输入符号当前的输入符号a a行事行事行事行事的。的。的。的。预测分析器模型如下右预测分析器模型如下右预测分析器模型如下右预测分析器模型如下右图所示：图所示：图所示：图所示：中原工学院中原工学院 计算机学院计算机学院总控程序的设计思想总控程序的设计思想若若若若X=a=#X=a=#，则分析，则分析，则分析，则分析成功成功成功成功，停止分析过程。停止分析过程。停止分析过程。停止分析过程。若若若若X=a#X=a#，则把，则把，则把，则把X X从从从从STACKSTACK栈顶弹出，让栈顶弹出，让栈顶弹出，让栈顶弹出，让a a指指指指向下一个输入符号。向下一个输入符号。向下一个输入符号。向下一个输入符号。中原工学院中原工学院 计算机学院计算机学院总控程序的设计思想（续）总控程序的设计思想（续）若若若若X X是一个非终结符，则查是一个非终结符，则查是一个非终结符，则查是一个非终结符，则查看分析表看分析表看分析表看分析表MM。若。若。若。若MX,aMX,a 中有中有中有中有X X的产生式，则把的产生式，则把的产生式，则把的产生式，则把X X弹出弹出弹出弹出STACKSTACK，然后把产生式的右然后把产生式的右然后把产生式的右然后把产生式的右部符号串按反序逐一压栈部符号串按反序逐一压栈部符号串按反序逐一压栈部符号串按反序逐一压栈（若右部符号为（若右部符号为（若右部符号为（若右部符号为，则不压，则不压，则不压，则不压栈）；若栈）；若栈）；若栈）；若MX,aMX,a 中存放着中存放着中存放着中存放着“出错标志出错标志出错标志出错标志”，则调用出错诊，则调用出错诊，则调用出错诊，则调用出错诊断程序断程序断程序断程序ERRORERROR。中原工学院中原工学院 计算机学院计算机学院句型句型i*i+i的预测分析过程的预测分析过程步骤步骤符号栈符号栈输入串输入串所用产生式所用产生式0#Ei*i+i#1#ETi*i+i#ETE2#ETFi*i+i#TFTTFT中原工学院中原工学院 计算机学院计算机学院句型句型i*i+i的预测分析过程（续的预测分析过程（续1）步骤步骤符号栈符号栈输入串输入串所用产生式所用产生式345#ETii*i+i#Fi#ET*i+i#ETF*i+i#T*FT中原工学院中原工学院 计算机学院计算机学院句型句型i*i+i的预测分析过程（续的预测分析过程（续2）步骤步骤符号栈符号栈输入串输入串所用产生式所用产生式678#ETF i+i#ETi i+i#Fi#ET +i#中原工学院中原工学院 计算机学院计算机学院句型句型i*i+i的预测分析过程（续的预测分析过程（续3）步骤步骤符号栈符号栈输入串输入串所用产生式所用产生式91011#E +i#T#ET+i#E+TE#ET i#中原工学院中原工学院 计算机学院计算机学院句型句型i*i+i的预测分析过程（续的预测分析过程（续4）步骤步骤符号栈符号栈输入串输入串所用产生式所用产生式121314#ETF i#TFT#ETi i#Fi#ET#中原工学院中原工学院 计算机学院计算机学院句型句型i*i+i的预测分析过程（续的预测分析过程（续5）步骤步骤符号栈符号栈输入串输入串所用产生式所用产生式1516#E#T#E中原工学院中原工学院 计算机学院计算机学院
