14 Feb 2006 10:15:56 -0500

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) |

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.