1
$\begingroup$

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?

$\endgroup$

migrated from stackoverflow.com Aug 14 '12 at 12:33

This question came from our site for professional and enthusiast programmers.

  • 2
    $\begingroup$ What is your goal here? Left-recursive grammars can not be parsed by LL(1). $\endgroup$ – Raphael Aug 14 '12 at 20:39
7
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.