LL(1) parsing table of left-recursive grammar

Question

I have been taking a compiler course of Stanford on coursera. I have a slight misunderstanding on the parsing table of the following grammar:

S -> Sa | b

According to the professor parsing table looks like this:

• If the leftmost nonterminal is S and the input is 'a', the production is nothing.

• If the leftmost nonterminal is S and the input is 'b', the production is both Sa and b.

So if input is just b, then it is correct, it will go directly to production b. But how will it go to production Sa for input b?

Answer 1

It appears you have misunderstood your professor. "If the leftmost nonterminal is S and the input is 'b', the production is both Sa and b." means that both Sa and b are correct answers if the leftmost nonterminal is S and the input is 'b'. This means that the parser does not know which production to go to and is stuck.

This means that this grammar cannot be parsed using this type of parser technology. You would either have to change the grammar or use a different type of parser.

Answer 2

This language is left-recursion If you try to derive using the first production, you will get some kind of infinite loop $ S \rightarrow Sa \rightarrow Saa \rightarrow Saaa ... \rightarrow Saaa...aaa$ So it cannot be parsed using LL(1). As @Alex ten Brink said, you should change the grammar.