Tue, 24 Jun 2008 10:13:01 +0200

Related articles |
---|

predictive parsing and non-recursive predictive parsing unix.sh@gmail.com (2008-06-23) |

Re: predictive parsing and non-recursive predictive parsing kamalpr@hp.com (kamal) (2008-06-24) |

Re: predictive parsing and non-recursive predictive parsing torbenm@pc-003.diku.dk (2008-06-24) |

Re: predictive parsing and non-recursive predictive parsing max@gustavus.edu (Max Hailperin) (2008-06-24) |

Re: predictive parsing and non-recursive predictive parsing james.harris.1@googlemail.com (James Harris) (2008-06-24) |

Re: predictive parsing and non-recursive predictive parsing max@gustavus.edu (2008-06-24) |

Re: predictive parsing and non-recursive predictive parsing gene.ressler@gmail.com (Gene) (2008-06-25) |

Re: predictive parsing and non-recursive predictive parsing unix.sh@gmail.com (2008-06-25) |

Re: predictive parsing and non-recursive predictive parsing ang.usenet@gmail.com (Aaron Gray) (2008-06-27) |

[8 later articles] |

From: | torbenm@pc-003.diku.dk (Torben =?iso-8859-1?Q?=C6gidius?= Mogensen) |

Newsgroups: | comp.compilers |

Date: | Tue, 24 Jun 2008 10:13:01 +0200 |

Organization: | Department of Computer Science, University of Copenhagen |

References: | 08-06-053 |

Keywords: | parse, LL(1) |

Posted-Date: | 24 Jun 2008 21:25:44 EDT |

unix.sh@gmail.com writes:

*> I can use recursive predictive parsing, which is very straightforward.*

*> So what's the advantage of non-recursive predictive parsing. To*

*> perform non-recursive parsing, I need to construct FIRST, FOLLOW sets*

*> and use explicit stack. On the other hand, recursive predictive*

*> parsing is very easy to understand. I understand non-recursive calls*

*> have a better performance than recursive one. Is this the only reason?*

In principle, you also need to construct FIRST and FOLLOW sets to use

deterministic recursive predictive parsing (aka recursive descent).

If there are no empty productions, you don't need FOLLOW and if all

productions for the same nonterminal start with different terminal

symbols, FIRST is trivial, so in these cases you can write recursive

descent parsers very easily. But in the very same cases, construction

of LL(1) parse tables is also very easy. For more complicated cases,

you do need to calculate FIRST and FOLLOW even for recursive descent

-- at least if you want to avoid backtracking.

Table-driven LL(1) is no faster than recursive descent, and it can be

slower in some cases. But tables can be made fairly compact, so

table-driven parsers can be smaller. Also, tables are slightly easier

to generate than programs.

Torben

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.