消除立即左递归 [英] Eliminating Immediate Left Recursion

问题描述

我知道，为了消除包含形式A⇒Aα的语法的立即左递归，我需要将其替换为A⇒βA'和A'⇒αA/∈

I understand that in order to eliminate an immediate left recursion from a grammar containing production of the form A⇒Aα i need to replace it by A⇒βA'and A'⇒αA/∈

我有以下作品，我需要消除立即左递归

Im having the following productions,i need to eliminate immediate left recursion

E⇒E+ T/T

E⇒E+ T/T

T⇒T* F/T

F⇒(E)/(id)

我看到消除后，第一个生产变成了

I can see that after elimination the first production becomes

E⇒TE'

E'⇒+ TE'/T∈

E'⇒+TE'/T∈

有人可以解释这是怎么回事

Can somebody explain how this comes

推荐答案

这实际上只是遵循算法的问题.让我们看一下一般情况.根据该算法，规则的形式为:

It's really just a matter of following the algorithm. Let's look at the general case. According to the algorithm a rule of the form:

A => A a1 | ... | A aN | b1 | .. | bN

其中，A a1, ..., A aN是终端和非终端的非零左递归序列，而b1, ..., bN是不以终端A开头的终端和非终端的序列.

where A a1, ..., A aN are nonzero left recursive sequences of terminals and nonterminals and b1, ..., bN are sequences of terminals and nonterminals that does not start with the terminal A.

算法表明，我们需要将其替换为

The algorithm says we need to replace this by

A => b1 A' | ... | bN A'
A' => a1 A' | ... | aN A' | epsilon

让我们看看您的情况.这里有

Let's look at your case. Here we have

E => E + T | T

因此您可以认为a1是序列+ T，因为E + T是末端和非末端的左递归序列.同样，您可以将B1视为T，因为这是一个非左递归序列.现在，我们将其用于将新的非终结符E定义为:

So you can think of a1 is the sequence + T since E + T is a left recursive sequence of terminals and nonterminals. Likewise you can think of B1 as T since this is a nonleft recursive sequence. We now use this to define the new nonterminal E as:

E => b1 E'

并且由于b1是T，因此变为

E => T E'

定义E'我们得到

E' => a1 E' | epsilon

并且由于a1是+ T，因此变为

E' => + T E' | epsilon 

因此，您最终会得到语法

Thus you end up with the grammar

E => T E'
E' => + T E' | epsilon

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