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

间接左递归是指在语法规则中存在一条产生式，该产生式的右部可以推导出一个非终结符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）解析器中驯服了左递归。

8353 0

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

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

4618 0

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

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

7591 0

语法分析

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

3023 0

【C++】模拟实现二叉搜索(排序)树

,即先递归访问左子树再访问根节点最后递归访问右子树但在面向对象设计中,我们设计类内的递归函数会遇到一个问题,就是类对象调用其成员函数的递归传参问题: 我们知道C语言完成中序遍历函数时一个参数是恰好可以满足首次调用和递归调用时传参的形式的...待删除结点只有左孩子结点(不管右孩子) 待删除结点只有右孩子结点(不管左孩子) 待删除结点左,右孩子结点都有在实际删除操作中,可以将1和2 / 3合并起来,因为我们的逻辑是哪边有孩子就管理...//左右都不为空 { //找左树的最右值 Node* parent = cur; //这里不能写=nullptr,防止删的节点的leftMax就是自己的左子树的情况,这样就不会进下面的...//然后复用递归删除自己就行,但是注意,因为自己和左子树的最右值, //即比自己小一点点的值交换了位置,那么再找自己删自己的时候就不能 //从根节点开始找...->_left); //先递归删左子树 Destroy(root->_right); //再递归删右子树 delete root; //最后删掉根节点 root ==

1101 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.3K3 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！

4.1K3 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

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

941 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.8K2 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) # 添加判断条件，类循环写法间接递归

9041 0

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

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

4682 0

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

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

5.1K7 2

Python 函数递归教程

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

5573 0

DFS：解决二叉树问题

函数头函数头：bool dfs(root) 函数体遇到叶子节点返回叶子节点的值，遇到非叶子节点，对左子树和右子树进行递归操作。...从下面图应该可以看出：思路对于这道题，我们先来走一遍，当我们进入根节点4的时候，我们先递归左子树，我们肯定必须要知道前面的和是多少，因为我们要计算下一个节点的和，所以必须知道前面节点的和是多少，...，因为只有后序遍历，才能将左子树和右子树的信息传递给节点，确定了该如何遍历之后，我们来讨论应该如何删除节点，首先我们肯定不能从非叶子节点开始删，因为我们根本不知道他的左子树和右子树的信息，所以应该从叶子节点开始删...，计算这个是第几小，count我们最好选择全局变量，因为全局变量不会随着递归而改变，当我们中序遍历到叶子节点的时候，我们的count就应该–操作，每次–之后，我么都应该判断一下这个count是否已经==...string的原因是因为当我们返回到上一节点的时候，因为全局变量不会改变，所以我们需要手动删除当前路径下的不需要的所有节点，才能进入下一个分支，就拿上面的图为例子，当我们要进入右子树的时候，我们必须将左子树中的

1151 0

【数据结构与算法】红黑树

，路径中的黑色⚫️节点数一样实现插入情况插入节点均视为红色 case 1：插入节点为根节点，将根节点变黑⚫️ case 2：插入节点的父亲若为黑色⚫️，树的红黑性质不变，无需调整插入节点的父亲为红色...可能会接着触发红红相邻，因此对将祖父进行递归调整 case 4：叔叔为黑色⚫️ 父亲为左孩子，插入节点也是左孩子，此时即 LL 不平衡让父亲变黑⚫️，为了保证这颗子树黑色不变，将祖父变成红...1：删的是根节点删完了，直接将 root = null 用剩余节点替换了根节点的 key，value，根节点孩子 = null，颜色保持黑色⚫️不变删黑色会失衡，删红色不会失衡，但删黑色有一种简单情况...case 2：删的是黑⚫️，剩下的是红，剩下这个红节点变黑⚫️ 删除节点和剩下节点都是黑⚫️，触发双黑，双黑意思是，少了一个黑 case 3：被调整节点的兄弟为红，此时两个侄子定为黑 ⚫️ 删除节点是左孩子...红黑树在维护平衡的过程中，能够进行较少的节点旋转操作，因此插入删除效率较高，并且查询效率也较高。综上所述，红黑树具有较高的综合性能，是一种广泛应用的数据结构。

1181 0

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

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

2941 0

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

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

1561 0

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

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

5814 0

点击加载更多

扫码

添加站长进交流群

领取专属 10元无门槛券

手把手带您无忧上云