Re: Grammar analysis (VBDis)
29 Nov 2004 00:25:11 -0500

          From comp.compilers

Related articles
Grammar analysis (2004-11-20)
Re: Grammar analysis (Lasse =?ISO-8859-1?Q?Hiller=F8e?= Petersen) (2004-11-26)
Re: Grammar analysis (Alexey Demakov) (2004-11-28)
Re: Grammar analysis (2004-11-29)
Re: Grammar analysis (Lasse =?ISO-8859-1?Q?Hiller=F8e?= Petersen) (2004-12-01)
Re: Grammar analysis (2004-12-01)
| List of all articles for this month |

From: (VBDis)
Newsgroups: comp.compilers
Date: 29 Nov 2004 00:25:11 -0500
Organization: AOL Bertelsmann Online GmbH & Co. KG
References: 04-11-102
Keywords: parse
Posted-Date: 29 Nov 2004 00:25:11 EST

"Lasse =?ISO-8859-1?Q?Hiller=F8e?=
Petersen" <> schreibt:

>> The computation of the First and Follow sets is not trivial,

>I hope you meant trivial, I managed to write some code that seems to
>work, so it must be! ;-)

Okay, I better had said "The efficient computation...".

>I think I've seen references to "efficient" computation of FIRST and
>FOLLOW; but given the simplicity of the approach above, when would such
>efficient algorithms be worthwhile?

At least when the computation of a big grammar takes days...

The first rules in the loop tend to stabilize soon, nonetheless they
are re-evaluated in your implementation in every iteration. IMO you'll
find a difference when you count the processed productions in your
loop, both with and without the "something_changed" wrapper.

Thanks for your hint on "efficient", I'll try to find such qualified
references myself.

I suspect that it may be worth to compute dependency trees first, and
then to process the productions in these trees by DFS? My idea here is
that then the "bits" ripple up into all affected sets only once.


Post a followup to this message

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