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

Sylvain Schmitz <schmitz@i3s.unice.fr>
14 Feb 2006 10:15:56 -0500

          From comp.compilers

Related articles
Newbie: Does an LR(k) parser compute the FIRST set? franku@fmi.uni-passau.de (Ulrich Frank) (2006-02-12)
Re: Newbie: Does an LR(k) parser compute the FIRST set? schmitz@i3s.unice.fr (Sylvain Schmitz) (2006-02-14)
Newbie: Does an LR(k) parser compute the FIRST set? egagnon@sablevm.org (Etienne Gagnon) (2006-02-14)
Re: Newbie: Does an LR(k) parser compute the FIRST set? franku@fmi.uni-passau.de (Ulrich Frank) (2006-02-14)
| List of all articles for this month |

From: Sylvain Schmitz <schmitz@i3s.unice.fr>
Newsgroups: comp.compilers
Date: 14 Feb 2006 10:15:56 -0500
Organization: Compilers Central
References: 06-02-089
Keywords: LALR, parse, comment
Posted-Date: 14 Feb 2006 10:15:56 EST

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]


Post a followup to this message

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