删除此语法中的间接左递归

间接左递归是指在语法规则中存在一条产生式，该产生式的右部可以推导出一个非终结符A，而A又可以最终推导出产生式左部的非终结符。删除间接左递归是为了消除语法规则中的歧义，使得语法更加清晰和易于理解。

删除间接左递归的方法是通过引入新的非终结符和产生式来实现。具体步骤如下：

检查语法规则中的每个产生式，找出所有存在间接左递归的非终结符。
对于每个存在间接左递归的非终结符A，创建一个新的非终结符A'。
将原产生式中以A开头的产生式复制到A'，并在A'的产生式中删除A的出现。
对于原产生式中以A开头的产生式，将其改为以A'开头。
对于原产生式中以A开头的产生式右部可以推导出的非终结符B，将B的产生式复制到A'的产生式中，并在B的产生式中删除A的出现。
对于原产生式中以A开头的产生式右部可以推导出的非终结符B，将B的产生式改为以A'开头。

通过以上步骤，可以删除语法中的间接左递归，使得语法更加清晰和易于处理。

删除间接左递归的优势是可以消除语法规则中的歧义，使得语法更加易于理解和分析。同时，删除间接左递归也可以减少语法分析过程中的回溯和冗余，提高语法分析的效率。

应用场景：删除间接左递归的方法适用于任何需要消除语法规则中的间接左递归的情况。在编译器设计、语法分析器生成等领域中，删除间接左递归是一个常见的步骤。

腾讯云相关产品和产品介绍链接地址：腾讯云提供了一系列云计算相关的产品和服务，包括云服务器、云数据库、云存储等。具体可以参考腾讯云官方网站：https://cloud.tencent.com/

相关·内容

Python 之父的解析器系列之五：左递归 PEG 语法

传统的补救措施是重写语法。在之前的文章中，我已经这样做了。...当然，因为记忆缓存分别按输入位置和每个解析方法来处理缓存，所以它不受回溯或多个递归规则的影响（例如，在玩具语法中，我一直使用 expr 和 term 都是左递归的）。...我看到它适用于玩具语法中的 expr 等简单情况，也适用于更复杂的情况（例如，涉及一个备选项里可选条目背后藏着的左递归，或涉及多个规则之间的相互递归），但在 Python 的语法中，我能想到的最复杂的情况仍然相当温和...我不会在这里展示算法，事实上我将进一步简化工作，并假设语法中唯一的左递归规则就是直接左递归的，就像我们的玩具语法中的 expr 一样。然后检查左递归只需要查找以当前规则名称开头的备选项。...到此，今天的故事结束了：我们已经成功地在 PEG（-ish）解析器中驯服了左递归。

8173 0

python实现文法左递归的消除方法

前言继词法分析后，又来到语法分析范畴。完成语法分析需要解决几个子问题，今天就完成文法左递归的消除。没借鉴任何博客，完全自己造轮子。...要求 CFG文法判断左递归的类型消除直接左递归和间接左递归界面源码 import os import tkinter as tk import tkinter.messagebox import...（3）不足之处 1、我希望能够实现，非左递归文法，左递归和间接左递归的一起输入一起识别一起消除，碰到非左递归文法就输出“非左递归文法”，然后将其不做任何修改输出。...3、对于间接左递归文法产生式的输入顺序是有要求的，还没能做到随意输入。...从画出界面，接收文本输入，取到产生式，判断类型，消除直接左递归，合并间接左递归再到消除间接左递归。有条有理，一步一个脚印，方能万丈高楼平地起。

1.4K2 0

自顶向下分析：解决回溯及无限循环问题

在自顶向下的语法分析中，我们会遇到回溯的问题以及无限循环的问题。无限循环递归下降解析器的无限循环问题主要来自于左递归文法。...我们将含有A \Rightarrow A \alpha形式的产生式的文法称为是直接左递归的文法。消除直接左递归首先我们要理解直接左递归文法推导出来的到底是什么东西。...存在经过多步推导得到的左递归产生式的文法称为间接左递归文法。...比如，下面这个文法就是一个间接左递归文法： S \Rightarrow Aa \ | \ b A \Rightarrow Ac \ | \ Sd \ | \ \varepsilon 显然，我们能看出具有以下的间接左递归...： S \Rightarrow Aa \Rightarrow Sda 对于间接左递归文法，我们可以通过带入的方式，不断的穷举、替换，把它转换成直接左递归文法，然后用消除直接左递归的方法来做。

3798 0

编译原理文法详解_编译原理为什么存在递归文法

推导把产生式看成重写规则，符号串中的非终结符用产生式右部的串（α）代替。推导具有自反性，传递性。最左/右推导：每次替换都先选择最左/右的串进行推导。...我们对上例法一进行语法分析树的构建（e就是空串）：总之，就是将左推导展开成树的形式。...左递归的判定和消除左递归的判定：一个文法G，若存在P经过一次或多次推导得到Pa（即能推导出以P开头的式子），则称G是左递归的。...βn A’ A’ → α1A’ | α2A’| … | αmA’ | e 2.间接左递归间接左递归就是要通过多次推导才能看出文法有左递归。...总结这一节的主要内容应该是自顶向下分析，为了构建这一棵语法树，我们使用上下文无关文法，定义了推导的概念，发现我们要使用左推导，并且解决了二义性，顺便消除了左递归，这才成功构建出这样一棵语法树。

6851 0

语法分析

自顶向下的分析最左推导 lm表示的是最左最右推导自顶向下的语法分析采用最左推导方式例子自顶向下语法分析的通用形式预测分析文法转换两个问题消除直接左递归消除直接左递归的一般形式...消除间接左递归提取左公因子 LL(1)文法 S_文法例子非终结符的后继符号集follow 产生式的可选集select 串首终结符集first 比如求x的first集合，那么就是求的...A的first集合 select(A->a)它的结果就是a 预测分析表递归的预测分析法非递归的预测分析法例两种方法进行对比预测分析法实现步骤预测分析中的错误处理预测分析中的错误检测...自底向上的语法分析（考试不考）例移入-归约分析的工作过程移入-归约分析器可采取的4种动作移入-归约分析中的关键问题分析完了之后，栈中没有推出起始符S LR分析法 LR分析法的基本原理...就会发现有归约-归约冲突合并同心集后，虽然不产生冲动，但是可能会推迟错误的发现 LR分析中的错误处理语法制导翻译什么是语法制导翻译

2873 0

消除文法的左递归

简介 1．直接左递归的消除消除产生式中的直接左递归是比较容易的。例如假设非终结符P的规则为 P→Pα / β 其中，β是不以P开头的符号串。...P开头，将上述规则改写为如下形式即可消除P的直接左递归： P→β1 P’ / β2 P’ /…/βm P’ P’ →α1P’ / α2 P’ /…/ αn P’ /ε 2．间接左递归的消除消除间接左递归的方法是...，把间接左递归文法改写为直接左递归文法，然后用消除直接左递归的方法改写文法。...利用此算法可以将上述文法进行改写，来消除左递归。首先，令非终结符的排序为R、Q、S。对于R，不存在直接左递归。把R代入到Q中的相关规则中，则Q的规则变为Q→Sab/ ab/ b。...指明是否存在左递归，以及左递归的类型。对于直接左递归，可将其改为直接右递归；对于间接左递归（也称文法左递归），则应按照算法给出非终结符不同排列的等价的消除左递归后的文法。（应该有n！

3.9K3 0

第四章自顶向下语法分析方法

一、确定的自顶向下语法分析思想基本方法：对任何输入串,试图从文法的开始符号出发，自上而下地为输入串建立一棵语法树，或者说为输入串寻找一个最左推导。...4.2 左递归消除 4.2.1 关于非终结符P的规则直接左递归定义：若P → Pα|β，且α、β ∈Ｖ* 4.2.2 方法改写为等价的右递归，形如：P → Pα|β ，α非ε，β不以P开始。...’ \Rightarrow βαP’ \Rightarrow βα 4.2.3 消除多个直接左递归若有多个左递归的产生式如：P→Pα_1| Pα_2 |…| Pα_m |β_1| β_2 |…|β_n...\Rightarrow A) 2.无空产生式(A → ε) 4.2.4 消除间接左递归间接左递归定义：若P\overset + \Rightarrow Pα \ \ \ \ \ α∈Ｖ^* 例如：...→ Aab|b，变成A的产生式含有直接左递归。

1.2K3 0

DS进阶：二叉搜索树

要删除的结点有左、右孩子结点看起来有待删除节点有4中情况，实际情况a可以与情况b或者c合并起来，因此真正的删除过程如下：情况b：删除该结点且使被删除节点的双亲结点指向被删除节点的左孩子结点-...-直接删除（托孤）情况c：删除该结点且使被删除节点的双亲结点指向被删除结点的右孩子结点--直接删除（托孤）情况d：在它的右子树中寻找最小节点（或者在左子树找最大节点），用它的值填补到被删除节点...（递归版）在非递归版本中，我们需要记录父节点，然后将目标节点和父节点进行连接，那递归要如何实现连接呢？？...（递归版） bool _EraseR(Node*&root,const K&key) { if (root == nullptr) return false; //小就到左子树去删，大就到右子树去删...if (root == nullptr) return; //后续遍历，删左删右再删中间 Destroy(root->_left); Destroy(root->_left); delete

751 0

理解递归下降分析和parsec应用

前言本文将会从上下文无关文法开始介绍，从使用 BNF 描述语法到理解递归下降分析思想，最后实现一个简单的 html 解析器收尾。...使用 BNF 描述一下 js 中的简单语法，例如数组语法： js 中数组源代码为： [1] [1, 2, 3] [1, 2, 3, ] 复制代码用 bnf 表示：一个元素 ARRAY ::= "[...在含有递归的语法中，不能出现左递归（包括间接左递归），也不能有二义性，没有左递归且没有二义性的语法符合 LL(1)文法，就可以使用递归下降分析法解析。...左递归无法使用递归下降分析的原因是会让程序死循环，具体可以参考编译原理龙书 2.4.5 Left Recursion 章节。 3. 递归下降分析符合 LL(1)文法的语法可以使用递归下降分析法解析。...画出上面提到 html 语法 bnf（产生式）的展开图：程序将从输入代码字符串从左向右扫描，预测识别为非终结符 ELEMENT，开始解构展开，扫描展开式中的符号，遇到子节点中的下一个非终结符 ELEMENT

1.7K0 0

oracle和mysql语法区别大吗_口语和语法的区别

由于两者的语法有部分不一样，所以需要把Oracle中能用但MySQL中不能用的函数/类型等改为MySQL中能用的，以下是总结出的部分语法区别：一、数据类型 1....表(左/右)关联(+) Oracle左连接,右连接可以使用(+)来实现. MySQL只能使用left join ,right join等关键字。...删除语法 MySQL的删除语法没有Oracle那么随意，例如下面的sql在Oracle中可以执行，但在MySQL中就不可以。...递归查询(start with connect by prior) MySQL不支持(start with connect by prior)的这种递归查询，但可以通过自定义函数来实现...； 2、插入/更新的表必须有主键或唯一索引； -- 3、未修改/新增的数据项，如果必填，则必须有默认值) -- 1、由于是先删后增，所以需要满足以下2个条件之一： -- 1.要么必填项有默认值

2.7K2 0

the-super-tiny-compiler源码解析

代码生成：把转换过的抽象表示转成新代码字符串这里的解析包括词法分析及语法分析，由词法分析器把代码串转换成一系列词法单元（token），再由语法分析器生成能够描述语法结构（包括语法成分及其关系）的中间表示形式...，进行节点级操作（增/删/改节点）和属性级操作（增/删/改属性）。...语法分析 function parser(tokens) { // 当前正在处理的token索引 let current = 0; // 递归遍历（因为函数调用允许嵌套），把token转成AST节点...visitor与transformer实现上是独立的两层，所以需要手动记录新旧两棵树的联系，比如上面转换部分源码中的： // 偷懒以简单粗暴的方式维持新旧AST的联系，方便在遍历过程中操作新AST ast...peak() { return stack[stack.length - 1]; } 并在递归遍历旧树过程中维持这种联系： // 函数调用 CallExpression: { enter(node

1.1K4 0

Python 函数引入

return 语句，隐式会返回一个None值 #定义中的参数列表成为形式参数，只有一种符号表达，简称形参 #调用函数定义，只是声明了一个函数，它不会被执行，需要调用调用的方式，就是函数名加上小括号...斜树左斜树，所有结点都只有左子树右斜树，所有节点都自由右子树满二叉树 # 一颗二叉树的所有分支结点都存在左子树和右子树，并且所有叶子结点只存在在最下面一层完全二叉树 # 满二叉树一定是完全二叉树...函数执行流程（流程演示： http://pythontutor.com/visualize.html#mode=display ）递归Recursion 函数直接或者间接调用自身就是递归...递归需要有边界条件，递归前进段，递归返回段递归一定要有边界条件当边界条件不满足的时候，递归前进当边界条件满足的时候，递归返回 # 小练习： def fib(n):...cur print(cur,end=' ') if n == 2: return fib(n-1,pre,cur) fib(7) # 添加判断条件，类循环写法间接递归

8881 0

算法细节系列（22）：什么时候贪心完！

肯定全部留下，所以把e后面的元素，且在前面出现的全部置空。如下： "aabcezz" 这样我们就可以放心递归求解"aabc"而不会在后面出现了，然后继续递归求解e的后面部分。...咱们继续，如果不存在频次为1的元素该怎么办？很好的问题。答：没有频次为1的字符也很好办，我们就从原来的数中找最小字母所在的第一个index，然后按照上述方法继续递归。...虽然有上述的试错，但我们已经得到了正确答案，我们要找的划分应该保证左半部分的字符一定会出现在右半部分，那么在众多满足条件的划分中，我们一定寻找字符最小的那个。所以，新的思路如下： a....针对所有元素遍历一遍，针对每个index得到左半部分和右半部分。保证左半部分的元素都能在右半部分找到。 b....在所有符合情况的index中，找寻字符最小的那个index，这样，我们可以直接删除左半部分，剩下来的就是递归求解右半部分。

4592 0

编译原理学习笔记-5：自顶向下语法分析

语法分析 1.1 语法分析器在词法分析中，我们扫描输入源程序的每个字符，得到多种类型的单词（token），一系列的单词就构成了一条单词流。...但在这个过程中存在着一个问题，这个问题概况地说就是文法的不确定性。为什么说具有一种不确定性呢？我们可以从以下三个方面一一分析。 2.1 左递归 ① 定义其一，文法存在的左递归带来了不确定性。...这种不太明显的、需要经过替换才能体现递归性的，称之为间接左递归。...a，但是它确信在语法树中，排在自己右边的非终结符足以处理 a。...我们试着用预测分析程序进行语法分析。 ① LL(1) 判断有没有左递归？很明显，这个文法存在直接左递归，为了方便后续工作的开展，这里先消除左递归。

5K7 2

Python 函数递归教程

1.什么是函数递归函数的嵌套调用：一个函数里面又写了一个函数。函数的递归调用：他是一种特殊的嵌套调用，他也是在函数里面调用函数，但是他在函数体内调用的函数时他自己本身。...ls[0] res = func(n-1)+2 return resprint(func(5))3.间接调用间接调用指的是：不在原函数体内调用函数自身，而是通过其他的方法间接调用函数自身。...：一层一层的递归调用，每一次进行下一次的递归的时候问题的规模都必须是在减小的归：必须要又一个明确的结束条件，在满足该条件开始一层一层回溯。...在不断的重复过程之后，可以得到一个最终的结果列题给定一个只包括 '('，')'，'{'，'}'，''，'' 的字符串，判断字符串是否有效。有效字符串需满足：左括号必须用相同类型的右括号闭合。...左括号必须以正确的顺序闭合。注意空字符串可被认为是有效字符串。

5443 0

【二叉树进阶】搜索二叉树（递归+非递归两种版本详解）

删除操作（非递归）-重难点那如果要删除二叉搜索树中的某个结点，应该怎么处理呢？...另外其实第一种情况也可以归到第二种或第三种里面，第一种是两个孩子都为空，那也可以归到左为空或者右为空的情况里面。要删除的结点有左、右孩子结点比如我们要删除3或8，怎么删？...查找（递归版本）查找用递归要怎么写呢？在类里面定义的递归一般我们都要套一层写成这种，原因就和我们上面写中序遍历那里一样。 6.2 思路分析那具体怎么实现呢？...不可以的，因为C++中的引用是不能改变指向的，引用一旦引用一个实体之后，就不能再引用其他实体而这里递归的话，每次递归都相当于创建了一个新的引用，而不是改变上一层的引用的指向。...那其实大致的思路还是一样的，从根结点开始判断，如果要删除的值大于根，转换为去右子树删，小于根，转换为去左子树删，等于，就进行删除，如果走到空，那就是找不到。

2291 0

【C++】深入剖析C++11新特性

我们可以修改接口中只有头插头删，没有尾插尾删，因为如果要对尾部操作需要找尾， 3.unordered_map和unordered_set 这两个是以哈希为底层机构封装的容器，在查找方面速度优于以红黑树为底层结构的...---- 七、右值引用 1.右值引用和左值引用传统的C++语法中就有引用的语法，而C++11中新增了的右值引用语法特性，所以从现在开始我们之前学习的引用就叫做左值引用。...而右值引用是间接起作用，实现移动构造和移动赋值，在拷贝的场景，如果时将亡值，转移资源。 4.右值引用引用左值及其一些更深入的使用场景分析我们都知道，左值是无法使用右值引用的。...在C++11中更简单，只需在该函数声明加上=delete即可，该语法指示编译器不生成对应函数的默认版本，称=delete修饰的函数为删除函数。...，不需要通过递归终止函数，是直接在expand函数体中展开的, printarg不是一个递归终止函数，只是一个处理参数包中每一个参数的函数。

3764 0

DS：二叉树的链式结构及实现

而以下的学习中要重点理解二叉树中的递归思想和分治思想 !...因为每次我递归比较完后，并没有记录最大值，所以导致每次递归的时候最大值都得再重新递归一次！！如果树节点高度特别高的话，就很可能会出现这样的问题。...LeftHeight + 1 : RightHeight + 1; } 所以我们在递归时使用三目表达式要注意：如果比较的过程已经递归一次了，比较的结果就不要再去递归了！！可以及时的记录值！！...2.11 二叉树查找值为x的节点还是利用分治思想,转化为在左子树和右子树中找 BTNode* BTFind(BTNode* root, BTDataType x) { if (root == NULL...QueueEmpty(pq)); //队列中的出队列相当于链表的头删 //如果直接头删，那么如果队列只有一个有效数据的话，那么我们将phead的空间释放掉，但是没有将ptail给置空 //这样会导致

1261 0

Leetcode|BST修改与构造|669. 修剪二叉搜索树

1 递归注意，这里的核心思路不是剪枝或者显示删除每个不符合条件的节点。而是通过找到符合条件的节点或者子树，然后把符合条件的拼接到一起，从而间接达到修剪的目的。...根据BST性质，左必然小，右必然大，因此可以先通过节点的值比较找到符合[low, high]区间的节点，然后把两两符合条件的节点进行连接，从而间接移除了不符合条件的节点。...root) return nullptr; // 1.1 在右子树中寻找符合区间[low, high]的节点 if (root->val right, low, high); // 1.2 在左子树中寻找符合区间[low, high]的节点 if (root->val > high) return...trimBST(root->left, low, high); // 2.1 root->left接入符合条件的左子树 root->left = trimBST(root

2101 0

文件管理大师：深入解析Linux的文件与目录操控

mkdir创建目录命令:mkdir(make directory，创建目录) 作用:创建目录语法:mkdir[参数选项]路径(包含目录名) 常见参数: -p:递归创建所有目录,如果想创建多层不存在的路径...，一定是报错的需要递归删除 2、文件创建、删除 touch创建文件命令:touch 作用:创建文件，多次创建不报错，但是会修改文件的时间属性语法:#touch 文件路径[文件路径2 文件路径3.....touch命令虚拟机的快照为了防止你删库的。...) 命令:rm(remove缩写) 作用:删除文件或文件夹语法:rm [参数选项]文件或文件夹选项: -r:递归删除，主要用于删除目录，可删除指定目录及包含的所有内容，包括所有子目录和文件。...删腻了，你上班就不会出错了） 1.rm命令不带参数 2.rm命令删除多个文件 3.rm -f强制删除文件 4.rm -r递归删除文件及目录 5.rm -r -f强制递归删除文件夹 6.危险命令注意rm

1511 0

点击加载更多

扫码

添加站长进交流群

领取专属 10元无门槛券

手把手带您无忧上云