The Gateway to Computer Science Excellence
+3 votes
lets consider a grammar as:

$A\rightarrow Ab | Ac | a$

while checking whether it belongs to LL(1) grammar, we would point out that it has a left recursion as well as left factoring.

I was wondering that what would be the case if we had lookahead, k,  greater than 1.

So if look ahead , k =2.

will there be any need to remove left recursion or left factoring. Furthermore, should we still call it as a:

1) left recursion: because if we are looking 2 symbols at a time, there shouldnt be any recursion at all.

2) left factoring: we need not backtrack as we are looking beyond the common symbol, A to decide the production rule to be applied.

any further insights about the same will be very helpful.
in Compiler Design by Junior (941 points) | 468 views

1 Answer

0 votes
if a grammar has to be ll 1 then it should not be left recursive so you should eliminate left recursion while you need to make a grammar ll 1. If there is more than one production for the same variable as well as left recursion then there may be possibility to come all this production in the same cell of ll 1 parsing table because the left recursive variable we'll have same first and will keep those production in the first of left recursive variable  in ll 1 passing table.
by Junior (807 points)
I think you did not get what I was trying to ask.

To put it in simple words:

if look ahead were 2, does left recursion or left factoring would be a problem in this grammar(since we can look beyond first symbol I dont think there should be any LR or LF)
@manu00x @Rishi yadav @Kathleen any additions would be helpful :)
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,390 answers
105,443 users