recursioncompiler-constructioncontext-free-grammarambiguous-grammar

Fully left-factor the following grammar so that it is suitable for use in a top-down compiler


Here S is the non-terminal start symbol; A, B, C are non-terminal symbols; x, y, are terminal symbols

S → A B A C | A C A B
A → A x | A y
B → B x x | B y y
C → x y | y x

Having watched videos I understand simple examples for eliminating left recursion in production rules such as

S → a S a
S → b S b
S → ε

but I don't understand how to eliminate left recursion in the rules shown above. Can anyone explain or point me in the direction of an explanation?


Solution

  • There is no left-recursion in your second example, so removing the left-recursion is trivial.

    In your first grammar, you need to left-factor before you can tackle elimination of recursion. (Indeed, the title of your question says "left-factor", so you already had this clue in your homework assignment/quiz.)

    The link provided above is one of hundreds found by Google with the search term "left factor grammar", but I'd suggest that you at least consider the possibility that your course materials are a better source of information than Google searches (or random Youtube videos).