没有合适的资源?快使用搜索试试~ 我知道了~
首页编译原理课程设计-LR(1)语法分析模拟构造器的设计
编译原理课程设计-LR(1)语法分析模拟构造器的设计
5星 · 超过95%的资源 需积分: 10 48 下载量 157 浏览量
更新于2023-03-16
评论 3
收藏 596KB DOC 举报
语法分析的主要任务是接收词法分析程序识别出来的单词符由某种号串,判断它们是否语言的文法产生,即判断被识别的符号串是否为某语法部分。 LR(k)分析法是给出一种能根据当前分析栈中的符号串,“k”是指为了作出分析决定而向前看的输入符号的个数。据栈中的符号串和向右顺序查看输入串的k(k³0)个符号,就能唯一确定分析器的动作是移进还是归约,以及用哪个产生式进行归约。其中LR(0)分析器是在分析过程中不需要向右查看输入符号的,因而它对文法的限制较大,但是它是构造LR类分析器的基础。对于是否是LR(0)文法,可以通过查看是否存在两类冲突来判定,而需要的是判定功能,所以用项目集作为模块的输入。
资源详情
资源评论
资源推荐
引 言
语法分析是编译程序的核心部分,在编译系统中起到了至关重要的作用。
语法分析的作用是识别由词法分析给出的单词符号序列是否是给定文法的正确
句子,目前语法分析常用的方法有自顶向下分析和自底向上分析两类。本次课
程设计我们要完成的是 LR(1)分析器模拟构造器的设计,LR 分析属于自底向
上分析。
LR 分析法正是给出一种根据当前分析栈中的符号串和向右顺序查看输入串
的 k 个符号就可唯一地确定分析器的动作是移进还是规约和用哪个产生式规约 ,
因而也就能唯一的确定句柄。LR(0)分析器是在分析过程中,不需要向后查看
输入串符号,因此它对文法的限制较大,对绝大多数高级语言语法分析器是不
适用的,但是它是构造其他 LR 分析器的基础。
LR(0)最终存在的问题和需要解决的问题是在构造 LR(0)分析表的时候,在
LR(0)项目集规范族中,有移进项目和规约项目、规约项目和规约项目同时存
在的现象,形成移进-规约冲突和规约-规约冲突,直接导致语法分析器无法在
某一状态进行移进还是规约,所以对于 LR(0)文法需要判定。为了能够解决这
一问题,出现了 SLR(1)和 LR(1)。
本次课程设计需要分工合作,而我需要完成的部分是对 LR(0)文法的判定
功能。对于 LR(0)文法的判定就是要检查在一个文法的 LR(0)项目集规范是否
存在移进-规约,或规约-规约冲突。
LR(1)语法分析模拟构造器的设计
摘 要
语法分析的主要任务是接收词法分析程序识别出来的单词符由某种号串,
判断它们是否语言的文法产生,即判断被识别的符号串是否为某语法部分。
LR(k)分析法是给出一种能根据当前分析栈中的符号串,“k”是指为了作出分
析决定而向前看的输入符号的个数。据栈中的符号串和向右顺序查看输入串的
k(k³0)个符号,就能唯一确定分析器的动作是移进还是归约,以及用哪个产生
式进行归约。其中 LR(0)分析器是在分析过程中不需要向右查看输入符号的,
因而它对文法的限制较大,但是它是构造 LR 类分析器的基础。对于是否是
LR(0)文法,可以通过查看是否存在两类冲突来判定,而需要的是判定功能,所
以用项目集作为模块的输入。
关 键 字
LR 分析器;语法分析器;编译原理;文法判定
Abstract
The main task of parsing is a lexical analysis program to receive recognition at
the word from the string by a number to determine whether they have a language
grammar, namely, the symbols to be identified to determine whether the string part of
a grammar.
LR (k) analysis is given a stack can be analyzed in light of the current string of
symbols, "k" refers to an analysis of the decision to look to the future the number of
input symbols. According to the stack and the symbol string input strings to the right
view of the order k (k>= 0) symbols, we can only determine the analyzer is moved
into the action or reduction, as well as with which to reduce production. One LR (0)
analyzer in the analysis do not need to enter the symbol to the right view and therefore
the restrictions of its grammar, but it is the structural basis of LR-type parser. Whether
it is LR (0) grammar, you can see if there is to determine the types of conflict, and the
need is determined, so as to use itemsets input module.
Key Words
LR parser Parser Compiler Principles Grammar determine
目 录
引 言.....................................................................................................................................................I
摘 要...................................................................................................................................................II
第 1 章 概述........................................................................................................................................1
1.1 项目背景...............................................................................................................................1
1.2 编写目的...............................................................................................................................1
1.3 软件定义...............................................................................................................................1
1.4 开发环境...............................................................................................................................2
1.4.1 Visual C++简介..........................................................................................................2
1.4.2 MFC............................................................................................................................2
第 2 章 需求分析................................................................................................................................3
2.1 问题陈述...............................................................................................................................3
2.2 LR 分析器工作原理简介.....................................................................................................3
2.3 需完成的功能.......................................................................................................................4
2.4 数据流图...............................................................................................................................5
2.4.1 LR(1)分析器构造及输入串分析流程......................................................................5
2.4.2 求项目集规范族流程................................................................................................6
2.4.3 分析表构造流程........................................................................................................7
2.4.4 总控程序流程............................................................................................................8
2.5 数据字典表达.......................................................................................................................8
2.5.1 数据项........................................................................................................................8
2.5.2 数据结构....................................................................................................................9
2.5.3 数据流........................................................................................................................9
2.5.4 数据存储..................................................................................................................11
2.5.5 处理过程..................................................................................................................11
第 3 章 逻辑设计..............................................................................................................................14
3.1 系统基本工作流程.............................................................................................................14
3.2 系统设计模块框图.............................................................................................................15
第 4 章 总体设计..............................................................................................................................16
4.1 主要模块原理介绍.............................................................................................................16
4.1.1 LR(1)项目集族构造................................................................................................16
4.1.2 LR(1)分析表构造....................................................................................................16
4.1.3 LR(0)文法判定........................................................................................................17
4.2 主要模块算法思想.............................................................................................................17
4.2.1 相关数据结构..........................................................................................................17
4.2.2 项目集求闭包..........................................................................................................18
4.2.3 LR(0)判定模块........................................................................................................18
4.2.4 总控程序..................................................................................................................19
4.3 LR(0)文法判定流程图及核心代码...................................................................................20
4.3.1 流程图......................................................................................................................20
4.3.2 LR(0)文法判定源程序............................................................................................20
第 5 章 详细设计..............................................................................................................................23
5.1 LR(0)文法判定模块界面设计...........................................................................................23
5.2 LR(0)文法判定模块调试...................................................................................................27
6.1 系统实现情况.....................................................................................................................29
6.2 个人收获.............................................................................................................................29
参 考 文 献........................................................................................................................................31
附 录..................................................................................................................................................32
第 1 章 概述
1.1 项目背景
LR 分析器是一种由下而上的上下文无关语法分析器。LR 意指由左至右处
理输入字串,并以最右边优先衍生的推导顺序建构语法树。能以此方式分析的
语法称为 LR 语法。LR(K)分析方法是 1965 年 Knuth 提出的,括号中的 k 表示
向右看输入串符号的个数。这种方法比起自顶向下的 LL(k)分析方法和自底向上
的优先分析方法的限制要少的多,也就是说多余大多数用无二义性上下文无关
文法描述的语言都可以用相应的 LR 分析器进行识别,而且这种方法还具有分
析速度快,能准确、即时地指出出错位置。它的主要缺点是对于一个实用语言
文法的分析器的构造工作量相当大, k 愈大构造愈复杂,实现比较困难。因此,
目前许多实用语言的编译器程序,当采用 LR 分析器都是借助美国 Bell 实验室
推出的“一个编译器的编译器——YACC”来实现的。它能接受一个用 BNF 描述
的满足 LR 类中 LALR(1)的上下文无关文法并对其自动构造出 LALR (1)分析器。
通过编译原理课程一个学期的学习与探讨,现已基本了解文法分析的过程
和实现步骤。但是我们对于在课本中的知识的应用相当缺乏。学校安排了本次
课程设计对于我们更好的掌握和理解书本的知识有重要实践意义。
1.2 编写目的
课程设计实践对巩固所学基础专业课程知识、培养实践动手能力,从而掌
握编译系统的基本工作原理、基本方法和基本开发技术有重要意义。通过课程
设计,主要达到以下目的:
1. 帮助我们深入理解编译原理的有关理论和算法。
2. 巩固学习的编译原理、数据结构等课程的基础知识,对知识的回顾和掌
握有积极作用。
3. 从软件工程的角度来看,本次课程设计实行了分工合作,提高我们团队
合作的精神。
1.3 软件定义
对给定文法能够自动构造该文法的语法分析器,并且能够对输入串进行判
断是否为该文法的句子。
剩余36页未读,继续阅读
hugolcc
- 粉丝: 219
- 资源: 14
上传资源 快速赚钱
- 我的内容管理 收起
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
会员权益专享
最新资源
- ExcelVBA中的Range和Cells用法说明.pdf
- 基于单片机的电梯控制模型设计.doc
- 主成分分析和因子分析.pptx
- 共享笔记服务系统论文.doc
- 基于数据治理体系的数据中台实践分享.pptx
- 变压器的铭牌和额定值.pptx
- 计算机网络课程设计报告--用winsock设计Ping应用程序.doc
- 高电压技术课件:第03章 液体和固体介质的电气特性.pdf
- Oracle商务智能精华介绍.pptx
- 基于单片机的输液滴速控制系统设计文档.doc
- dw考试题 5套.pdf
- 学生档案管理系统详细设计说明书.doc
- 操作系统PPT课件.pptx
- 智慧路边停车管理系统方案.pptx
- 【企业内控系列】企业内部控制之人力资源管理控制(17页).doc
- 温度传感器分类与特点.pptx
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功
评论2