编译原理LL(1)文法之提取左公因子,消除左递归

2023-11-17

在判断LL(1)文法是否符合的时候,需要判断LL(1)文法是否存在左公因子,和左递归的情况,以下给出相应的判断方法以及通过提取左公因子和消除左递归使非LL(1)文法转换为LL(1)法的方法

 

第一种情况:存在左公因子  ;解决方法:提取左公因子;

 

若文法中存在形如:

A->ay|ab   两个产生式左部第一个符号相同,则不符合LL(1)文法,指代不明,则表示存在左公因子

 

解决方法:

转换成 A->aM1,aM2,aM3....的形式:

得:

A->aM

M->y|b

则成功提取左公因子;

 

 

第二种情况:存在左递归;

 

左递归有两种类型:

(1)直接左递归 :

A->AB, A∈Vn,B属于V*

(2)间接左递归

A->Bb

B->Aa

A,B∈Vn,a,b属于V*

 

(这里第二种情况注意,因为是左递归,所以看得就是第一个字符,一定要跟这个类型一样的A->B.... 以及B->A.... 这种才是左递归,如果A->B.... ,B->aA...,  这种就不是左递归了,因为样式不同,请注意)

同样消除左递归的方法:

如果是间接左递归,则先转换成直接左递归:

 

例子:

A->Bb | c

B->Aa

 

将B->Aa代入到另一个式子: A->Aab | c,

 

转换

A->cM

M->abM

M->ε

 

 

就是得出结论,优先删除右部第一个符号和左部相同的即

A->Aab,就是要删除这个右部的第一个A

然后在所有A相关式子后面补一个新的符号 M

变成A->abM    以及A->cM

然后再补充一个式子: M->ε 就得到自己需要的符合的LL(1)文法啦, 大家可以用博主推荐的判断方法,进行判断~~点击打开链接

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

编译原理LL(1)文法之提取左公因子,消除左递归 的相关文章

  • 【编译原理与技术】递归下降语法分析器(C++实现)

    目录 内容 示例 具体实现 C 代码 运行结果 内容 实现以下语法的递归下降分析 示例 对于以下代码给出其递归下降语法分析过程 i 2 while i lt 100 sum sum i i i 2 具体实现 首先对上下文无关文法进行检查 消
  • 合肥工业大学编译原理实验二 LL1分析

    写在开头 当老师说这个实验最好写成图形界面时 我笑了 滑稽 心想终于可以用到python了 python真香 用python的数据结构可以很方便的表示LL1的某些东西 当然有利也有弊 方便的同时也会有一些坑 当然Java也牛逼 Java的图
  • 合工大 编译原理 实验

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

    引言 前面已经介绍了编译器的预处理 词法分析 词法分析器的实现 也在其中说到了语法分析的任务和过程 语法分析的输入是词法单元序列 然后根据语言的文法表示 展开式 利用有限状态机理论 生成抽象语法树 然后遍历得到中间代码 即 三地址码 本节就
  • 编译原理 实验一 词法分析器设计

    一 实验目的 1 深入理解有限自动机及其应用 2 掌握根据语言的词法规则构造识别其单词的有限自动机的方法 3 基本掌握词法分析程序的开发方法 4 能够设计词法扫描器程序 对源程序进行词法分析 并输出单词序列 二 实验内容及要求 编写识别单词
  • 【编译原理】【C语言】实验三:递归下降分析法

    C语言 实验环境 Visual Studio 2019 author zoxiii 递归下降分析法 1 实验内容 2 前期准备 2 1 递归下降分析法原理 2 2 要实现的文法 2 3 需要的函数 3 分析过程 3 1 递归下降分析法设计思
  • 将NFA变成最小化DFA的方法

    学习的时候总感觉这个遇到新的题目不会做 这里总结一下 整个流程是这样的 我们直接来看一个例子 使用上面的算法来实现我们最后的目标 a b ba ab 我们先来画NFA 明确 开始状态和接受状态 终结状态要画两个圈 值得注意的是 由于 也可以
  • 电子科技大学编译原理复习笔记(四):程序语言的设计

    目录 前言 重点一览 语言的定义 比较 生成观点与识别观点 语义又该怎么描述 符号串 符号串集合 文法 超重点 定义 组成 表示 分类 重点 文法产生的语言 短语 直接短语和句柄 求它们目的是语法分析 语法树 推导树 语言的设计 本章习题
  • 【编译原理】- 递归下降的语法分析器的实现

    目录 一 实验题目 二 分析与设计 三 源代码 一 实验题目 编写识别由下列文法G E 所定义的表达式的递归下降语法分析器 E E T E T T T T F T F F F E i 输入 含有十进制数或十六进制数的表达式 如 75 1ah
  • 编译原理------词法分析器C/C++代码实现

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

    为了方便自顶向下语法分析 需要求文法对应的first集 follow集 以及select集 本文主要分为两部分 一个是求法解析 还有一个例子详解 第一部分是求法解析 将对first集 follow集 select集分为三种讲解方法 定义介绍
  • 移入——归约技术

    归约 定义 我们可以将自底向上语法分析过程看成是建一个串w 归约 慰问发开始符号的过程 在归约中 一个与某产生式体相匹配的特定子串被替换为该产生式的头部的非终结符号 定义理解起来比较晦涩 我们来看个例子就知道了 已知有文法 E gt E T
  • LLVM里的寄存器分配 - 准备工作(一)

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

    一 编译原理概述 1 翻译程序 把某一种语言程序 称为源语言程序 等价地转换成另一种语言程序 称为目标语言程序 的程序 2 编译程序 把某一种高级语言程序等价地转换成另一种低级语言程序 如汇编语言或机器语言程序 的程序 又分为 诊断编译程序
  • GDB 程序调试常用命令

    调试之前 若要在GDB中调试程序在编译时需要加上调试信息 在GCC中添加的方法 GCC g a c o a exe 或下面提供更符合GDB的调试信息 GCC ggdb a c o a exe 运行流程 命令 作用 start 开始执行程序
  • PL0语言出错编号表

    Notes 编译原理第 3 版的书貌似没有这个表 做实验和写课设的时候很不方便 把别人拍的第 2 版书上的这个表在这备份一份 Error Code Table 出错编号 出错原因 1 常数说明中的 写成 2 常数说明中的 后应是数字 3 常
  • 【编译原理】LR(1)分析方法(c++实现)

    前文回顾 编译原理 LR 0 分析方法 c 实现 编译原理 SLR 1 分析方法 c 实现 算法 来自龙书第二版 代码 和SLR的区别其实只是DFA中多了一个搜索符 构建分析表的时候规约项的列是相应的搜索符而已 代码基本上就在SLR的代码上
  • 递归下降算法语法分析c语言

    递归下降算法 自上而下文法的递归下降的预测分析 从根节点出发逐步构造分析树 所以被称作自上而下文法 在文法中有递归的函数 例如 E gt TE 所以叫做递归下降算法 使用的文法如下 E gt TE E gt TE e T gt FT T g
  • linux下几种目标文件的分析

    本文中用到的命令 gcc c addvec c 生成可重定位目标文件addvec o readelf addvec o a 读取可重定位目标文件addvec o gcc O2 c main c 生成可重定位目标文件main o gcc st
  • Compiler- 自增运算

    我们来看一下C语言中的前自增 i 和后自增 i 这个经典案例 大家在学习C的时候肯定学过前自增是先自增 然后将结果用于计算 后自增是先参与计算 再增加 好 看一下这段代码的结果 include

随机推荐

  • 工作中常用且容易遗忘的css样式整理,建议收藏

    1 文字超出部分显示省略号 单行文本的溢出显示省略号 一定要有宽度 p width 200rpx overflow hidden text overflow ellipsis white space nowrap 多行文本溢出显示省略号 p
  • Linux(驱动编程)(调试技术)(imx6ull)

    调试技术 1 在写驱动程序时函数未包含头文件 在linux内核源码driver char目录下输入命令 grep XXXX nrw 查看次函数在那个 c里用过 然后在vscode界面下按alt p搜索这个 c就可以参考这个 c的头文件 2
  • docker笔记(二)之镜像加速器

    国内从 Docker Hub 拉取镜像有时会遇到困难 此时可以配置镜像加速器 国内很多云服务商都提供了国内加速器服务 例如 阿里云加速器 点击管理控制台 gt 登录账号 淘宝账号 gt 右侧镜像中心 gt 镜像加速器 gt 复制地址 网易云
  • 从原理到应用,人人都懂的 ChatGPT 指南

    如何充分发挥ChatGPT潜能 成为了众多企业关注的焦点 但是 这种变化对员工来说未必是好事情 IBM计划用AI替代7800个工作岗位 游戏公司使用MidJourney削减原画师人数 此类新闻屡见不鲜 理解并应用这项新技术 对于职场人来说重
  • Pytorch实现多特征输入的分类模型 代码实操

    初学者学习Pytorch系列 第一篇 Pytorch初学简单的线性模型 代码实操 第二篇 Pytorch实现逻辑斯蒂回归模型 代码实操 第三篇 Pytorch实现多特征输入的分类模型 代码实操 文章目录 初学者学习Pytorch系列 前言
  • 基于Java发起HTTP请求实现文件的上传

    需要用到的包
  • wandb快速上手、使用心得(超好用的Tensorboard高替品)

    这里写目录标题 1 wandb介绍 2 快速上手 3 使用心得 3 1 一张图展示两条线 3 2 想要科学上网和wandb一起使用 离线使用 3 3 未完待续 1 wandb介绍 wandb地址 wandb Wandb Weights Bi
  • 构造一个死循环的shell脚本

    while do done
  • springBoot service 事务注解@Transactional不起作用的解决

    在springBoot使用事物时 发现事务并没有正常执行 没有进行回滚 Transactional public void add String companyName String name throws MyException comp
  • C++模板全特化(具体化)与偏特化(部分具体化)详解(转)

    1 模板简介 模板就是实现代码重用的一种机制 它可以实现类型参数化 即把类型定义为参数 从而实现了真正的代码可重用性 模板编程和函数重载可以实现C 静态多态 也叫编译时多态 模版可以分为两类 一个是 函数模版 另一个是 类模版 2 模板特化
  • 利用Vulnhub复现漏洞 - OpenSSH 用户名枚举漏洞(CVE-2018-15473)

    OpenSSH 用户名枚举漏洞 CVE 2018 15473 Vulnhub官方复现教程 漏洞原理 复现过程 启动环境 漏洞复现 CVE 2018 15473 Exploit Vulnhub官方复现教程 https vulhub org e
  • Option类型:C++(std::optional)、Rust(Option)、Go(gob.OptionalValue)

    当我们在实现一个函数 fn point 该函数会有返回的point指针有可能是null 那么函数的调用者必须显示的进行判断 避免出现null point引发的程序崩溃 Rust作为强调系统安全的语言 自然是从语言层面上给予了开发者莫大的帮助
  • 2020年集五福攻略:集五福不再难搞

    2020年的春节就要到了 让人期待的支付宝集五福活动也会随之而来 那么 2020支付宝集五福什么时候开始 支付宝的集福卡活动不是第一届了 2017年的支付宝集五福是1月18日开始 2018年的支付宝集五福是2月6日开始 2019年支付宝集五
  • XSS攻击实战

    一 XSS原理与分类 原理 XSS攻击全程跨站脚本攻击 恶意攻击者往Web页面里插入恶意Script代码 当用户浏览该页之时 嵌入其中Web里面的Script代码会被执行 从而达到恶意攻击用户的目的 与SQL注入类似 XSS也是利用提交恶意
  • 每个程序员都该学习的5种开发语言,不可错过!

    每个公司都喜爱精通多种编程语言并且多才多艺的程序员 一个既能很麻利地写脚本 也能编写复杂的Java程序的程序员 确实相当有价值 所以实际上 对于高级开发者来说 学习不止一种编程语言 几乎就是必然的要求 目前而言 面试官越来越看重那些拥有多种
  • 抢小米手机K40脚本

    声明 基于 puppeteer js 仅辅助更快操作浏览器 本脚本仅供米粉购买小米系列产品 请勿充当黄牛 代码地址 https github com shunyue1320 buy xiaomi
  • 应用层 —— 电子邮件

    一 电子邮件的信息格式 二 系统结构 三 SMTP
  • Meta标签中的apple-mobile-web-app-capable属性及含义

    这meta的作用就是删除默认的苹果工具栏和菜单栏 content有两个值 yes 和 no 当我们需要显示工具栏和菜单栏时 这个行meta就不用加了 默认就是显示
  • 内置数据库

    DERBY 完全使用java 开发 可以在任何存在合适的 Java 虚拟机的地方运行 不适用于在其他编程语言内置使用 HSQLDB Java内置的数据库 非常适合在用于快速的测试和演示的Java程序中 无需独立安装数据库 HSQLDB有三种
  • 编译原理LL(1)文法之提取左公因子,消除左递归

    在判断LL 1 文法是否符合的时候 需要判断LL 1 文法是否存在左公因子 和左递归的情况 以下给出相应的判断方法以及通过提取左公因子和消除左递归使非LL 1 文法转换为LL 1 法的方法 第一种情况 存在左公因子 解决方法 提取左公因子