I was trying to solve a question for practice, but I met a problem when I tried to compare the sample answer with mine. Here is the grammar before conversion:
E-> S*
S-> SD
S-> D
D-> [D]
D-> x
The start symbol is E and the other non-terminal symbols are S and D.
My answer here is :
E-> S*
S-> DS'
S'-> DS'
S'->
D-> [D]
D-> x
In the sample answer, they don't have S-> DS', and E becomes E-> DS'*. Due to the methods used in the book for removing left recursions,
A -> Aa
A -> b
=> A -> bA'
A' -> aA'
A' ->
there should be a S-> DS'. I'm now getting confused about this, and maybe I just did not understand this method. Could anyone give me any hints about this? And also could you please tell me the meaning of the star symbol * here? Thanks a lot!
There's nothing wrong with your answer. The sample answer just simplifies the grammar after transforming it.
E -> S*
S -> DS'
Given rules for S' and D, and assuming that S and E do not occur in other productions, this part of the grammar is equivalent to
E -> DS'*
The S in the first production was simply replaced by DS', as defined in the second production that has been stripped away.
The * symbol is possibly a Kleene star. It means that S can occur any number of times (including zero). But without context, it's hard to tell, and it could also mean something else.