Type of parser used for javac

[stevanity]

I wanna know what type of parser is used in the javac compiler. whether a top-down or bottom-up parser is used..... ?

[zeroliken]

I think it's a top-down parser
It starts at the top of the program which is line 1 right?

[stevanity]

Ermm. do u know whats the difference between a top down and bottom up parser?? its an internal thing.. evry compiler starts from the line 1. Its about how the tokens are validated...

[JamesCherrill]

According to http://compilers.iecc.com/comparch/article/01-03-037 it's LL(1), recursive descent

[leegao]

To be fair, top-down isn't a very descriptive name for the category of grammars.

If we're using http://java.sun.com/docs/books/jls/second_edition/html/syntax.doc.html without any modification, then this grammar is probably not suitable for LL(1).

The most obvious problem comes from Selector -> . x | . y | . z However, a LL(2) parser generator or one that does smart refactoring on the grammar (not possible with the action code however) will be able create a correct parser for this production rule.

More subtle issues includes:

1. The famous dangle else problem.
in the following production

Statement -> if ParExpression Statement [else Statement]

if we get rid of the extended syntax, (using the rules of left-factoring, in that A -> alpha [E] beta === A -> E' beta; E' -> epsilon | E), then we have
Statement -> if ParExpression Statement ELSE'
ELSE' -> epsilon | else Statement

since ELSE' is nullable, in order to fill the jump table for ELSE'[else], we must look at Follow(ELSE') = FOLLOW(Statement) which includes FIRST(ELSE') = {else}. Hence, we have a duplicity for the transition from ELSE' under the lookahead terminal of "else". In LL(1), this is an ambiguous production.

2. Expression3 -> Type Expression3
| Primary {Selector} {PostfixOp}

Since FIRST(Primary) U FIRST(Type) = {int,long,float,double,boolean}, Expression3 cannot predictively determine what action to take on encountering any of the primitive type tokens.

A few more ambiguities such as trying to determine how any of the assignment operators ought to proceed on the [Expression1Rest] rule, given that it is nullable and a few even more subtle ones.

[hfx642]

Well... My error lists have always been in order of ascending line numbers.

[stevanity]

According to http://compilers.iecc.com/comparch/article/01-03-037 it's LL(1), recursive descent

Thanks a lot!! That was very helpful... :)

And thanks to everyone who replied :)