编译原理课程设计(LR（0)分析表的构造） - 图文

引 言

《编译原理》是计算机专业的一门重要的专业课程，其中包含大量软件设计思想。通过课程设计，实现一些重要的算法，或设计一个完整的编译程序模型，能够进一步加深理解和掌握所学知识，对提高自己的软件设计水平具有十分重要的意义。

语法分析是编译过程的第二阶段，是编译器前端的核心组成部分，在编译系统中起到了至关重要的作用。自底向上的语法分析与自顶向下的语法分析相比，对将要分析的源程序有着更大的分析空间，从而受到了广泛的运用。

LR(0)分析是自底向上LR类语法分析的基础，自底向上语法分析方法是一种移进-规约过程，在当前分析的栈顶符号串形成句柄时就采取规约动作，因此最终目标是如何在分析过程中确定句柄。LR分析法是给出一种能根据当前分析栈中的符号串和向右顺序查看k个符号串就可以唯一地确定分析器动作：是移进还是规约，采用哪条产生式。LR(0)分析器是在分析过程中，不需要向后查看输入串符号，因此它对文法的限制较大。对绝大多数高级语言语法分析器是不适用的，但是它是构造其他LR分析器的基础。

LR(0)最终存在的问题和需要解决的问题是在构造LR(0)分析表的时候，在LR(0)项目集规范族中，有移进项目和规约项目、规约项目和规约项目同时存在的现象，形成移进-规约冲突和规约-规约冲突，直接导致语法分析器无法在某一状态进行移进还是规约。为了能够解决这一问题，我们需要再向后查看一个输入字符（也就是当前字符的FOLLOW集）以确定下一步操作是否能够进行。

我班选择的是老师给的LR(1)语法分析构造器的设计，即对任意给定的文法G构造LR(1)项目集规范族，其中要实现CLOSURE(I)、GO(I,X)、FIRST集合等。在此基础上， 构造了LR（1）分析表。然后对输入的句子进行语法分析，给出接受或出错报告。程序采用文件输入输出方式。其中包括两个输入文件：文法grammar.txt，以及输入串input.txt；两个输出文件：项目集items.txt和文法的LR(1)分析表action_table.txt。由于语法分析的结果只给出接受或错误报告，比较简单。所以直接在屏幕上输出，也便于用户查看。

在具体编写程序过程中，对文法操作的各个功能模块独立成为一个子程序，而对具体输入串的分析则放在main()函数中进行。各个变量及函数的意义和用法我将在叙述程序设计的总体方案中详细给出。

程序的总体算法思想来自《编译原理》课程。具体实现由我独立完成。程序用C/C++语言编写。在Microsoft Visual C++ 2005环境下调试通过。

摘 要

语法分析的主要任务是接收词法分析程序识别出来的单词符由某种号串，判断它们是否语言的文法产生，即判断被识别的符号串是否为某语法部分。 LR分析法是给出一种能根据当前分析栈中的符号串（通常以状态表示）和向右顺序查看输入串的K个（K≥0)）符号就可唯一地确定分析器的动作是移进还是归约和用哪个产生式归约，因而也就能唯一地确定句柄，所以LR分析过程是一种规范归约过程。 经过分析，我们使用C作为前端开发工具，在分析语法成分时比较方便直观，更便于操作。运行程序的同时不断修正改进程序，直至的到最优源程序。

关 键 字

语法分析 文法 LR(1)分析 移进 归约

- 2 -

Abstract

Grammatical analysis of the main tasks was to receive lexical analysis procedure 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. The LR analytic method is gives one kind to be able to act according to current analyzes in stack's string (usually by condition expression) and examined in turn toward right the input string K (K≥0)) the mark may determine only which production pattern selling and buying of real esgate within the same family analyzer's movement is moves to or the selling and buying of real esgate within the same family and uses . Therefore can also determine the handle only, therefore the LR parsing process is one kind of standard selling and buying of real esgate within the same family process. After analysis, we use VC + + as a front-end development tool 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 Words

Grammatical analysis grammar LR (1) Analysis Moves Selling and buying of real esgate within the same family

课程设计任务书

1、本课题的目的及意义

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

2、本课题任务的主要内容

本课程设计主要内容包括以下几点:

1、根据选定的题目，查阅资料，熟悉相关理论、方法；

（1）掌握文献检索方法，以获得编译系统开发技术等相关资料；

（2）学习并熟练使用一种4GL开发平台（如VC++、Java、Dephi、PB、VB等）； 2、分析问题，确定系统逻辑结构；

3、确定系统所需模块及模块结构，并用流程图描述各模块； 4、编码及调试程序；

5、撰写课程设计说明书。

3、提交的成果

1、一份符合课程设计说明书撰写规范的课程设计说明书。 2、一套系统原型。

- 4 -

目 录

第1章 概述……………………………………………………………………6

1.1 项目背景……………………………………………………………6 1.2 编写目的……………………………………………………………7 1.3 软件定义……………………………………………………………7 1.4 开发环境……………………………………………………………7 1.5 编译环境简介………………………………………………………7

第2章需求分析…………………………………………………………………8

2.1 问题陈述……………………………………………………………8 2.2 需完成的功能………………………………………………………8 2.3 数据流图 ………………………………………………………… 9 2.4 数据字典 ……………………………………………………………10

2.4.1 数据项 ……………………………………………………………………10 2.4.2数据结构 ……………………………………………………………………11 2.4.3数据流 ………………………………………………………………………11 2.4.4数据存储 ……………………………………………………………………12 2.4.5处理过程 ……………………………………………………………………12 2.5 E-R图…………………………………………………………………14

第3章逻辑设计…………………………………………………………………15

3.1 系统组织基本工作流程……………………………………………15 3.2 系统设计框图………………………………………………………16

第4章总体设计…………………………………………………………………17

4.1 LR(1) 分析器工作流程图…………………………………………17 4.2 流程简介……………………………………………………………17 4.3 LR(1) 分析思想 ………………………………………………………19 4.4 各模块流程图………………………………………………………20

第5章详细设计…………………………………………………………………22

5.1 正规式构造NFA ……………………………………………………22 5.2 将NFA转化为DFA …………………………………………………24 5.3 把DFA最小化 ………………………………………………………25

第6章 测试……………………………………………………………………26

小结 ………………………………………………………………………………28 致谢 ………………………………………………………………………………29 参考文献 …………………………………………………………………………30

本文来源：https://www.bwwdw.com/article/uchv.html