王涛

（滁州学院 安徽滁州 239000）

编译原理LL(1)语法分析的可视化教学方法

王涛

（滁州学院 安徽滁州 239000）

编译原理是公认的难教难学的课程之一，其主要原因是编译原理要求的知识体系复杂，并且算法抽象。本文的作者针对编译原理课程的特征提出了一种教学观点，即重视对学生的概念教学和形象教学。为了说明形象教学在编译原理教学中的重要性，在本文以LL(1)语法分析为例提出了一种编译原理可视化软件的设计方法，并给了软件实例。教学实践证明，由于可视化教学为学生提供了直观的感性材料，极大的提高了学生理解相关概念并掌握相关算法的能力。

思维模式 LL(1)算法 可视化

编译原理在计算机科学中的地位非常重要，编译原理知识掌握较好的学生在从事编程工作时，往往都具有较好的编程语言运用能力和对新语言的学习能力。在ACM/IEEE-CS发布的CSC2013（Computer Science Curricula 2013）中将编译原理相关的知识体系列入到Programming Language知识体系的核心课程中[1]。

在实际的教学过程中，由于编译原理与汇编语言、计算机组成原理、数据结构、操作系统、高级编程语言等课程的关系紧密，同时对可计算理论、形式语言与自动机等知识有要求，知识体系复杂，是公认的难学、难教的课程[2][3]，探索编译原理如何成功教学的方法一直是该课程教学研究的热点问题。

本文作者结合编译原理的教学特点，提出了一种新的课程教授思路，要点是：一、重视学生的系统思维、逻辑思维和形象思维的锻炼，让学生掌握学好编译原理的方法；二、通过设计并实现一套编译方法教学软件，提供直接、形象的感性材料，在解决较复杂的算法问题的时候，有助于学生思维的顺利进行。

1.掌握大学生的思维规律是教好编译方法的关键

编译原理的课时设置相对于其知识体系来讲一般偏少，以滁州学院计算机科技与技术专业中对编译原理的课程设置来看，其理论课时只有48个学时、实验课时只有16个课时，其它高校的在课时的设置上会有所差异，但最多也只相差10几个课时上下。在如此短的课时中如何让学生实现编译方法课的入门是一个挑战。

第一，在教学中首先要重视概念的教学，思维过程是分析、综合、比较、抽象、概括、判断和推理的过程，首先要形成概念，然后才能判断和推理，使学生真正的理解相关的定理、定义。

因此，在讲授类似的概念时要重点让学生掌握译方法的系统思维、逻辑思维。

第二，要重视形象教学。思维是在感性材料的基础上产生的，感性认识是思维活动的源泉和根据。在编译原理授课时，如果脱离具体形象，特别是在解决比较复杂的问题的时候，由于无法提供直观的鲜明、生动的示例，会妨碍思维的顺利进行。因此，在课程中针对典型的算法要设计要实现一系列可视化的算法程序，让学生亲自参与到算法编写，并通过可视化的手段实现诸如NFA到DFA的转化算法，词法分析相关算法，语法分析的相关算法，语义分析相关算法，目标代码生成相关算法等，通过动画形式让学生理解算法的内涵。

在本文的其余部分，将以LL(1)算法为例说明如何设计编译原理可视化教学模块。

2.LL(1)算法可视化模块的设计

2.1 LL(1)中相关概念的逻辑关系

LL(1)是实现语法分析器的经典算法之一，其本质是按文法的产生式，识别输入符号串是否为一个合法的子句，LL(1)中的第一个L表示从左到右扫描输入串，第二个L表示最左推导,1表示分析时每一步只需向前查看一个符号。目前已经有基于JAVA语言的编译原理可视化软件的报导，考虑到C#语言强大的界面处理功能，本文中的模块基于C#语言设计并开发。

LL(1)的生成过程是一种自上而下的生成树的过程，所谓的与输入串的匹配，即自左向右依次对比生成树的叶子结点与输入串的每一个符号是否吻合，否则，输入串不合法。在进行该算法模块设计的时候要通过可视化算法重点向学生讲授以下内容，

⑴要消除递归性。文法的生成式是有递归性的，如果利用计算机直接实现一个文法结构会存在若干问题，主要表现在可能会存在左递归，使得编译程序陷入死循环。

⑵要消除“回溯”。由于产生式左部会对应多个候选式，编译程序如果无法选择正确的候选式，会让编译程序不停的“回溯”，依次尝试直到找到一个合适的候选式。

⑶消除空符号ε带来的影响。当一个输入符号遇到一个非终结符时，可能会产生ε，如何判断此时为错误、无法进行或者可以继续分析是自上而下分析的另一要注意的内容。

⑷一个文法只有在消除了以上的影响之后，才可以称为LL(1)文法，在此时要向学生讲授LL(1)的详细定义，概念的内涵和外延，并指出，成为了LL(1)文法才使得自上而下语法分析编译算法的编程成为可能。

2.2.模块的设计要点

一般来讲，实现LL(1)算法有两种方法，一种是递归下降分析程序，一种是预测分析程序，本文所述的模块设计采用的是预测分析程序。

（1）可视化算法解决方案的目录结构。编译原理可视化软件采用C#语言和Visio 2010开发完成，在解决方案中添加两个主要项目，分别为ComilerPrinciples和CompilerDLL，前者用于控制算法界面的可视化逻辑，是界面层，后者用于完成算法的处理，是控制逻辑层。两者之间通过函数调用实现交互。

⑵LL(1)可视化算法模块的核心类文件。在LL(1)可视化算法模块中的界面层中的核心类文件是DlgForcastAnalysisTable.cs和LL1_Analysis. cs，分别用于预测分析表和LL(1)算法的可视化。在控制逻辑层中的核心类文件是LL1_Analysis.cs和Model_LL1_StepStatus.cs，分别用于完成LL(1)预测算法的控制逻辑以及分步骤呈现算法的实现过程。

⑶模块的复用。在进行软件设计的时候，尽量的考虑到控制逻辑与界面层的组件复用，例如在LL(1)分析模块中，会复用到词法分析的所有功能，因此通过继承关系和组件化调用尽量的复用现有模块，从而提高编程的效率。

3.基于C#的LL(1)算法可视化模块实例

为了更好说明LL(1)可视化算法的运行过程，以表达式“为例进行分析说明。

3.1.词法分析

如图1所示，首先启动编译原理可视化算法软件，在菜单中调用LL (1)分析模块。在进行语法分析前先完成词法分析，将表达式中的每一个单词符号解析出来，这一步是后续分析的基础，并且词法分析的结果将作为语法分析的输入使用。

图1：词法分析界面示意图

通过此功能可以向学生讲授目前常用的编程环境IDE的工作原理，IDE的核心功能是按所支持的编程言语的格式完成代码的编写。在不考虑编译器的情况下，IDE和普通的文本编译工具是没有区别的，正是由于存在了编译器模块才使得IDE可以将我们输入的文本字符串转换为编译器可以识别的单词符号串。有了这样的认识，首先可以让学生破除对编译原理的神秘感，其次通过亲自动手可以让学生直观的理解符号串的生成以及后续的语法分析的关系[8]。

词法分析器所基于的算法是基于DFA的单词符号识别算法，单词识别完成后的输出结果如表1所示。

表1:单词符号识别结果

3.2.预测分析表生成模块

在LL(1)分析中预测分析表的本质是一个以非终结符和终结符为坐标的二维矩阵，其形如M[A,a]，其中A为非终结符，a为终结符，坐标A和坐标a所对应的元素为一个产生式。

图2:预测分析表界面示意图

本模块的作用是按照一定的文法结构生成矩阵M[A,a]，如图2所示。本模块的构成分为三个部分：

⑴图2的左上方为产生式输入区域，分别输入产生式的左部(head)和产生式的右部(body)，并提供了添加、删除、上移和下移功能。

⑵随着产生式的添加会自动的生成所要分析的文法结构G，如图2右上方所示。

⑶文法结构生成并检查无误后，单击“预测分析表”功能，可以自动生成语法分析程序所需的预测分析表。

预测分析表的生成算法的核心步骤如下：

⑴对文法G中的每一个文法符号X（X为终结符或者非终结符）构造First(X)，并对文法G中的每一个非终结符A构造Follow(A)，构造完成后执行第⑵步。

⑵对文法G的每一个产生式A→a执行第⑶和⑷步。

⑶对每个终结符a∈FFirst(a)，把A→a添加到矩阵M[A,a]。

⑷若ε∈First(a)，则对任何b∈Follow(A)把A→a添加到矩阵M [A,a]。

⑸对所有无定义的矩阵部分标记为错误。

预测分析表生成后，在C#中采用Hashtable数据结构保存矩阵M[A, a]，矩阵的产生式用自定义的数据模型保存，用户自定义模型ModelProduction中只实现Get与Set方法，并以产生式的左部和右部为数据模型，ModelProduction的结构如图3所示。

图3:产生式存储模型ModelProduction

3.3.LL(1)可视化分析过程

预测分析表生成后，基于表1生成的符号串可以完成LL(1)语法分析。由于LL(1)的预测分析程序需要栈作为辅助数据结构，在C#中可以直接使用Stack数据类型完成，并在栈底保存一个字符“#”。Stack的栈顶元素为X，表1中的当前输入符号为a，预测分析的核心步骤为：

⑴若X=a=’#’，则分析结束。

⑵若X=a≠’#’，则X出栈，指向下一人符号。

⑶若X为非终结符则查看分析表M[A,a]。

基于以上分析步骤所实现的分析界面如图4所示。

图4:LL(1)分析界面示意图

在本功能中提供了预测分析表调用功能，用于修正预测分析表，添加了“起始步”、“上一步”、“下一步”、“结束步”等功能，并显示分析过程中每一步的执行状态以及栈的存储状态。

对于抽象的语法分析树则通过树形生成算法利用可视化进行展示，如图5所示，分别给出了第4步、第6步、第8步、第10步、第12步、第16步的语法树形态，学生也可以利用本软件任意查看语法分析过程中每一步的语法树形态，从而对语法树有一个直观的认识，并通过这种直观认识加强对算法的理解[9]。

图5:语法分析过程中每一步的语法树形态

总结

本文针对编译原理的教学特点，提出了一种强调思维锻炼并结合可视化教学软件实现编译方法顺利教学的新观点，思维锻炼是基本，可视化教学软件用于提供感性材料。同时本文中以LL(1)为例阐述了如何设计编译原理可视化教学软件。

[1]The Joint Task Force on Computing Curricula Association for Computing Machinery(ACM)IEEE Computer Society.Computer Science Curricula 2013.

[2]陈文宇.关于 “编译原理”课程教学的思考 [J].实验科学与技术, 2008(12):80-82.

[3]王顺晔.“编译原理”课程教学方法的研究与实践[J].计算机教育，2010(3):36-38.

本文得到滁州学院校级优质课程“编译方法”(项目号2014yzkc07编译方法)项目的资助。