Re: Newbie: Does an LR(k) parser compute the FIRST set?

Ulrich Frank wrote:
> - Does a LR-Parser also compute the FIRST and FOLLOW sets like a
> LL-Parser?


Only the FIRST sets are needed for LR(k), k>0, parser construction: the
computation of the lookahead uses them. The basic LR(0) construction
does not use any of these sets. SLR parsers need to compute the FIRST
and FOLLOW sets. LALR parsers do not need any of these sets, but need
to compute which nonterminals are nullable.


> So far I used ANTLR for generating a grammar. I've chosen ANTLR
> because I need to analyse the FIRST set.


What exactly made this analysis of the FIRST sets mandatory? LR parsers
handle more grammars than LL ones, thus if your issue was related to
parsing conflict resolution, there is a slight chance for this analysis
to be unnecessary with LR parsers.


> Now I've read that LR-Parsers are much more efficient and faster
> than LL-Parsers, so I want to change [...].


If you have a working software using ANTLR, I am not sure that the
potential efficiency you might win will be worth rewriting for another
parser generator.


--
Hope that helps,


      Sylvain
[It's been a long time since I saw a compiler where the parser was a
bottleneck. The usual performance hogs are character processing in the
lexer and global analysis in the optimizer. -John]

Return to the comp.compilers page.
Search the comp.compilers archives again.