I'm preparing midterm exam, so I found some questions and tried to solve it.
But my answer is not as same as given answer

Question:

Consider The Following Grammar, Which Generates Email Addresses:

Addr → [email protected]
Name → id | id.Name

This grammar, as written, is not LL(1).  Rewrite the grammar to eliminate all LL(1) conflicts.

The question asked us to eliminate LL(1) conflicts According to my understood, it can be eliminated by left factoring.
Therefore, my answer is

Addr → [email protected]
Name → idName'
Name' → epsilon | .Name

However, the given answer is

Addr → [email protected]
Name → idName'
Name' → epsilon | .idName'

Is there any wrong of my understood? Any advise in this post is appreciated.
Thanks

CodePudding user response：

As far as I can see, neither your solution nor the one you show as the given answer is LL(1). However, the given answer is a more accurate reflection of the left-factoring procedure. Your solution leaves the artefact Name -> id Name', which now serves no purpose; expanding Name in the grammar to its only production eliminates an unnecessary derivation step. (Indeed, you could eliminate both instances of Name, the same way.)

But if the question is asking you to come up with an LL(1) grammar, then the given answer is not going to work.

Take a simple address, [email protected], and imagine that the parser runs until just after example, which is an id. At this point the parser is expecting a Name', which is either empty or something which starts with .. (In your grammar, the something is '.' Name and in the solution you quote, it's '.' id Name, but either way the expected next token is ..) So the parser needs to decide between the empty production and the production starting with a .. Since the lookahead is ., the parser could certainly choose the production starting with .. But what about choosing the empty production? In that case, the next token will match whatever follows the second Name in Addr -> Name @ Name . id, which is also a .. In other words, looking at the ., the parser has two apparently valid options: the empty production or the production starting with .. And that's true whether it's using your grammar or the solution's grammar.

The simplest solution (which is not very general) is to rearrange the Addr rule. Addr wants there to be at least two ids after the @, which could just as well be achieved with:

Addr -> Name @ id . Name

You still need to left-factor Name to make that work, but now there is no problem with Name's FOLLOW set; it can no longer be followed by a ., and the decision after example is forced.