logo资料库

计++LR（0）类文法的判断及分析表的构造.docx

发布时间：2022-06-08 发布人：admin 分类：说明书 资料大小：0.14M 资料格式：docx 举报 版权申诉
第1页 / 共32页
第2页 / 共32页
第3页 / 共32页
第4页 / 共32页
第5页 / 共32页
第6页 / 共32页
第7页 / 共32页
第8页 / 共32页
资料共32页，剩余部分请下载后查看
    题目： LR（0）类文法的判断及分析表的构造
    系 别： 计算机科学与工程系
    1．引言
    2．开发工具介绍
    2．1面向对象的程序设计语言C++
    2．2 Microsoft Visual C++
    2.2.1 Visual C++特性
    3 . 语法分析原理介绍
    3.1 语法分析简述
    3.1.1 与分析有关的术语简介
    栈
    3.2 LR分析器
    3.2.1. LR分析算法
    3.2.2．LR文法和LR分析方法的特点
    4. 项目需求分析及规划
    4. 1 功能要求
    4. 2 详细设计
    4.2.3 计算文法的项目集：
    5．系统设计和实现
    5.1 代码生成
    5.2 功能测试
    5.2.1 输入文法
    5.2.2生成LR(0)分析表
    6、小结
    致谢
    安徽工程科技学院课程设计用纸 编（学）号：3052104407 安 徽 工 程 科 技 学院 编译原理课程设计（论文） 题目： LR（0）类文法的判断及分析表的构造 系 专 年 别： 计算机科学与工程系 业：计算机科学与技术专业 级： 二零零五级 学生姓名： 代明明 完成时间: 二零零八年六月 第 页
    安徽工程科技学院课程设计用纸 LR（0）类文法的判断及分析表的构造 作者：代明明 学号：3052104407 指导教师：杨丹老师 摘 要 本课程设计主要是介绍 LR（0）文法的判断及分析表的构造，其主要功能是 对任意输入一个文法进行判断是否为 LR（0）文法，若是要对其分析表进 行 构造。构造一个文法的 LR(0)分析表时，首先构造其识别活前缀的自动机 DFA， 这样可以很方便的利用 DFA 的项目集和状态转换函数构造它的 LR(0)分析表，在 实际应用中为了节省存储空间，通常把关于终结符部分的 GOTO 表和 ACTION 表重 叠，也就是把当前状态下面临终结符应作的移进-归约动作和转向动作用同一数 组元素表示 关键字 ：自下而上 语法分析 规约 项目 活前缀 LR 分析 Abstract This course is designed primarily on LR (0) grammar judgement and analysis of the structural form, its main function is to enter a grammar for any to judge whether the LR (0) grammar, if it is necessary to make a structural analysis table. Construct a grammar of the LR (0) analysis table, the first structure of its recognition of automatic machine-prefix DFA, this can easily use the DFA of the project and state-transfer function of its structural LR (0) analysis table, in the practical application In order to save storage space, usually at the end of the on the part of the GOTO ACTION table and table overlap, which is the current state faced at the end should be moved into the - reduction actions and movements to use the same array of elements that. Key Words： Bottom-up Grammar analysis Statute Live prefix Item 第 页 LR analysis
    安徽工程科技学院课程设计用纸 目 录 1. 引言……………………………………………………… 2． 开发工具介绍…………………………………………… 2.1 面向对象的程序设计语言C++特点……………… 2.2 Visual C++特点………………………………… 3. 语法分析器相关原理介绍……………………………… 3.1 语法分析简述……………………………………… 3.2 LR 分析器………………………………………… 4. 项目需求分析及规划……………………………………. 4.1 功能要求……………………………………………. 4.2 总体设计……………………………………………. 4.3 详 细 设 计……………………………………………… 5. 系统设计和实现………………………………………….. 5.1 代码开发……………………………………………. 5.2 功能测试……………………………………………. 6． 结束语………………………………………………. 致谢…………………………………………………………… 参考文献……………………………………………………………… 附录…………………………………………………………………… 第 页
    安徽工程科技学院课程设计用纸 1．引言 LR(k）分析方法是 1965 年 Knuth 提出的，LR 分析的基本思想和当 k<=1 时 LR 的分析器的基本构造原理和方法。LR（0）分析器是分析过程中不需向右查看 输入符号。 本世纪中期，人们在研究使“自然语言”形式化的过程中，提出和发展了 形式语言与自动机理论。由于它与计算机科学中的程序语言有着密切的关系，所 以随着计算机科学的飞速发展，形式语言与自动机理论和方法的研究也越来越受 到人们的重视，但前已成为计算机科学的理论基础。应用领域已扩展到图像处理、 模式识别、自动控制以及生物工程等方面。本文主要研究自动机在编译方面的应 用，并将讨论的重点放在自下而上 LR 分析方法与构造识别文法活前缀的有限状 态自动机上，并用此理论完成 LR(0)语法分析课件的开发工作。 语法分析（简称分析）器在编译器模型中位置如图（1）所示，分析器读取 词法分析器提供的记号流，检查它是否能由源语言的文法产生，输出分析树的某 种表示。另外，我们希望该分析器能以易理解的形式报告任何语法错误，并从错 误中恢复过来，使后面的分析能继续进行下去。 源程序 词 法 分析器 记 号 取下一个记号 分析器 分析树 前端的 其余部分 分析树 符号表 图（1）分析器在编译器模型中的位置 第 页
    安徽工程科技学院课程设计用纸 2．开发工具介绍 2．1 面向对象的程序设计语言 C++ ·C++类中包含私有、公有和保护成员 C++类中可定义三种不同访问控制权限的成员。一种是私有(Private)成员， 只有在类中说明的函数才能访问该类的私有成员，而在该类外的函数不可以访问 私有成员；另一种是公有(Public)成员，类外面也可访问公有成员，成为该类的 接口；还有一种是保护(Protected)成员，这种成员只有该类的派生类可以访问， 其余的在这个类外不能访问。 ·C++中通过发送消息来处理对象 C++中是通过向对象发送消息来处理对象的，每个对象根据所接收到的消息 的性质来决定需要采取的行动，以响应这个消息。响应这些消息是一系列的方法， 方法是在类定义中使用函数来定义的，使用一种类似于函数调用的机制把消息发 送到一个对象上。 ·C++支持继承性 C++中可以允许单继承和多继承。一个类可以根据需要生成派生类。派生类 继承了基类的所有方法，另外派生类自身还可以定义所需要的不包含在父类中的 新方法。一个子类的每个对象包含有从父类那里继承来的数据成员以及自己所特 有的数据成员。 2．2 Microsoft Visual C++ 2.2.1 Visual C++特性 MFC 的本质就是一个包含了许多已经定义好的对象的类库，虽然我们要编写 的程序在功能上是千差万别的，但从本质上来讲，都可以化归为用户界面的设计， 对文件的操作，多媒体的使用，数据库的访问等等一些最主要的方面。在这个类 库中包含了一百多个程序开发过程中最常用到的对象。在进行程序设计的时候， 第 页
    安徽工程科技学院课程设计用纸 如果类库中的某个对象能完成所需要的功能，这时我们只要简单地调用已有对象 的方法就可以了。我们还可以利用面向对象技术中很重要的“继承”方法从类库 中的已有对象派生出我们自己的对象，这时派生出来的对象除了具有类库中的对 象的特性和功能之外，还可以由我们自己根据需要加上所需的特性和方法，产生 一个更专门的，功能更为强大的对象。更可以在程序中创建全新的对象，并根据 需要不断完善对象的功能。 正是由于 Visual C++充分利用了面向对象技术的优点，它使得我们编程时 极少需要关心对象方法的实现细节，同时类库中的各种对象的强大功能足以完成 我们程序中的绝大部分所需功能，这使得应用程序中程序员所需要编写的代码大 为减少，有力地保证了程序的良好的可调试性。 2.2.2 Visual C++主要的开发工具： ·ClassWizard ClassWizard（类向导）是 Visual C++提供的强大的类处理工具。其中的 Message Map(消息映射)选项卡可以让我们添加或删除要处理的 Windows 消息处 理器；Member Variable(成员变量)选项卡为应用程序中的类创建成员变量，并 和控件联系在一起；Class Info（类信息）选项卡显示了应用程序中所包含类的 一般信息，包括定义的头文件和源文件类名，以及与之相关联的基类。并且 Add Class 按钮提供了在工程中创建新类的方法。 ·组件库 组件库允许向工程中插入与定义的类，我们可以通过组件库中的预制组件来 增强应用程序的功能。他们可以是对话框中的简单控件，以可以是 ActiveX 中的 复杂控件。 ·调试器 Visual C++ 中提供的调试器功能非常强大，其中最好的例子是能够提供在线帮 助。在程序调试过程中，常用的有调试器工作栏、指针观察窗口、数据观察窗口 等。 第 页
    安徽工程科技学院课程设计用纸 3 . 语法分析原理介绍 3.1 语法分析简述 3.1.1 与分析有关的术语简介 ·文法 文化 G 定义为一个四元组（VT, VN, S, P），其中： (1) VT 是一个非空有限集合，其元素称为终结符,一般用小写字母表示。 (2) VN 是一个非空有限集合，其元素称为非终结符，一般用大写字母表示， 并有 VT∩VN = 。非终结符定义终结符串的集合，它们用来帮助定义由文法决定 的语言。 S是非终结符，称为识别符或开始符号，它定义的终结符串集就是文法定义 的语言。 ·上下文无关文法 形式上说，一个上下文无关文法 G=（VT, VN, S, P），其中 P 满足： P 中的每一个产生式 a->b 均满足||>=||,仅仅处 S->e 除外。 ·推导 按推导长度进行归纳可以证明，对于文法（1），其句子是由二元算符+和*、 一元算符、括号和运算对象 id 组成的算术表达式。反过来，按算术表达式长度 进行归纳可以证明，这样的算术表达式都可以由此文法产生。于是文法（1）恰 好产生这样的算术表达式集合。 如果在推导过程中出现的句型有两个或多个非终结符，那么就需要决定下一 步推导代换哪个非结符。例如， E   E   (E)   (E + E)   (id + E)   (id + id)（推导 1） 在得到 (E + E)后，可以如下进行：  ( E + E )   (E + id)   (id + id) （推导 2） 第 页
    安徽工程科技学院课程设计用纸 （推导 2）的每个非终结符代换时所用的右部和（推导 1）的一样，但有不同的 代换次序。 每一步都是代换句型中最左边非终结符的推导叫做最左推导。若 是最 左推导，可写成 lm。（推导 1）是最左推导，可以写成 E lm  E lm  (E) lm  (E + E) lm  (id + E) lm  (id + id) 使用前面的约定，每部最左推导可写成 wA lm w的形式，其中 w只含终 结符，A是所用的产生式，是文法的符号串。为了强调最左地推导出，可 写成 * lm  类似地可以定义最右推导，即每步都代换最右边非终结符的推导，用rm表 示。最右推导又叫规范推导。 ·分析树 分析树是推导的图形表示。分析树的每个内部结点由非终结符标记，它的子 结点由该非终结符的这次推导所用产生式的右部各符号从左到右依次标记。分析     E E ( E ) E E+ E   E E (   E E ) E E+ E i 图 2 推导（1）的分析树   E ( E ( E E E ) ) E E+ i E i 树的叶结点由非终结符或终结符标记，所有这些标记从左到右构成一个句型。例 如，表达式(id + id)的最左推导的分析树（包括推导过程中的分析树）如图（2） 所示。 自下而上分析一般称作移进归约分析。编译器常用的移进归约分析方法叫 第 页
    分享到：
    赞 收藏

    相关推荐

    资料库

    课程资源

    共收录17145份资料，累计13个分类，关注成员有19位，主要包括：PHP,网络管理,网页制作,Java,.Net,数据库,3G/移动开发,C/C++,游戏开发,嵌入式,讲义,软件测试,专业指导

    热门标签

    PHP 网络管理 网页制作 Java .Net 数据库 3G/移动开发 C/C++ 游戏开发 嵌入式 讲义 软件测试 专业指导

    最新资料