LL语法分析构造表的设计--正文

1、编译原理课程设计任务书1、 本课题的目的及意义课程设计实践对学生巩固所学基础专业课程知识、进行编译系统基本技能训练、培养实践动手能力，从而掌握编译系统的基本工作原理、基本方法和基本开发技术，最终达到具有一定的编译系统的实际开发能力有重要意义。通过课程设计，主要达到以下目的：1.帮助学生深入理解编译原理的有关理论和巩固编译原理相关知识。2. 巩固学生学习的编译原理、程序设计语言、数据结构等课程的基础知识，训练学生分析和解决编译系统的相关问题的能力，提高学生的综合素质。3. 从软件工程的角度来看，编译原理课程设计是一个很好的实例，可以训练学生软件设计的能力以及编码调试能力。2、本课题任务的主要内容

2、本课程设计主要内容包括以下几点:1、根据选定的题目，查阅资料，熟悉相关理论、方法；（1）掌握文献检索方法，以获得编译系统开发技术等相关资料；（2）学习并熟练使用一种4GL开发平台（如VC+、Java、Dephi、PB、VB等）；2、分析问题，确定系统逻辑结构；3、确定系统所需模块及模块结构，并用流程图描述各模块；4、编码及调试程序；5、撰写课程设计说明书。3、提交的成果1、一份符合课程设计说明书撰写规范的课程设计说明书。2、一套系统原型。LL(1)语法分析构造器的设计指导教师 王勇 作者 陈慧娟摘 要语法分析的主要任务是接收词法分析程序识别出来的单词符由某种号串，判断它们是否语言的文法产生，即

3、判断被识别的符号串是否为某语法部分。 一般语法分析常用自顶向下方法中的LL（1）分析法，采用种方法时，语法分程序将按自左向右的顺序扫描输入的的符号串，并在此过程中产生一个句子的最左推导，即LL（1）是指自左向右扫描，自左向右分析和匹配输入串。我们使用VC+作为前端开发工具，在分析语法成分时比较方便直观，更便于操作。运行程序的同时不断修正改进程序，直至的到最优源程序。关 键 字 语法分析 文法 自顶向下分析 LL(1)分析 最左推导AbstractGrammatical analysis of the main tasks was to receive lexical analysis proc

4、edure to identify the words from a website, string, and judge whether they have a grammar of the language, that is, judging by the series of symbols to identify whether a grammar part. General syntax analysis commonly used top-down methods of LL analysis, using methods, Grammar hours will be from th

5、e procedures of the order left-to-right scanning input string of symbols, and in the process produced one of the most left the sentence is derived, LL is scanned from left to right, From left to right analysis and matching input strings. After analysis, we use VC + + as a front-end development tool

6、for the analysis of syntax ingredients more convenient visual, more easy to operate. Operational procedures at the same time constantly improving procedures, until the source of optimal. Key WordsGrammatical analysis grammar Top-down analysis LL (1) Analysis Most left Derivation目录引言第1章 概述51.1 编写目的51

7、.2 项目背景51.3 软件定义61.4 开发环境6第2章 需求分析72.1问题陈述72.2功能要求72.3数据流图8第3章 设计任务分工 103.1 小组的任务分工103.2 本人主要工作10第4章 系统设计 114.1总体设计 114.1.1 LL(1)文法改造和源程序预处理114.1.2 LL(1)文法的判别、消除左公因子、消除左递归144.1.3预测分析器的构造 164.1.4构造生成LL(1)语法树184.2详细设计21第5章 运行与测试结果 295.1测试数据295.2界面实现情况29结论与展望30参考文献 31致谢32引言编译器的构造工具是根据用户输入的语言的文法，编译器的构造工

8、具可以生成程序来处理以用户输入的文法书写的文本。随着计算机应用范围的扩大，在软件自动生成，文档处理，特定专业的语言等领域，编译器的构造工具这一技术显得越来越重要。一个编译程序在对某个源程序完成了词法分析工作之后，就进入语法分析阶段，分析检查源程序是否是语法上正确的程序，并生成相应的内部中间表示供下一阶段使用。程序设计语言是一般形式语言的特例，程序语法正确性的检查正是语法句子的识别，语法分析问题也就是句型识别问题。按照识别句子时语法树建立的方式，有自顶向下与自底向上两大类分析技术。本课程设计讨论自顶向下的情况。本次课程设计所做的工作是用VC要建立一个针对LL(1)文法的编译器的编译器。本文既可以

9、以定义好的文法书写的文件作为输入，其中包括语法及语义动作，鉴于输入文件的所用的文法可以用LL(1)分析，于是对输入的文件用递归下降的分析方法在内存中建立它的存储结构，然后分别计算所输入的文法的非终结符号是否可以生成空，每个非终结符号的first集合，每个非终结符号的follow集合，以及每个规则的predict集合，接着判断任意一个非终结符号的任意两个规则的Predict集的交集是不是都为空，如果是则输入文法可以用递归下降法分析，否则不可以，用户应该对所输入的文法作适当的修改，使其满足LL(1)文法分析的要求，。如果所输入的文法可以用递归下降法分析，生成相应文法的语法分析程序。也可以自行添加文

10、法，本课程设计有根据相应文法自动生成分析表和语法树，并将分析信息和结果保存到一个外部文件中的的功能，能灵活实现语法编译器的相应功能。 第1章 概述1.1 编写目的语法分析器通过接受词法分析程序识别出来的单词符号串，判断它们是否由某种语言的文法产生，即判断被识别符号串是否为某语法成分，同时进行语法检查，为后面的语义分析和代码生成作准备。本次课程设计所做的工作是用VC要建立一个针对LL(1)文法的编译器的编译器。本文既可以以定义好的文法书写的文件作为输入，其中包括语法及语义动作，鉴于输入文件的所用的文法可以用LL(1)语法分析，根据相应文法自动生成分析表和语法树，并将分析信息和结果保存到一个外部文

11、件中的的功能，能灵活实现语法编译器的相应功能。1.2 项目背景 编译程序是现代计算机系统的基本组成部分之一，而且多数计算机系统都配有不止一个高级语言的编译程序。由于早期的机器语言、汇编语言编写起来不容易、又枯燥无味，所以开发一种更类似数学定义和自然语言的简洁形式来编写程序的操作，应与任何机器无关的编译器十分重要。编译器的构造工具是根据用户输入的语言的文法，可以生成程序来处理以用户输入的文法书写的文本。随着计算机应用范围的扩大，在软件自动生成，文档处理，特定专业的语言等领域，编译器的构造工具这一技术显得越来越重要。一个编译程序在对某个源程序完成了词法分析工作之后，就进入语法分析阶段，分析检查源程

12、序是否是语法上正确的程序，并生成相应的内部中间表示供下一阶段使用。程序设计语言是一般形式语言的特例，程序语法正确性的检查正是语法句子的识别，语法分析问题也就是句型识别问题。按照识别句子时语法树建立的方式，有自顶向下与自底向上两大类分析技术。本课程设计讨论自顶向下的情况。1.3 软件定义Microsoft visual C+ 6.0:-Visual C+ 6.0是一个功能强大的可视化软件开发工具。自1993年Microsoft公司推出Visual C+1.0后，随着其新版本的不断问世，Visual C+已成为专业程序员进行软件开发的首选工具Visual C+6.0不仅是一个C+编译器，而且是一个

13、基于Windows操作系统的可视化集成开发环境（integrated development environment,IDE）。Visual C+6.0由许多组件组成，包括编辑器、调试器以及程序向导AppWizard、类向导Class Wizard等开发工具。 这些组件通过一个名为Developer Studio的组件集成为和谐的开发环境。Microsoft office Visio 2003：是微软公司出品的一款的软件，它有助于 IT 和商务专业人员轻松地可视化、分析和交流复杂信息。它能够将难以理解的复杂文本和表格转换为一目了然的 Visio 图表。该软件通过创建与数据相关的 Visio 图

14、表（而不使用静态图片）来显示数据，这些图表易于刷新，并能够显著提高生产率。使用 Office Visio 2007 中的各种图表可了解、操作和共享企业内组织系统、资源和流程的有关信息。1.4 开发环境操作系统：Microsoft Windows XP开发平台：Microsoft visual C+ 6.0第2章 需求分析LL(1)分析法中，第一个L的含义是：从左向右的处理输入进行分析，第二个L的含义是：为每个输入串描绘出一个最左推导，1的含义是：向输入串中输入一个符号就可以唯一确定当前将要的产生式。构造出一个LL(1）语法分析器可以更加直观的解决文法输入串在面临不同产生式的选择上，所要进行的分

15、析操作，从而为开发人员带来方便。2.1问题陈述建立一个针对LL(1)文法编译器的自动生成器，要完成此编译器需要对源文件进行两遍处理：第一遍词法分析、第二遍语法分析，语法分析程序应用LL(1)语法分析方法。首先输入(打开)定义好的文法文件，然后建立词法分析器，包括词法分析主程序、扫描部分、关键字表等等。经词法分析后分别计算所输入的文法的每个非终结符号的FIRST集合、每个非终结符号的FOLLOW集合，以及每个规则的SELECT集合，并判断任意一个非终结符号的任意两个规则的SELECT集的交集是不是为空，如果是，则输入文法符号是LL(1)文法，可以进行分析。在对文法的语法进行分析的过程中，要解决各

16、方面的问题如(1)当文法出现做递归时可能使分析过程陷入无限循环、(2)在推导过程中选择哪一右部展开时，如果选择错误，将导致回溯。对文法进行改造，要实现把某些非LL(1)文法到LL(1)文法的等价变换。其总起过程大体包括以下各方面：1、提取左公因子 2、消除左递归。2.2 功能要求设计一个给定LL（1）语法分析器，输入一个句子，能由依据LL（1）分析表输出与句子对应的语法树。能对语法树生成过程进行模拟。动态模拟算法的基本功能是： 1、 词法分析：打开或输入一个文法文件或句子，能对其进行词法分析，显示token表信息，当存在错误时，能给出良好的错误提示。2、 语法分析：打开或输入一个文法文件或句子

17、，能对其进行语法分析，能显示器中间代码信息，当存在错误时，能显示出语法分析错误信息。3、 LL(1)文法判别:打开(输入)一个形如E-abc的LL(1)文法，能对其求出FIRST集，FOLLOW集，并能用直观的关系图显示；4、 预测分析： 打开(输入)一个形如E-abc的LL(1)文法，能直观的形成表达式文法的预测分析表。5、 句子语法树；根据确认LL(1)文法，确认输入串是否为文法的句子，是，则形成该符号串的分析过程，并直观的显示分析过程。6、 该语法分析器具有粘贴、复制、剪切、保存、退出功能！7、 总控程序：显示各模块功能！2.3数据流图：数据流图是结构化分析方法中使用的工具,它以图形的方

18、式描绘数据在系统中流动和处理的过程，由于它只反映系统必须完成的逻辑功能，所以它是一种功能模型。数据流图英文缩写DFD（Data Flow Diagram）它是描绘信息流和数据从输入移动到输出的过程中所经受的变换。 数据流图从数据传递和加工的角度，以图形的方式刻画数据流从输入到输出的移动变换过程。该系统的实现的整个过程的数据流图大体如下：LL(1)语法分析器0层图LL(1)语法分析器1层图：LL(1)语法分析器2层图：第3章 设计任务分工3.1 小组的任务分工本小组的任务是编写一个程序，进行分析表的构造。学号姓名职责主要任务邹纪标组长消除间接左递归，构造分析表 陈春辉组员计算SELECT集，提取

19、左公因子闫瑞雪组员LL(1)文法的判定江於组员计算FIRST集龚玉静组员计算FIRST集陈慧娟组员计算FOLLOW集赵梦组员计算FOLLOW集王报兴组员消除直接左递归3.2 本人主要工作 在这次课程设计中本人的任务是计算FOLLOW集，为后面求SELECT集、判断所给文法是否是LL（1）文法。第四章 系统设计4.1 总体设计4.1.1文法改造和源程序预处理假设条件：（1） 文法G = (N, , P, S) 的产生式规则都取如下的形式：V - w，则称之为上下文无关的，其中 VN ，w(N)* 。N（A|.|Z），N=，SN。（2） 源程序中的注释只支持格式：/注释内容设计相关任务说明：（1）

20、 打开文件（当然也可以手工输入），在窗口中显示文法内容。点击“加载”，选择文件，确定，界面如下。（2）若手工输入，输入文法，则界面如下：1. 保存文法，点击“保存”按钮，输入文件名，确定，即可将文法以一定的格式保存在文件中。2. 在编辑框中输入源程序，点击“Token串”，则对源程序滤掉空格，跳过注释、换行符，变为可被语法分析部分识别的输入串。3. 判断文法是否为上下文无关文法。4. 文法改造部分，去掉形如AA的有害产生式。5. 文法改造部分，去掉不可终止符及其产生式。6. 文法改造部分，去掉不可达符及其产生式。7. 符号表的构造。 4.1.2分析表的构造分析表的构造模块由以下几个部分组成：集

21、合的求解，判断文法是否是LL(1)文法、消除左公共因子及左递归、构造分析表。该模块的结构框图如下：该模块的构造共完成以下任务该部分的功能是判断一个文法是否为LL(1)文法，它通过对输入的文法求解FIRST集、FOLLOW集、SELECT集，最后根据SELECT集是否相交来判断，如果SELECT集相交，测通过提取左公因子，消除左递归看是否可以构成LL(1)文法；如果SELECT集不相交，则该文法是LL(1)文法。消除左公共因子及左递归这部分能够对非LL(1)文法进行改造，使其可能成为LL(1)文法。它先对文法进行判断，看其是否含有左公共因子，若有则消除，若无则不作任何处理，然后再判断文法是否含有

22、直接或间接左递归，若有则消除，若无则不作任何处理。构造分析表通过以上first，follow，select集的求解，判断是否是LL（1），然后通过流程图及算法描述，编写程序构造分析表。4.1.3 LL(1)预测语法分析LL（1）语法分析的模块原理如下：首先初始化栈，#进栈，E进栈作为文法开始的状态。初始化产生式表、非终结符表、终结符表。根据产生式表的产生式生成每个非终结符的FIRST集及FOLLOW集。参考2、3模块，由一个算法生成预测分析表，该预测分析表是由一个二维数组Mn1n2构成。由定理可知：若aSELECT(A ),则把A 放于矩阵MA,a。而这里生成的二维数组Mn1n2与该定理类似。

23、不过这里n1是指A在非终结符表中的序号，n2是指a在终结符表中的序号，而Mn1n2的值是指产生式A 在产生式表中的序号。这样做就为下面的预测分析程序带来了方便。预测分析程序分为检测不合法输入模块和对输入字符串的语法分析模块。对输入字符串的语法分析是通过栈及产生式表和预测分析表的相关联系构建一个算法来对这个字符串进行语法分析。通过算法将栈顶元素与输入字符串的比对、出栈及相关产生式的推导的右部的逆序入栈等操作可完成对输入字符串的语法分析。LL（1）语法预测分析总流程图4.1.4构造生成LL(1)语法树算法思想：本模块的主要功能是将产生式的序列以语法树的方式显示，本组对其进行详细研究后，发现可以将其

24、分成两个模块分别处理。第一个模块是将产生式结构转换成树形的结构进行存储，第二个模块是将以树形结构存储的语法树以树形目录的方式输出。第一个模块，涉及到两个数据结构：产生式的数据结构和树的数据结构。产生式的结构定义存放在Generation.h文件中，在此简述，有两个属性：产生式左部string类型的left和产生式右部vector类型的right。对于传送到本模块的产生式序列，要求它们以vector的形式存放，使用的时候则可以用下标的方式逐个引用。树的结构定义在Tree.h中。整体思想如下：产生式的序列一定是按照最左推导得到的序列，所以树的构造也应按照最左构造，对于如下的简单的语法树 其产生式序

25、列必然为： S-BaFB-ACDA-aC-cD-dF-a如此在构造树的时候必然也要按照如下次序：构造节点S构造S的子节点构造B的子节点构造A的子节点构造C的子节点构造D的子节点构造F的子节点1可设置一个current指向当前节点，最初current指向根节点。2扫描产生式，每次得到一个产生式，将其左部存到current指向的节点，然后申请若干新节点存放产生式右部的符号。3 若右部有非终结符，则将current指向第一个，进行下一次扫描4 若右部没有非终结符，则说明这次推导已到一个子树的树叶。向上回溯，找父节点的相邻非终结符节点，若父节点没有相邻非终结符则继续向上回溯，直到找到为止，并将curr

26、ent指向它，进行下一次扫描。若回溯到根节点则说明树已构造完毕。在构造非终结符节点的时候需要设置该节点的next指针，例如构造A时要设置其next指针指向C，目的是构造完a之后可以寻找下一个要构造的节点，father指针指向B，目的是在构造完D之后可以向上回溯通过B的next指针找到下一个要构造的节点F。对于第二个显示模块，思想如下：1首先current指向根节点，并输出根节点2 输出current的子节点，并将current指向最左的一个非终结符子节点，用递归的思想输出该节点的子树，然后current继续第二个非终结符子节点，并用递归输出其子树。4.2详细设计自顶向下语法分析方法 语法分析方

27、法是编译程序的核心部分。语法分析的作用是识别由词法分析给出的单词符号序列是否是给定文法的正确句子（程序），目前语法分析方法有自顶向下分析和自底向上分析两大类。自顶向下分析包括确定分析和不确定分析，自底向上分析又包括算符优先分析和LR分析这些分析方法各有优缺点。然而除了自顶向下的不确定分析方法外，都是当今编译程序构造的使用方法。 自顶向下的分析也称面向目标的分析方法，也就是从文法的开始符号出发企图推到出一输入的单词串完全像匹配的句子，若输入串是给定文法的句子，则必能退出，反之必然出错。自顶向下的确定分析方法需对文法有一定的限制，但由于实现方法简单、直观，便于手工构造或自动生成语法分析器，因而仍是

28、目前常用的方法之一。确定的自顶向下分析方法，是从文法的开始符号出发，考虑如何根据当前的输入符号（单词符号）唯一地确定选用哪个产生式替换相应非终结符一往下推导，或如何够着一颗相应的语法树。当我们需选用自顶向下分析技术时，首先必须判别所给文法是否是LL（1）文法。因而对任给文法需计算FIRST、FOLLOW、SELECT集合，进而判别文法是否是（）文法。有关已有其他同学详细叙述，在这里就不在赘述。在此详细叙述关于集的定义及有关算法。预测分析方法是自顶向下分析的另一种方法，一个预测分析器是由三个部分组成。预测分析程序先进后出栈预测分析表其中只有预测分析表与文法有关，而分析表有可用一个矩阵（或二维数组

29、）表示。矩阵的元素，中的下表表示非终结符，为终结符或句子括号“”，矩阵元素，中的内容是一条关于的产生式，表明当用非终结符向下推导时，面临输入符时，所应采取的候选产生式，当元素内容物产生式时，则表明用为左部向下推导遇到了不该出现的符号，因此元素内容为转向出错处理的信息。预测分析程序的工作过程用下图表示。图中符号说明如下：“”句子括号集输入串的括号“”文法的开始符号“”存放当前栈顶符号的工作单元“”存放当前输入符号的工作单元开始否是否是否否是X=a ?X=a ?X=# ?结束XVT?上托栈顶符号放入X# S 进栈，当前终结符送a若产生式为Xx1x2xn按逆序即xnx2x1入栈是读入下一符号X=a

30、?是MX,a是产生式吗？否出错出错预测分析程序的框图1.FOLLOW集的定义 设G=（VT，Vn，S，P)是上下文无关文法，AVN，S是开始符号 FOLLOW(A)=a|S* A且aFIRST（），V*T，V+ 若有S* A，且*，则#FOLLOW(A)。其中#作为输入串的结束符，或称输入串括号。2. 计算FOLLOW集(1)根据定义计算 对文法中每一AVT计算FOLLLOW（A） 设S为文法的开始符号，把#加入FOLLOW（S)中（这里“#”为句子括号）。 若AB是一个产生式，则把FIRST（）的非空元素加入FOLLOW（B）中。如果*则把FOLLOW（A)也加入FOLLOW（B）中。 反复

31、使用直到每个非终结符的FOLLOW集不再增大为止。（2） 用关系图法球非终结符的FOLLOW集 文法G中的每一个符号和“#”对应图中的一个结点，对应终结符和“#”的结点用符号本身标记。对应终结符的结点（如ACVT）则用FOLLOW（A)标记。 从开始符号S的FOLLOW（S)结点到“#”号的结点连一条箭弧。 如果文法中有产生式ABX，且*，则从FOLLOW（B)结点到FIRST（X)结点连一条弧，当XVT时，则与X相连。 如果文法中有产生式AB且*则从FOLLOW（）结点到FOLLOW（A)结点连一条弧。对每一FIRST（）结点如果有产生式 AX，且*，则从FIRST（）到FOLLOW（）连一

32、条箭弧。 凡是从FOLLOW（A)结点有路径可以到达的终结符或“#”号的结点，其所标记的终结符或“#”号即为FOLLOW（A)的成员。如文法为 得（）（），（）（）（）FOLLOW(B)FOLLOW(D)FOLLOW(S)FOLLOW(A)FOLLOW(C)FIRST(D)FIRST(B)#ac计算集的关系图3.求解FOLLOW集合的算法 逐一扫描代码中的产生式, 将产生式右部赋给 串,j表示 串中的第j 个字符。 逐一扫描产生式的右部, 若j为非终结符X, 找出j后继的第一个字符k。若k为终结符, 则将该终结符加入到FOLLOW 集合, 结束, 跳出;若k为非终结符, 则FIRST 集合-

33、, 执行。 逐一扫描X 后的字符串,分为下面两种情况:a.若非终结符k能推出空字符串, 则k+, 继续执行、两步;b.若非终结符k为产生式最后一个字符, 则将该产生式的左部非终结符的FOLLOW 集合加入该非终结符的FOLLOW集合。 若扫描完全部的产生式, 则求得所有非终结符的FOLLOW 集合。在计算FOLLOW 集中也存在“ 环”和重复的终结符的问题, 解决的办法与FIRST 集的相同。 计算FOLLOW集的流程图产生式为：Xx1x2xnYk=i+1iVT?YXi=iN0i=n?Y#FOLLOW(X)X=S?NkVN?FOLLOW(X)FOLLOW(Xk)xk+1xk+2xn*YNk*k

34、+kFOLLOW(X)FIRST(k）-FOLLOW（i）结束6、部分代码：void FOLLOW(int i)int j,k,m,n,result=1;char c,temp20;c=non_teri; /*c为待求的非终结符*/temp0=c;temp1=0;merge(fo,temp,1);if(c=start) /*若为开始符号*/temp0=#;temp1=0;merge(followi,temp,1); for(j=0;j=count-1;j+)if(in(c,rightj)=1) /*找一个右部含有c的产生式*/for(k=0;k+)if(rightjk=c)break; /*k

35、为c在该产生式右部的序号*/ for(m=0;m+)if(vm=leftj)break; /*m为产生式左部非终结符在所有符号中的序号*/if(k=strlen(rightj)-1) /*如果c在产生式右部的最后*/if(in(vm,fo)=1)merge(followi,followm,1);continue; if(Fm=0)FOLLOW(m);Fm=1;merge(followi,followm,1);else /*如果c不在产生式右部的最后*/for(n=k+1;n=strlen(rightj)-1;n+)empt0=0;result*=_emp(rightjn);if(result=1) /*如果右部c后面的符号串能推出*/ if(in(vm,fo)=1) /*避免循环递归*/merge(followi,followm,1);continue;i