一个编译原理语法分析器的实现与设计
摘 要
编译程序一般由词法分析程序、语法分析程序、语义分析程序、中间代码生成程序、目标代码生成程序、代码优化程序、表格管理程序和出错处理程序等成分构成。在编译原理的教学过程中，算法的讲解都需要对算法进行详细的分析，包括算法条件的判断，文法分析表的构造过程，文法分析表的具体生成，针对文法的句子的分析过程等，这些过程往往需要占用大量时间来分析、制表等。本软件的主要任务就是利用程序来完成算法的上述相关过程，以达到高效，直观的效果。本文旨在介绍语法分析方法中的一种自上而下的分析方法——LL(1)分析法。所谓LL(1)分析法是指语法分析是按自左至右的顺序向前查看一个输入字符串，并分析过程中产生句子的最左推导。
关键词：编译；语法分析；LL(1)算法；演示目 录
1引言 1
1.1项目背景 1
1.2目标 1
1.3名词解释 1
1.4算法简介 2
1.4.1自顶向下分析 2
1.4.2 递归子程序 3
1.4.3 LL（K）分析方法 4
1.4.4 LL（1）分析方法 4
1.4.5LL(1)分析表 5
2 系统流程图 6
2.1程序流程图 6
2.2 系统模块流程图 7
3 系统实施 7
3.1文件读取模块 8
3.1.1文件读取使用的CommonDialog控件介绍 8
3.1.2文法左递归的判断 9
3.2算法分析模块 9
3.2.1求select集 9
3.2.2求first集 10
3.2.3求follow集 10
3.3分析表构造模块 12
3.3.1构造文法分析表 12
3.3.2A::=aβ规则 13
3.3.3A::=Dβ规则 13
3.3.4A::=ε规则 13
3.4句子分析模块 13
3.4.1读取句子 14
3.4.2分析句子 14
4 特殊问题及解决方法 14
4.1 Select集的求解 15
4.1.1 问题描述 15
4.1.2 解决方案 15
4.1.3 解决结果 15
4.2为ListBox添加水平滚动条 15
4.2.1 问题描述 15
4.2.2 解决方案 15
4.2.3 解决结果 16
5 结果测试 16
5.1测试正确文法 16
5.2测试错误文法 19
结 论 20
参考文献 20
致 谢 21
声 明 22
1.1项目背景
编译原理是计算机专业中最难的一门课程,在理论上它要求学生掌握有关形势语言和自动机的抽象概念,在技术上要求学生能够熟练地利用各种数据结构进行编程。
编译程序是现代计算机系统的基本组成部分之一。编译程序一般由词法分析程序、语法分析程序、语义分析程序、中间代码生成程序、目标代码生成程序、代码优化程序、表格管理程序和出错处理程序等成分构成。
在编译原理的教学过程中，语法和语义分析阶段关于算法的讲解都需要对算法进行详细的分析，包括算法条件的判断，文法分析表的构造过程，文法分析表的具体生成，针对文法的句子的分析过程等。这些过程往往需要占用大量时间来分析、制表等。教学主要是对这些过程的讲解和分析，没有必要花这么多的时间来做这些工作。本软件的主要任务就是利用程序来完成算法的上述相关过程，节约教学时间。
1.2目标
《一个编译原理语法分析器的设计与实现》
1.主要通过文本方式获取相关文法，并实现以下相关操作：
2.判断文法是否符合LL（1）的要求
3.获取文法的终结符和非终结符
4.求文法的select集（其中包括first集和follow集的求解）并判断select集是否符合LL（1）算法的要求
5.根据文法和select集构造文法分析表
6.根据文法分析表判断输入的句子是否符合文法
1.3名词解释
语法分析：逐一分析词法分析所得的属性字，检查其中的语法错误，如果没有发现语法错误， 则给出正确的语法结构。
句子的分析：句子的分析实际就是分析源程序中的语句是否符合给定的文法。
文法：对语言结构的定义和描述，即在形式上用于描述和规定语言结构。由若干条规则组成。
规则：为一个二元组，通常格式为U：：=x或U→x；其中U为规则的左部，是一个符号；x是规则的右部，是一贯有穷字符串。规则又称为产生式。
BNF表示法：即巴科斯范式表示法，它引进了符号“|”，符号“|”表示“或”。运用符号“|”把相同左部的规则缩写在一起，这样显得文法更为紧凑。
文法G[Z]：规则的非空有穷集合，其中Z为文法的识别符号或开始符号，它至少要在一条规则的左部出现。
字汇表：在文法中，由全部规则的左部和右部中的所有符号组成的符号集。
非终结符：文法中出现在规则左部的符号，它们组成的集合称为非终结符集。
终结符：文法中凡不属于非终结符集的符号，它们组成的集合称为终结符集。
递归：同一操作或一组操作的连续重复，其实质上是处理过程的性质，在这种过程的每一步都要用到它自身的上一步或上几步的结果。
递归定义：在定义某种事物时又用到其本身。
直接左递归规则：型如U：：=Uy的规则称为直接左递归规则。
First集：首符号集。
Follow集：向前看集。
Select集：可选集。
LL（1）文法：对于文法G（S），其每个非终结符的不同规则具有不相交的Select集，则称该文法为LL（1）文法。
