113基于VB的一个编译原理语法分析器的实现与设计

一个编译原理语法分析器的实现与设计
摘  要
编译程序一般由词法分析程序、语法分析程序、语义分析程序、中间代码生成程序、目标代码生成程序、代码优化程序、表格管理程序和出错处理程序等成分构成。在编译原理的教学过程中，算法的讲解都需要对算法进行详细的分析，包括算法条件的判断，文法分析表的构造过程，文法分析表的具体生成，针对文法的句子的分析过程等，这些过程往往需要占用大量时间来分析、制表等。本软件的主要任务就是利用程序来完成算法的上述相关过程，以达到高效，直观的效果。本文旨在介绍语法分析方法中的一种自上而下的分析方法——LL(1)分析法。所谓LL(1)分析法是指语法分析是按自左至右的顺序向前查看一个输入字符串，并分析过程中产生句子的最左推导。 [资料来源：THINK58.com]

关键词：编译；语法分析；LL(1)算法；演示
 
The Design and Implementation of A Syntax Analyzer based on Compilation Theory
 Abstract
The compiler generally is made up of the lexical analyzer program, the syntax analysis program, the semantics analysis program, the inter-language production procedure, the goal code production procedure, the code optimization procedure, the form executive program and the procedure of disposing mistakes. In the teaching process of compiler principle, all algorithm explanation needs to be explain clearly, including algorithm condition judgment, grammar analytical table structure process, grammar analytical table concrete production, in view of grammar sentence analysis process and so on. These processes often take much time to analyze, the scheduling and so on. This program mainly work is to complete the algorithm which take advantage of the procedure to deal with those above mentioned processes , in order to save time. The paper aims at introducing a syntax analytical method named LL(1) algorithm which from the up to down. The syntax analyzer analyzes the character string beginning from the left to right one word each time and educes the most left deduction of the sentence in the analyze course..

Key words: compiler; grammar analysis; LL(1) algorithm; demonstrate
 
目  录
论文总页数：22页
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 [资料来源：THINK58.com]
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项目背景
编译原理是计算机专业中最难的一门课程,在理论上它要求学生掌握有关形势语言和自动机的抽象概念,在技术上要求学生能够熟练地利用各种数据结构进行编程。
编译程序是现代计算机系统的基本组成部分之一。编译程序一般由词法分析程序、语法分析程序、语义分析程序、中间代码生成程序、目标代码生成程序、代码优化程序、表格管理程序和出错处理程序等成分构成。
在编译原理的教学过程中，语法和语义分析阶段关于算法的讲解都需要对算法进行详细的分析，包括算法条件的判断，文法分析表的构造过程，文法分析表的具体生成，针对文法的句子的分析过程等。这些过程往往需要占用大量时间来分析、制表等。教学主要是对这些过程的讲解和分析，没有必要花这么多的时间来做这些工作。本软件的主要任务就是利用程序来完成算法的上述相关过程，节约教学时间。

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）文法。
1.4算法简介
1.4.1自顶向下分析
对于文法G[Z]，给顶一个待分析的句子(字符串)，自顶向下分析的基本思想是从识别符号Z开始，根据文法试着建立一个推导序列，若得到所给的句子，则句子得到识别，表明其结构符合文法，如果经过各种推导都不能得到所分析的句子，则该符号串不符合文法。或者说，从根结点出发，自上而下地建立一颗语法树，其未端结点按从左到右的顺序连接起来，构成给定的符号串，则符号串得到识别。 [资料来源：http://think58.com]
例：设有文法G[N]和符号串25                            N         
N::=D|ND
D::=0|1|2|…|9                                          
根据文法有：
NÞNDÞDDÞ2DÞ25；                                       
因此我们说25符合此文法                             

[资料来源：http://think58.com]

                                                                                                                     图1 G[N]过程分析  [资料来源：http://THINK58.com]

                                                                                            
自顶向下分析的难点及解决办法：
1.自顶向下分析的难点
  [资料来源：http://www.THINK58.com]