From mboxrd@z Thu Jan 1 00:00:00 1970 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me X-Spam-Level: X-Spam-Status: No, score=-1.3 required=5.0 tests=BAYES_00,INVALID_MSGID autolearn=no autolearn_force=no version=3.4.4 X-Google-Language: ENGLISH,ASCII-7-bit X-Google-Thread: 103376,99222a5bd46ef3c9 X-Google-Attributes: gid103376,public From: "Samuel T. Harris" Subject: Re: GOTO considered necessary (reworked) Date: 1997/06/25 Message-ID: <33B1702E.794B@hso.link.com>#1/1 X-Deja-AN: 253091599 References: <5nn2fm$11dk$1@prime.imagin.net> <33A58C79.1C7A@sprintmail.com> <5oqu9i$s22@zdi.informatik.uni-stuttgart.de> Organization: Hughes Training Inc. - Houston Operations Newsgroups: comp.lang.ada Date: 1997-06-25T00:00:00+00:00 List-Id: Wolfgang Gellerich wrote: > > In article , bobduff@world.std.com (Robert A Duff) writes: > > (...) > > |> In my experience, a hand-coded lexical analyzer is always better done > |> with loops and ifs and case statements, rather than as above. That is, > |> forget that it's a FSM, and just write it in the natural way. ("An > |> identifier is a letter, followed by a sequence of zero or more letters > |> and digits" translates quite nicely into loops, not gotos.) I know you > |> agree, since I've seen the GNAT lexer. (A tool-generated lexer is a > |> whole 'nother story, of course -- throw readability to the winds, and go > |> for efficiency. Funny thing is, tool-generated lexers are less > |> efficient, in practise, in my experience.) > > Definitely. We recently made a study comparing different methods how to > implement an Ada 95 scanner and then measured the time they needed to lexical > analyse some large Ada sources. The slowest and the fastest scanners > differed by factor 74 (!) and the fastest one was hand-coded scanner, using > no GOTOs and basically following the strategy described above. > > ------ > > Wolfgang While true as to efficiency, tool-generated scanners allow you to work in the realm of the syntax of you language and allows you to quickly modify your syntax and get a new scanner almost instantly. As far as the loop/case vs goto is concerned for general FSA, I have used both on occasion, but have always perfered tables with subprogram pointers. While not directly possible with Ada 83 except through families of task entries (a kludge), Ada 95's new support for access to subprogram objects makes this an attactive alternative. The advantage of the table approach is that you can easily maintain it by adjusting the values within the table. The table is index by state and input, which each component of the 2-dimentional array being a recording containing subprogram pointers and the new state. The FSM simply remembers the current state. The iterate operation applies a new input to the FSM which indexes the table, executes the subprogram, and resets the current state. FSM which require prolog and epilog operations around the main action routine will have additional subprogram pointers in the record structure. If feedback from the action routine is required to determine the next state, then the action routine can be a function taking the current state, input, and recommended next state and return the actual next state. The point is that once the logic and semantics of traversing the FSM from one state to another has been built to whatever level of complexity is appropriate, then the mechanism for iterating the FSM can be encapuslated into a 2 dimentional table and the "engine" itself is a really simply piece of code. The table itself can be initialized with an aggregate or read in from a data file. By separating the action routines from the FSM code, you get easy maintenance when the tables change. Of course, you can achieve the same separation with the loop/case and goto model, but you have to "touch" the source code when the transitions change. With a table driven FSM, you only have to change the data file. As a side note, I'm working on an effort at the moment where the internal FSM of the component is sometimes an "animated" entity (running on its own in a background task) and sometimes it is an "actuated" entity (meaning the program doesn't want tasks hanging around and needs to control when the FSM interates). A goto model must always be animated. A loop/case or table driven model can be animated or actuated. As with any debate concerning equally "powerful" alternative, it is the application of very specific requirements which show one method to be superior to the others, but only for that particular case. That's which none of the three is the best all (or even most) of the time. -- Samuel T. Harris, Senior Engineer Hughes Training, Inc. - Houston Operations 2224 Bay Area Blvd. Houston, TX 77058-2099 "If you can make it, We can fake it!"