Left-factoring a non-left-recursive grammar to make it LL(1)
I have removed left-recursion from a left-recursive grammar given to me. The original grammar is as follows:
SPRIME::= Expr eof
Expr::= Term | Expr + Term | Expr - Term Term::= Factor |开发者_Python百科 Term * Factor | Term / Factor | Term mod Factor | Term div factor Factor::= id | { Expr } | num | Funcall | Funcall::= id [ Arglist ] Arglist::= Expr | Expr , ArglistWhen removing left-recursion, this is the grammar I produced:
SPRIME::= Expr eof
Expr::= Term Expr' Expr'::= e | + Term Expr' | - Term Expr' Term::= Factor Term' Term'::= e | * Factor Term' | / Factor Term' | mod Factor Term' | div Factor Term' Factor::= id | { Expr } | num | Funcall Funcall::= id [ Arglist ] Arglist::= Expr Arglist' Arglist'::= , Arglist | eMy next task is to perform left-factoring on this grammar in order to make it LL(1). Having read the relevant chapter in the Dragon book, I'm unsure if I need to do anything to this grammar. My question is: is this grammar in LL(1) form already? And if not, where do I need to perform left-factoring in order to make it LL(1)?
EDIT: After taking @suddnely_me's answer into account, I have edited the Arglist non-terminal in order to left-factor it's productions. Is the grammar I have now an LL(1) grammar?
No, this grammar is not LL(1). At least, the last rules group is not left factored, since FIRST( Expr) and FIRST( Expr, Arglist) do interstect.
if it is in the form of A->A.ALPHA|BETA
REMOVING LEFT RECURSION A->BETA A'|
A'->ALPHA A'|NULL
EXAMPLE:::A->A+B|a
IN THIS A=A A'=A'
ALPHA=+B
BETA=a
REMOVING LEFT RECURSION : A=aA'
A'=+BA'|NULL
No, still (even a year later!) not LL(1). My oracle says:
Can't choose between two rules of 'Factor'
-> id
-> Funcall
'Funcall' can start with id. For example:
Funcall -> id ...
精彩评论