自下而上分析方法-算符优先,LR(0),SLR,LR(1),LALR大全

2023-11-19

自下而上分析法

自下而上分析方法:从输入串开始,逐步进行规约,直至文法的开始符号。是指根据文法的产生式规则,把产生式的右部替换成左部符号

因此自上而下分析法的核心问题为识别可规约串

一、规范规约

相关定义

短语

G是一个文法,S是文法的开始符号,假定 α \alpha α β \beta β δ \delta δ是文法G的一个句型,如果有在这里插入图片描述在这里插入图片描述
则称 β \beta β是句型 α \alpha α β \beta β δ \delta δ相对于非终结符A的短语。

直接短语

如果有A⇒ β \beta β,则称 β \beta β是句型 α \alpha α β \beta β δ \delta δ相对于规则A→ β \beta β的直接短语。

句柄

一个句型的最左直接短语称为该句型的句柄。

素短语

这样一个短语,至少含有一个终结符,并且,除自身之外不再含任何更小的素短语。

最左素短语

处于句型最左边的素短语

语法树表示

在一个句型对应的语法树中,以某非终结符为根的一颗子树的所有叶子自左至右排列起来形成一个相对于子树根的短语。
仅有父子两代的一棵子树,它的所有叶子自左至右排列起来所形成的符号串为直接短语
语法树中最左那棵只有父子两代的子树的所有叶子的自左至右排列形成的字符串为句柄

示例

在这里插入图片描述

规范规约

在这里插入图片描述
如图所示,将修建语法树的过程倒过来,即得到S⇒aAcBe⇒aAcde⇒aAbcde⇒abbcde,这显然是一个最右推导,规范规约是关于一个最右推导的逆过程。

二、语法分析器

在这里插入图片描述
我们将输入串一一移入至栈中,当栈内形成可规约串时,就进行规约。这种规约可能出现多次,一直归约直至栈顶不再出现可规约串。然后,我们继续向栈内移入符号,直至输入串仅剩 # ,栈内内容变为 #S

在上述过程中,分析器共产生4中动作:

  1. 移进:读入下一个输入符号并把它下推进栈。
  2. 规约:当栈顶符号串形成一个可归约的串(如:句柄)时,直接进行归约,即用产生式左侧的非终结符替换栈顶的句柄。
  3. 接受:当栈底只有“#”和开始符号,而输入也已经到达右端标志符号“#”时,识别出符号串是句子,执行该动作,表示分析成功,是归约的一种特殊情况。
  4. 出错:栈顶的内容与输入符号相悖,即当识别程序发现输入符号串不是句子时,进行出错处理。

在移进规约过程中,可能会出现移进-归约冲突归约-归约冲突,不同的分析方法有不同的处理冲突的技术。

三、算符优先分析算法

在这里插入图片描述
在这里插入图片描述
我们首先对终结符a与b的优先关系进行定义:
在这里插入图片描述

算符文法

在这里插入图片描述
在这里插入图片描述

1. 算符优先文法

在这里插入图片描述

2. FIRSTVT( P )和LASTVT( P ):

(1) FIRSTVT( P )

在这里插入图片描述
在这里插入图片描述

(2) LASTVT( P )

在这里插入图片描述
在这里插入图片描述
此外,算符优先文法句型扩在两个#之间,形如#E#,因此
在这里插入图片描述

2. 构建优先关系表

  1. 在这里插入图片描述
  2. 在这里插入图片描述
    在这里插入图片描述

3. 示例

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

在这里插入图片描述

算符优先分析算法

在这里插入图片描述

在这里插入图片描述
注:算符优先分析只关心句型中自左向右的终结符序列的优先关系,不涉及终结符之间可能存在的非终结符,因此可以认为这些非终结符是同一个符号。

示例

在这里插入图片描述
在这里插入图片描述

三. LR分析法

在这里插入图片描述
优点:能用LL(1)分析法分析的所有文法都能使用LR分析法来进行分析。
LR分析法在自左至右扫描输入串的过程中能发现其中的任何错误,并能准确指出出错位置。
缺点:手工构造分析表工作量太大,需使用自动生成器。

LR分析法通过求句柄逐步归约进行语法分析。其中句柄是通过求活前缀而求得。

活前缀

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

我们通过下图过程,可以得到:

LR分析器

在这里插入图片描述

在这里插入图片描述

1.分析表

分析表(分析函数):不同的文法分析表不同,同一个文法采用的LR分析器不同时,分析表也不同,分析表又可分为动作(ACTION)表状态转换(GOTO)表两个部分,它们都可用二维数组表示。

ACTION[s,a]:当状态s面临输入符号a时,应采取什么动作。
每一项ACTION[s,a]所规定的四种动作:

  1. 移进 把(s,a)的下一状态s’和输入符号a推进栈,下一输入符号变成现行输入符号。
  2. 归约 指用某产生式A→ β \beta β进行归约. 假若 β \beta β的长度为r, 归约动作是: 去除栈顶r个项,使状态sm-r变成栈顶状态,然后把(sm-r, A)的下一状态s’=GOTO[sm-r, A]和文法符号A推进栈。
  3. 接受 宣布分析成功,停止分析器工作。
  4. 报错

GOTO[s,X]:状态s面对文法符号X时,下一状态是什么。
对于如下分析表:
在这里插入图片描述
Si:把当前输入符号移进栈,第i个状态进状态栈。
ri:按第i个产生式进行规约。
i:第i个状态进栈。

对于一个文法,如果能够构造一张分析表,使得它的每个入口均是唯一确定的,则这个文法就称为LR文法。
一个文法,如果能用一个每步顶多向前检查k个输入符号的LR分析器进行分析,则这个文法就称为LR(k)文法。

2.通过自动机识别活前缀

对于一个文法G,我们可以构造一个有限自动机,它能识别G的所有活前缀。
由于产生式右部的符号就是句柄,若这些符号串都已进栈,则表示它已处于“归态活前缀”,若只有部分进栈,则表示它处于“非归态活前缀”。要想知道活前缀有多大部分进栈了,可以为每个产生式构造一个自动机,由它的状态来记住这些情况,此“状态”称为“项目”。这些自动机的全体就是识别所有活前缀的有限自动机。
在这里插入图片描述
在这里插入图片描述
构成识别一个文法活前缀的DFA的项目集(状态)的全体称为文法的LR(0)项目集规范族。

由于以下结论,我们可以构建一个项目闭包,避免需要将NFA确定化。
在这里插入图片描述

LR(0)项目集规范族的构造

在这里插入图片描述

在这里插入图片描述

3.LR(0)分析法

LR(0)分析表的构造

在这里插入图片描述
在这里插入图片描述

示例

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

4.SLR分析法

当发生移进-规约冲突时,如果出现以下情况:
在这里插入图片描述
在这里插入图片描述

构建分析表

在这里插入图片描述
按上述方法构造出的ACTION与GOTO表如果不含多重入口,则称该文法为SLR(1)文法。
使用SLR表的分析器叫做一个SLR分析器。
每个SLR(1)文法都是无二义的。但也存在许多无二义文法不是SLR(1)的。

示例

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

5.LR(1)文法

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

项目闭包的构建

在这里插入图片描述

分析表

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

示例

在这里插入图片描述
在这里插入图片描述

在这里插入图片描述在这里插入图片描述

6.LALR(1)文法

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

分析表

在这里插入图片描述
在这里插入图片描述

示例

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)

自下而上分析方法-算符优先,LR(0),SLR,LR(1),LALR大全 的相关文章

  • 编译原理三大经典书籍(龙书 虎书 鲸书)

    1 龙书 Dragon book 英文名 Compilers Principles Techniques and Tools 作者 Alfred V Aho Ravi Sethi Jeffrey D Ullman 中文名 编译原理技术和工具
  • 控制流分析之循环

    最近做科研碰到了如何识别程序热对象的问题 解决这个问题的一般思路是做静态分析 主要是分支概率和基本块频率的分析 目前 LLVM 里已经添加了这两种分析 然而 直接看相关的代码效率很低 主要原因是缺乏控制流分析方面的基础 导致代码中出现的许多
  • 编译原理第七章笔记 -- 中间代码生成

    本文中内容整理西安交通大学软件学院吴晓军老师的ppt中 仅供学习使用 请勿转载或他用 参考教材 程序设计语言 编译原理 第3版 陈火旺等 国防工业出版社 这一章分数在35左右 两个大题 数组的引用四元式生成 控制语句当中布尔表达式的翻译 考
  • C++实现的利用LR(1)分析表对赋值表达式进行语法制导翻译生成四元式及汇编代码

    赋值语句的语法制导翻译 后续已完善算术运算文法 赋值文法 布尔运算文法 if while do while和复合语句文法 编译器项目已上传GitHub https github com sleep jyx compiler 一 需要的语义过
  • 合工大 编译原理 实验

    目前仅有实验一二三四 Windows桌面应用程序项目 开发语言 c 开发环境 Visual Studio 实验一 GitHub 实验二 传送门 实验三 传送门 实验四 传送门 实验一大致功能 支持程序运行时输入关键词 支持已保存关键词的表格
  • 编译原理实验 实验二 LL(1)分析法 Python实现

    1 实验目的 通过完成预测分析法的语法分析程序 了解预测分析法和递归子程序法的区别和联系 使学生了解语法分析的功能 掌握语法分析程序设计的原理和构造方法 训练学生掌握开发应用程序的基本方法 有利于提高学生的专业素质 为培养适应社会多方面需要
  • 编译原理------词法分析器C/C++代码实现

    一 实验目的 设计 编制并调试一个词法分析程序 加深对词法分析原理的理解 二 实验内容 2 1 待分析的简单的词法 1 关键字 begin if then while do end 所有的关键字都是小写 2 运算符和界符 lt lt lt
  • 用 Rust 编写一个简单的词法分析器

    词法分析是编译器和解释器的第一个环节 相对而言也比较简单 词法分析器 有时也称为单元生成器 tokenizer 或者扫描器 scanner 将源代码转换为词法单元 这个过程称为词法分析 本文代码设计复刻自 用Go语言自制解释器 词法分析器一
  • 语义分析- C-- 语言

    C V1 0 E gt n true false E E E E 类型合法的程序 3 4 false true 类型不合法的程序 3 true true false 对这个语言 语义分析的任务是 对给定的一个表达式e 写一个函数type c
  • (二):C++求解文法的First集和Follow集

    功能及代码结构 为实现编译器前端 需要对文法进行分析 该部分实现从文件中读入文法 方便修改 用合适的数据结构表示并求解各个非终结符号的First集和Follow集 仓库 https github com xs1317 Complier 文件
  • LLVM里的寄存器分配 - 准备工作(一)

    1 背景介绍 本文档是基于 LLVM 的寄存器分配系列科研笔记第一篇 以一个 C 语言程序为主干介绍 LLVM 在寄存器分配前做的一些主要工作 分析在寄存器分配前期可能的写操作来源 并记录了我在研究 LLVM 后端中 SSA 形式的中间表示
  • 编译原理基础知识+笔记(1)

    一 编译原理概述 1 翻译程序 把某一种语言程序 称为源语言程序 等价地转换成另一种语言程序 称为目标语言程序 的程序 2 编译程序 把某一种高级语言程序等价地转换成另一种低级语言程序 如汇编语言或机器语言程序 的程序 又分为 诊断编译程序
  • 编译原理 CS-143(更新至week4)

    编译原理 CS 143 Pre Course Survey Navigation Your Course 01 01 Introduction 8m20s 01 02 Structure of a Compiler 13m53s 编译器结构
  • 编译原理实验二:Bison

    编译原理实验二 Bison 实验要求 1 了解Bision基础知识 如何将文法产生式转换为Bison语句 2 阅读 src common SyntaxTree c 对应头文件 include SyntaxTree h 理解分析树生成的过程
  • OCaml 安装以及简单的加减乘除Demo(以Ubuntu16.04为例)

    安装nix 参考 https mirrors tuna tsinghua edu cn help nix 安装nix sh lt curl https mirrors tuna tsinghua edu cn nix latest inst
  • 递归下降算法语法分析c语言

    递归下降算法 自上而下文法的递归下降的预测分析 从根节点出发逐步构造分析树 所以被称作自上而下文法 在文法中有递归的函数 例如 E gt TE 所以叫做递归下降算法 使用的文法如下 E gt TE E gt TE e T gt FT T g
  • 【Python】代码实现LL(1),LR(1)上下文无关文法(Stack()类)

    任务要求 针对书上第三章中的表达式文法 采用LL 1 LR 1 进行分析 相关文法 需要进行消除左递归等操作 顺手分享一下课本资源好了 可能不是最新版 排版略有点别扭 后文的书上内容就是指这本书 编译原理 陈意云 文字版 提取码 e0ag
  • 编译原理(4)LR(0)语法分析程序设计(Python实现)

    1 实验要求 1 已知文法G S 0 S E 1 E aA 2 E bB 3 A cA 4 A d 5 B cB 6 B d 手工建立文法G S 的LR 0 的项目集规范族DFA和LR 0 分析表 2 根据清华大学版 编译原理 第3版 教材
  • Compiler- volatile关键字

    为了直观的感受编译器为程序所做的编译优化 我们通过以下的C 程序来进行演示 只能体现编译优化的一小部分hh 请大家预测一下下面代码的输出结果 include
  • 自下而上分析方法-算符优先,LR(0),SLR,LR(1),LALR大全

    文章目录 自下而上分析法 一 规范规约 相关定义 短语 直接短语 句柄 素短语 最左素短语 语法树表示 示例 规范规约 二 语法分析器 三 算符优先分析算法 算符文法 1 算符优先文法 2 FIRSTVT P 和LASTVT P 1 FIR

随机推荐

  • CentOS 7 关闭网络限制

    1 安装CentOS 7 3操作系统mini版本即可 2 设置关闭Selinux 编辑 etc selinux config vi etc selinux config SELINUX disabled 重启机器 查看selinux状态 s
  • C++中的namespace

    namespace中文意思是命名空间或者叫名字空间 传统的C 只有一个全局的namespace 但是由于现在的程序的规模越来越大 程序的分工越来越细 全局作用域变得越来越拥挤 每个人都可能使用相同的名字来实现不同的库 于是程序员在合并程序的
  • 手撕计算机网络——应用层(四):P2P

    前言 进入应用层学习也有了一段时间了 接下来的这篇文章中小荔枝会将应用层P2P结构体系于我们客户 端系统体系在分发文件中的机理进行整理 希望今天能结束应用层学习哈哈哈 运输层我来啦 目录 前言 一 P2P的自拓展性 二 BitTorrent
  • 【高德地图API】从零开始学高德JS API(八)——地址解析与逆地址解析

    摘要 无论是百度LBS开放平台 还是高德LBS开放平台 其调用量最高的接口 必然是定位 其次就是地址解析了 又称为地理编码 地址解析 就是将地址转换为经纬度 而逆地址解析 就是将经纬度转换为地址 经纬度一般是由专业测绘机构用GPS采集 然后
  • Shell——脚本执行命令和控制语句

    前言 在正常情况下 shell按顺序执行每一条语句 直至碰到文件尾 if选择结构示例 if后面紧跟判断条件 then后面是执行语句 fi是结束标志 多重if结构示例 case多选结构 通常用于在一系列模式中匹配某个变量的值 命令 只在cas
  • CH7-查找

    文章目录 1 查找的基本概念 2 线性表的查找 2 1 顺序查找 线性查找 算法2 1 0 类型定义 算法2 1 1 顺序查找 算法2 1 2 改进后的顺序查找 性能分析 2 2 折半查找 二分或对分查找 算法2 2 1 非递归算法 算法2
  • 基于容器PaaS云技术平台方案

    本文以容器技术建设 PaaS 平台即服务 云平台的解决方案为例 分析其如何实现系统资源的集中管理 动态分配 监控 共享和调度 如何实现应用的统一部署和业务连续性保障 实现多数据中心的高可用 推动系统架构及流程的调整 应对云计算时代所带来的变
  • 分析研究<<一战到底>>节目规则演变

    分析研究 lt lt 一战到底 gt gt 节目规则演变 一 研究范围 江苏卫视2012年3月2日推出益智答题类节目 研究时间截止 2014年1月4日星期六 二 规则演变 1 初始规则 2012年3月2日规则 1 每期参加节目的有11人 分
  • 01-ZooKeeper快速入门

    1 Zookeeper概念 Zookeeper是Apache Hadoop项目下的一个子项目 是一个树形目录服务 zookeeper翻译过来就是 动物园管理员 它是用来管理Hadoop 大象 Hive 蜜蜂 Pig 小猪 的管理员 简称ZK
  • C语言程序设计 现代方法(第2版)电子书pdf下载

    C语言程序设计 现代方法 第2版 下载链接 https pan baidu com s 1XIKYGAxGhRTscgibAj3kgQ 提取码获取方式 关注下面微信公众号 回复关键字 1129
  • 关于猜数字游戏以及关机指令

    这几天学习到了一些没有接触过的东西 因此在这里记录下 首先是猜数字游戏 这个小程序特别简单 只要知道相关的几个关键函数就能明白 它的主要函数有rand 返回随机数 以及srand 用来设置随机数的起点 以及time 代码如下 include
  • 【QTUM量子链中国区】零撸180元攻略

    QTUM量子链中国区 于2020年1月7日正式上线 实名认证 无需上传 通过后赠送体验矿机一台 周期30天 总产量10QTUM 价值130元 进入官方QQ群可以目测到 这个新出的项目非常火爆 问题是 QTUM量子链中国区和著名的QTUM量子
  • ABAP 参照TR创建副本TR并释放

    简介 一般项目中为了后期传输的统一性 都会采用传输副本请求的方式来避免出现一个需求有过多的工作台TR的情况 但是常规的创建副本请求的方式不是很便捷 因此本文介绍一种参照已有TR创建副本TR的样例 效果 代码 Report YSTMS
  • Ljavax/validation/ParameterNameProvider

    利用宝塔部署项目war包出现 Ljavax validation ParameterNameProvider 的错误 初始化org springframework validation beanvalidation OptionalVali
  • day08-Linux自有服务&软件包管理

    自有服务 即不需要用户独立去安装的软件的服务 而是当系统安装好之后就可以直接使用的服务 内置 学习目标 1 了解systemctl命令用途 2 掌握使用systemctl开启 关闭 重启服务 3 了解常见自有服务ntpd firewalld
  • Linux基础学习

    安装gcc 1 apt get命令是debain Linux发新版的APT软件包管理工具 dabian ubuntu deepin等Linux系统通过以下命令 安装gcc Shell输入sudo apt get install gcc命令
  • 4--一元多项式的乘法与加法运算

    个人题解 include
  • JS判断数组中是否有重复的元素

    function isRepeatId arr arr 100 200 400 200 if arr length 1 若元素数为1一定不重复 直接返回 return false var hash for let i in arr 遍历ar
  • C语言的面向对象的封装方法

    1 3 1 变长结构体的实现 以上文数据结构C语言 双向链表及其实现的双向环链为例 具体封装方法如下 在上述双向环链中节点中不可避免地引入了数据指针 void data占用了8byte的空间 那么能不能在链表每个节点中省去这8byte的空间
  • 自下而上分析方法-算符优先,LR(0),SLR,LR(1),LALR大全

    文章目录 自下而上分析法 一 规范规约 相关定义 短语 直接短语 句柄 素短语 最左素短语 语法树表示 示例 规范规约 二 语法分析器 三 算符优先分析算法 算符文法 1 算符优先文法 2 FIRSTVT P 和LASTVT P 1 FIR