Write short note onLeft recursion and left factoring removal technique System Programming and Compiler Construction Sem 6 Mumbai University May 2015

We are building EduLadder(ELADR) - Protocol

The Eladr Protocol is a decentralized, security and efficiency enhanced Web3 noSQL database powered by IPFS as the data storage layer https://ipfs.io/, and the Cardano block chain as the rewards token platform, https://cardano.org/. It provides a JSON based, IPFS layer 2 solution for data indexing and retrieval in an 'append only' file system built with open source Node.js API libraries.

The ELADR token was designed to incentivize and reward community members as a proof of contribution. Token holders are also granted access to EduLadder.com premium features as well as associated ELADR token enabled apps.

WHITE PAPER Buy Now Try BETA

Real Problems! Real Experts!

Join Our Telegram Channel !

The Eduladder is a community of students, teachers, and programmers. We help you to solve your academic and programming questions fast.
In eduladder you can Ask,Answer,Listen,Earn and Download Questions and Question papers.
Watch related videos of your favorite subject.
Connect with students from different parts of the world.
Apply or Post Jobs, Courses ,Internships and Volunteering opportunity. For FREE
See Our team
Wondering how we keep quality?
Got unsolved questions? Ask Questions

GATE GMAT CBSE NCERT Career Interview Railway UPSC NID NIFT-UG NIFT-PG PHP AJAX JavaScript Node Js Shell Script Research

UNIX-SYSTEMS-PROGRAMMING-AND-COMPILER-DESIGN-LABORATORY-10CSL68--->View question

Write short note on:Left recursion and left factoring removal technique -System Programming and Compiler Construction-Sem 6-Mumbai University-May 2015

It is related to system programming and compiler construction.

Asked On2017-12-19 15:50:03 by:leo

Taged users:
Jhon 13priya

Likes:
Purnima

Dislikes:
Be first to dislike this question
Talk about this Like Dislike

View all questions

Answers

Left Recursion

•Left Recursion. The production is left-recursive if the leftmost symbol on the right side is the same as the non-terminal on the left side.

•For example, expr → expr + term. If one were to code this production in a recursive-descent parser, the parser would go in an infinite loop.

Elimination of left Recursion

We eliminate left-recursion in three steps.

•eliminate ɛ -productions (impossible to generate ɛ!)

•eliminate cycles (A ⇒+ A)

•eliminate left-recursion

Step 1

2. Direct Recursion

For each rule which contains a left-recursive option,

A --> A | β

introduce a new nonterminal A' and rewrite the rule as

A --> β A'

A' --> | A'

Thus the production:

E --> E + T | T

is left-recursive with "E" playing the role of "A","+ T" playing the role of , and "T" playing the role of β A'.

Introducing the new nonterminal E', the production can be replaced by:

E --> T E'

E' --> | + T E'

Of course, there may be more than one left-recursive part on the right-hand side. The general rule is to replace

A --> A | | ... | β | β | ... | β

A --> β A' | β A'| ...| β A'

A' --> | A' | A' | ...| A'

Note that this may change the "structure". For the expression above, the original grammar is left-associative, while the non-left recursive one is now right-associative.

Step 2

Indirect Recursion

Step one describes a rule to eliminate direct left recursion from a production. To eliminate left-recursion from an entire grammar may be more difficult because of indirect left-recursion.

For example

A --> B x y | x

B --> C D

C --> A | c

D --> d

is indirectly recursive because

A ==> B x y ==> C D x y ==> A D x y.

That is, A ==> ... ==> A where is D x y.

The algorithm eliminates left-recursion entirely. It contains a "call" to a procedure which eliminates direct left-recursion (as described in step one).

Left Factoring

Left factoring is another useful grammar transformation used in parsing

Left Factoring is a grammar transformation technique. It consists in "factoring out" prefixes which are common to two or more productions.

For example, going from:

A -> α β | α γ

to:

A -> α A'

A' -> β | γ

Left factor:

Let the given grammar: A-->ab1 | ab2 | ab3

1)We can see that, for every production, there is a common prefix & if we choose any production here, it is not confirmed that we will not need to backtrack. 2)It is non deterministic, because we cannot choice any production and be assured that we will reach at our desired string by making the correct parse tree. But if we rewrite the grammar in a way that is deterministic and also leaves us to be flexible enough to make it any string that may be possible without backtracking.... it will be:

A --> aA', A' --> b1 | b2| b3 now if we are asked to make the parse tree for string ab2.... we don't need back tracking. Because we can always choose the correct production when we get A' thus we will generate the correct parse tree.

Left factoring is required to eliminate non-determinism of a grammar. Suppose a grammar, S -> abS | aSb

Here, S is deriving the same terminal a in the production rule (two alternative choices for S), which follows non-determinism. We can rewrite the production to defer the decision of S as-

S -> aS'

S' -> bS | Sb

Thus, S' can be replaced for bS or Sb

Difference between Left Factoring and Left Recursion

Left recursion: when one or more productions can be reached from themselves with no tokens consumed in-between.

Left factoring: a process of transformation, turning the grammar from a left-recursive form to an equivalent non-left-recursive form.

Left factoring is removing the common left factor that appears in two productions of the same non-terminal. It is done to avoid back-tracing by the parser. Suppose the parser has a look-ahead ,consider this example-

A -> qB | qC

where A,B,C are non-terminals and q is a sentence. In this case, the parser will be confused as to which of the two productions to choose and it might have to back-trace. After left factoring, the grammar is converted to-

A -> qD

D -> B | C

In this case, a parser with a look-ahead will always choose the right production.

Left recursion is a case when the left-most non-terminal in a production of a non-terminal is the non-terminal itself (direct left recursion) or through some other non-terminal definitions, rewrites to the non-terminal again (indirect left recursion).

Consider these examples -

(1) A -> Aq (direct) (2) A -> Bq B -> Ar (indirect)

Left recursion has to be removed if the parser performs top-down parsing.

Answerd on:2018-06-06 Answerd By:aksingh1818

Likes:
|aksingh1818

Dislikes:
Be first to dislike this answer
Talk about this Like Dislike

Lets together make the web is a better place

We made eduladder by keeping the ideology of building a supermarket of all the educational material available under one roof. We are doing it with the help of individual contributors like you, interns and employees. So the resources you are looking for can be easily available and accessible also with the freedom of remix reuse and reshare our content under the terms of creative commons license with attribution required close.

You can also contribute to our vision of "Helping student to pass any exams" with these.
Answer a question: You can answer the questions not yet answered in eduladder.How to answer a question
Career: Work or do your internship with us.Work with us
Create a video: You can teach anything and everything each video should be less than five minutes should cover the idea less than five min.How to upload a video on eduladder

Welcome to Eduladder V 4.0

Ads

Write short note on:Left recursion and left factoring removal technique -System Programming and Compiler Construction-Sem 6-Mumbai University-May 2015

It is related to system programming and compiler construction.

Similar Questions

Notes