[第四章自顶向下的语法分析-LL..ppt

* * * * * * * * * * 编译程序原理与实现 张晶 2013.02 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 第四章 自顶向下的语法分析 4.1 自顶向下语法分析概述 4.2 三个重要的集合 4.3 递归下降语法分析方法 4.4 LL(1)语法分析方法 ? ? ? Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 4.4 LL(1)语法分析方法 LL(1)语法分析方法的主要思想 LL(1)文法 LL(1)分析表 LL(1)分析驱动程序 LL(1)分析程序的自动生成器 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. LL(1)方法的主要思想 LL的含义是从左到右扫描输入串，采用最左推导分析句子。 数字1表示分析句子时需向前看一个输入符号。 LL(1)方法和递归下降法属于同一级别的自顶向下分析法(分析条件相同)。 G = (VT, VN, S, P) 对任意 A? VN, 对A的任意两条产生式, Predict(A ? ?1)? Predict(A ? ?2) = ? Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. LL(1)方法的主要思想 采用LL(1)分析表记录每个产生式的预测符 采用LL(1)分析驱动程序控制分析过程 采用符号栈记录需要推导的句型 (A, a) (a, a) (b, a) ( ，#) Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. LL(1)分析机制 符号栈 输入流 a LL(1)驱动程序： ? 栈为空情形的处理 ? X? VT情形的处理 ? X? VN情形的处理 X LL[1]分析表 符号栈：保存LL(1)分析的中间结果，当输入流和符号栈同时为空，则接受否则拒绝输入串 LL(1)分析表：T(A,a),指引选择哪条产生式 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 4.4 LL(1)语法分析方法 LL(1)语法分析方法的主要思想 LL(1)文法 LL(1)分析表 LL(1)分析驱动程序 LL(1)分析程序的自动生成器 ? Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. LL(1) 文法 如果一个 CFG G 满足下面的条件，则称 G 是一个 LL(1) 文法 G = (VT, VN, S, P) 对任意 A? VN, 对 A的任意两条产生式, Predict(A ? ?1) ? Predict(A ? ?2) = ? LL(1) 文法的特性 无二义性 无左递归 对于一个非终极符来讲,最多只有一个空产生式 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 4.4 LL(1)语法分析方法 LL(1)语法分析方法的主要思想 LL(1)文法 LL(1)分析表 LL(1)分析驱动程序 LL(1)分析程序的自动生成器 ? ? Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.