编译原理:代替LR的MP:2.遇到的问题

用指针加速

MP是multi-pass,多遍分析法,它是从“先乘除后加减”中得来的灵感。在实践中,发现C语言优先级有15级,如果将源代码处理15遍,每一遍都从头开始找,势必很慢。所以,有了用指针加速的想法。

例如,给所有乘除号的指针排列起来,所有加减号的指针排列在它下面。这是在词法分析那一遍完成的。然后,处理乘除法的那一遍,可以直接找到乘除号,处理加减法时,能够直接找到加减号。不用再从头开始找了,有提速效果。

树的结构

要想实现“用指针加速”的想法,需要用指针指向树上的节点,并且还能在树上移动。用C++的vector实现树状结构恐怕不行,它需要一个指针指向父节点,再来一个下标说明是第几个子节点。

希望只用一个指针描述节点,这么一来,要用C语言实现树状结构了。树上的每个节点,包括一个字符串,和4个指针,分别指向父节点(上)、兄弟节点(左右)、长子节点(下)。其中“长子”是个新的概念,是子节点中最左边的一个。

重叠的产生式

在实践中遇到了“重叠的”产生式,即两个产生式,有公共的部分,又不完全一样。如:

A->*E
B->E*E
或
E->id
E->id=E

星号E,表示C语言的指针操作,可星号同时也是乘号,并且,前者的优先级更高。如果先把所有*E归约为A,再遇到乘法时,看到的就是EA,这就错了。

第二个例子,先把id归约为E,然后发现id=id变成了E=E,这导致不能识别id=E。

用FIRST集和LAST集解决上述问题。比较*EE*E,左侧多出一个E,应该求LAST(E),当判断*E时,看到星号左边的符号属于LAST(E),则不做归约。LAST集的求法,在《编译原理》书中没有说,但是它和FIRST集差不多,对称的。

比较id和id=E,右侧多出=E,求FIRST(=E),结果是等于号。在尝试把id归约为E时,看一看右边是不是等于号,如果是,就不归约。

修正

解决上述产生式重叠问题的另一个方法,是“修正”。对于产生式A->*E,修改为Ax->*E,这么一来,在之后的某一遍中,遇到EAx就知道应该“修正”为E*E

Ax是一个新的文法符号,并且它的子节点正是星号和E。修正时,检查一下子节点,更安全。

突破

在这里插入图片描述
图中的语言是一串a,很简单,但是,它的文法产生式却如此复杂。有时,我觉得chomsky的四型文法是个陷阱,至少也是个坑,许多人都掉进去了。

在MP分析法中,使用函数来处理树状结构,而基于纯文法的语法分析,只使用“替换”。不管是推导还是归约,都是替换。用左边的替换右边的,或者用右边的替换左边的。用函数则更灵活。

图中的语言,用函数来识别,可以是这样:

/a+/ =~ s
n=strlen(s)
n=2^i, i=1,2,3...

如此说来,MP分析法超越了上下文无关文法,更强。

前进的动力

下图中,成功实现了一个源代码的分析,这给了我动力。在这里插入图片描述
一开始,是一个只有根节点,没有任何子节点的树,它的内容是源代码。

经过词法分析,出现了一棵略微复杂一点的树。

之后的一步步,形成了完整的语法树。

注意,这个例子中,总是针对根节点进行分析的。在添加了括号之后,用数数的方法进行括号的配对,这需要对某个子节点进行分析。引入递归的函数,可以完成括号的分析。
a(bcd(efg)h)ijk
括号配对的结果是
a(.)ijk
bcd(efg)h
把指针p指向点号,第二行做它的子节点。调用分析函数f(p)。由于在子节点中还有括号,所以会出现函数f的递归调用。

总结

MP分析法可以代替LR分析法,并且还能有所超越。这是一个有希望的研究方向。发明LR分析法的Knuth先生还健在,它看到MP分析法之后,会怎么想呢?

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/723993.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

开发者配置项、开发者选项自定义

devOptions.vue源码 <!-- 开发者选项 &#xff08;CtrlAltShiftD&#xff09;--> <template><div :class"$options.name" v-if"visible"><el-dialog:custom-class"sg-el-dialog":append-to-body"true":close-on…

发力采销,京东的“用户关系学”

作者 | 曾响铃 文 | 响铃说 40多岁打扮精致的城市女性&#xff0c;在西藏那曲的偏远农村&#xff0c;坐着藏民的摩托车&#xff0c;行驶在悬崖边的烂泥路上&#xff0c;只因为受顾客的“委托”&#xff0c;要寻找最原生态的藏区某款产品。 30多岁的憨厚中年男性&#xff0c;…

【吊打面试官系列-Mysql面试题】SQL 语言包括哪几部分?每部分都有哪些操作关键字?

大家好&#xff0c;我是锋哥。今天分享关于 【SQL 语言包括哪几部分&#xff1f;每部分都有哪些操作关键字&#xff1f;】面试题&#xff0c;希望对大家有帮助&#xff1b; SQL 语言包括哪几部分&#xff1f;每部分都有哪些操作关键字&#xff1f; SQL 语言包括数据定义(DDL)、…

[创业之路-117] :制造业企业的必备管理神器-ERP-是什么?企业经营管理与EPR的主要功能模块与全流程

目录 一、什么是EPR 1.1 跨企业的供应链思想 1.2 EPR的概念&#xff1a;企业资源管理计划 1.2.1 助力企业管理各种资源&#xff1a;人、财、物&#xff08;机、料、法、环&#xff09; 1.2.2 助力企业有效管理 1.2.3 效率的提升 1.4 应用领域 二、ERP的功能模块 三、E…

ROS2学习笔记三:话题Service

目录 前言 1 话题简介 2 常用指令 3 RCLCPP实现实现话题 3.1 创建工作空间 3.2 代码编写 3.2.1 发布端编写 3.2.2 发布端编写 前言 Service是ROS 2提供的一种通信机制&#xff0c;用于在不同节点之间进行请求和响应。 Service允许一个节点向另一个节点发送请求&#…

CSS实现文字上下滚动、间歇滚动和无限滚动

目录 1、连续滚动2、间歇性向上滚动3、任意个数向上滚动 本文主要记录了如何实现文字上下滚动效果&#xff0c;实现主要就是用到了css3的两个属性&#xff1a; framekeys和 animation 1、连续滚动 <div class"scroll-continuous"><div class"content…

计算机专业毕设-在线商城系统

1 项目介绍 在线商城系统&#xff0c;后端java语言&#xff0c;springboot&#xff0c;SSM框架。前端thymeleaf&#xff0c;前后端不分离。本项目已经隐去作者信息&#xff0c;所有代码文件均没有创建人和创建时间&#xff0c;可以放心使用。 系统用户分为两类&#xff0c;管理…

Shopee菲律宾本土店允许中途无理由退货,如何应对退货后库存混乱问题?

Shopee菲律宾本土店最近实施了一项新政策&#xff0c;自2024年6月10日起&#xff0c;允许买家在商品仍在运输途中申请退货与退款&#xff0c;此即“在途退货/退款”功能&#xff0c;主要的目的是为了提升买家的购物体验&#xff0c;增强市场竞争力。 图源&#xff1a;Shopee菲律…

关于Panabit在资产平台中类型划分问题

现场同事问了一个问题&#xff1a;Panabit能不能当做CentOS接入&#xff1f; 我第一反应是&#xff1a;Panabit是个什么鬼&#xff1f;为啥要混编接入&#xff1f;后期维护都是事啊。所以&#xff0c;我就想回答&#xff1a;不能&#xff01; 但是&#xff0c;最好要给出一个…

立讯精密:“果链一哥”怎么摆脱依赖症

AI手机创新赋能&#xff0c;隔岸苹果股价走出历史新高&#xff0c;消费电子有望迎来复苏&#xff1f; 这里我们聊聊苹果产业链代工龙头——立讯精密 作为早早入场的代工企业&#xff0c;立讯精密曾经吃足“果链”红利&#xff0c;如今摆在它面前的是增长、毛利、安全等难题。 …

Linux-PXE批量安装

一、部署 PXE 远程安装服务 在大规模的 Linux 应用环境中&#xff0c;如 Web 群集、分布式计算等&#xff0c;服务器往往并不配备光驱设备&#xff0c;在这种情况下&#xff0c;如何为数十乃至上百台服务器裸机快速安装系统呢&#xff1f;传统的 USB光驱、移动硬盘等安装方法显…

深度解析“科技信贷”:构建科技支行的五维模型

科技信贷是指金融机构为支持科技创新、技术改造和设备更新等领域提供的专项信贷服务&#xff0c;旨在促进科技企业的发展和技术的进步。科技信贷在推动科技企业和创新项目发展方面具有重要作用&#xff0c;其特点在于提供定制化的金融支持&#xff0c;以满足科技创新链条中的融…

【C语言】扫雷游戏

Hi~&#xff01;这里是奋斗的小羊&#xff0c;很荣幸您能阅读我的文章&#xff0c;诚请评论指点&#xff0c;欢迎欢迎 ~~ &#x1f4a5;&#x1f4a5;个人主页&#xff1a;奋斗的小羊 &#x1f4a5;&#x1f4a5;所属专栏&#xff1a;C语言 &#x1f680;本系列文章为个人学习…

深信服科技:2023网络钓鱼趋势分析报告

随着互联网的快速发展和广泛应用&#xff0c;网络钓鱼活动带来的安全隐患愈演愈烈。因应威胁发展&#xff0c;我 们编撰了此份分析报告&#xff0c;旨在全面了解其发展态势&#xff0c;并提醒相关部门、企业和公众加强防范。 在本报告中&#xff0c;我们将详细梳理网络钓鱼的近…

成都爱尔周进院长提醒毕业生摘镜,术式如何挑

高考完迎来一个悠长假期&#xff0c;考后放松的同时&#xff0c;也有不少同学开始“准备”。 为奔赴梦想&#xff0c;为了理想的专业和学校&#xff0c;不少人决定摘镜。 不少专业有视力要求&#xff0c;且不同专业方向的要求各有不同。我们先来看看有视力要求的专业有哪些&am…

macOS聚集搜索功能开启与关闭

按下command空格弹出 使用搜索 关闭搜索 sudo mdutil -a -i off 启用搜索 sudo mdutil -a -i on

GLib库对核心应用的支持

代码&#xff1a; /** main.c** Created on: 2024-6-19* Author: root*/#include <glib.h> // 包含GLib函数库 static GMutex *mutex NULL; static gboolean t1_end FALSE; // 用于结束线程1的标志 static gboolean t2_end FALSE; // 用于结束线程…

最新版首发 | 手把手教你安装 Vivado2024.1(附安装包)

Q&#xff1a;Vivado出2024版了&#xff01;不知迪普微有没有对应的安装包呢&#xff1f; A&#xff1a;有的&#xff01;回复“Vivado2024.1”即可获得相应安装包哦~ Q&#xff1a;好哒~但是我不会安装&#xff0c;可否安排一期安装教程&#xff1f; A&#xff1a;立马安排&…

网抑云特殊版,登录即永久

前言 今天分享一款特殊版本的音乐软件&#xff0c;相信大家在听网抑云的时候会有两大烦恼&#xff0c; 一是歌曲需要开通VIP才可以收听&#xff0c;不管怎么说也是国内厂商普遍操作 但是第二种烦恼你万万想不到的是&#xff0c;开通了会员后&#xff0c;惊奇的发现&#xff…

数据结构---二叉树的性质总结

第i层上的节点数 证明: 二叉树的最大节点数 证明: 第一层对应2^0个节点, 累加得到 这是一个等比数列 求和公式: 那么这里的n指的是一共有多少个相加 根据从b到a一共有b-a1个可推出 有(k-1)-01个相加 那么结果为: 叶节点与度为2的节点关系 证明: 假设二叉树的总节点数为 NNN…