Re: Grammar analysis

"Lasse =?ISO-8859-1?Q?Hiller=F8e?=
Petersen" <lhp+news@toft-hp.dk> 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.


DoDi

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