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

5 Years
Discussion Span
Last Post by 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...


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.

Edited by leegao: n/a


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

Edited by hfx642: n/a

This question has already been answered. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.