消除间接左递归 [英] elimination of indirect left recursion

问题描述

我在理解有关如何删除此语法中的左递归的在线解释时遇到问题.我知道如何删除直接递归，但不清楚如何处理间接递归.有人可以解释吗?

I'm having problems understanding an online explanation of how to remove the left recursion in this grammar. I know how to remove direct recursion, but I'm not clear how to handle the indirect. Could anyone explain it?

A --> B x y | x 
B --> C D
C --> A | c
D --> d

推荐答案

我学会的方法是用每个扩展替换有问题的非终结符之一.在这种情况下，我们首先将 B 替换为其扩展名:

The way I learned to do this is to replace one of the offending non-terminal symbols with each of its expansions. In this case, we first replace B with its expansions:

A --> B x y | x
B --> C D

成为

A --> C x y | D x y | x

现在，我们对非终端符号 C 执行相同的操作:

Now, we do the same for non-terminal symbol C:

A --> C x y | D x y | x
C --> A | c

成为

A --> A x y | c x y | D x y | x

剩下的唯一其他语法规则是

The only other remaining grammar rule is

D --> d

所以您也可以替换 ，将整个语法保留为

so you can also make that replacement, leaving your entire grammar as

A --> A x y | c x y | d x y | x

由于根本没有间接的东西，所以现在没有间接的左递归.

There is no indirect left recursion now, since there is nothing indirect at all.

另请参见此处.

要完全消除左递归(不仅是间接左递归)，请从您自己的资料中引入 A'符号(为澄清和完成，请注明为OP):

To eliminate left recursion altogether (not merely indirect left recursion), introduce the A' symbol from your own materials (credit to OP for this clarification and completion):

A -> x A' 
A' -> xyA' | cxyA' | dxyA' | epsilon

---

回复 naomik 的评论

---

Response to naomik's comments

是的，语法具有有趣的属性，您可以根据语法规则的约束来表征某些语义功能.有一些转换算法可以处理某些类型的解析问题.

Yes, grammars have interesting properties, and you can characterize certain semantic capabilities in terms of constraints on grammar rules. There are transformation algorithms to handle certain types of parsing problems.

在这种情况下，我们要删除左递归:语法的一个理想属性是 any 规则必须的使用至少消耗一个输入标记(终端符号).左递归打开了解析器中无限递归的门.

In this case, we want to remove left-recursion: one desirable property of a grammar is that the use of any rule must consume at least one input token (terminal symbol). Left-recursion opens a door to infinite recursion in the parser.

多年前，我在计算基础"和编译器构造"课程中学习了这些东西.与其编写解析器以适应特定语法，不如将语法转换为适合我们所需的解析器样式.

I learned these things in my "Foundations of Computing" and "Compiler Construction" classes many years ago. Instead of writing a parser to adapt to a particular grammar, we'd transform the grammar to fit the parser style we wanted.

这篇关于消除间接左递归的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！