开发者

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 , Arglist

When 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 | e

My 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 ...
0

上一篇:

下一篇:

精彩评论

暂无评论...
验证码 换一张
取 消

最新问答

问答排行榜