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

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

编译原理是计算机专业中最难的一门课程,在理论上它要求学生掌握有关形势语言和自动机的抽象概念,在技术上要求学生能够熟练地利用各种数据结构进行编程。
编译程序是现代计算机系统的基本组成部分之一。编译程序一般由词法分析程序、语法分析程序、语义分析程序、中间代码生成程序、目标代码生成程序、代码优化程序、表格管理程序和出错处理程序等成分构成。
在编译原理的教学过程中，语法和语义分析阶段关于算法的讲解都需要对算法进行详细的分析，包括算法条件的判断，文法分析表的构造过程，文法分析表的具体生成，针对文法的句子的分析过程等。这些过程往往需要占用大量时间来分析、制表等。教学主要是对这些过程的讲解和分析，没有必要花这么多的时间来做这些工作。本软件的主要任务就是利用程序来完成算法的上述相关过程，节约教学时间。(毕业设计网 )

《一个编译原理语法分析器的设计与实现》
主要分为四个模块：
1．文件读取模块
文件读取模块主要完成将记事本中的待分析文法读入到内存中的功能。其中包括了对可能出现的文法BNF表示法的判断以及对文法中是否存在直接左递归规则的判断。 [资料来源：http://THINK58.com]
2．算法分析模块
算法分析模块是《一个编译原理语法分析器的设计与实现》
中的关键模块。本模块包含了LL（1）算法中的大部分重要数据和信息，其中包括获取输入文法的终结符集和非终结符集，对文法中每一条规则求select集（select集的求解又包括求first集或者follow集），以及对select集合法性的判断，即同一非终结符所对应的不同规则的select集中不能有相同的终结符。
3．分析表构造模块
分析表构造模块的主要功能是将算法分析模块所求解出的符合LL（1）算法规则的文法的select集转化成文法分析表，以便下一模块的调用。
4．句子分析模块
句子分析模块是整个《一个编译原理语法分析器的设计与实现》的主体演示模块，包括句子读取、句子合法性判断、句子分析等部分。其中句子合法性的判断又分为句子中是否有文法终结符以外的符号和句子是否符合文法规则的判断。下面将对以上四个模块的具体实现技术、数据结构及关键程序片段进行详细的说明。

[版权所有：http://think58.com]

 
目  录
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 [资料来源：http://think58.com]
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 [资料来源：http://www.THINK58.com]

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