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: fac41,9a0ff0bffdf63657 X-Google-Attributes: gidfac41,public X-Google-Thread: 1108a1,9a0ff0bffdf63657 X-Google-Attributes: gid1108a1,public X-Google-Thread: f43e6,9a0ff0bffdf63657 X-Google-Attributes: gidf43e6,public X-Google-Thread: 103376,4b06f8f15f01a568 X-Google-Attributes: gid103376,public From: eachus@spectre.mitre.org (Robert I. Eachus) Subject: Re: Software landmines (was: Why C++ is successful) Date: 1998/09/01 Message-ID: #1/1 X-Deja-AN: 386908161 References: <6qfhri$gs7$1@nnrp1.dejanews.com> <35cb8058.645630787@news.ne.mediaone.net> <902934874.2099.0.nnrp-10.c246a717@news.demon.co.uk> <6r1glm$bvh$1@nnrp1.dejanews.com> <6r9f8h$jtm$1@nnrp1.dejanews.com> <6renh8$ga7$1@nnrp1.dejanews.com> <6rf59b$2ud$1@nnrp1.dejanews.com> <6rfra4$rul$1@nnrp1.dejanews.com> <35EB3B71.ED6D4066@ibm.net> Organization: The Mitre Corp., Bedford, MA. Newsgroups: comp.lang.eiffel,comp.object,comp.software-eng,comp.lang.ada Date: 1998-09-01T00:00:00+00:00 List-Id: In article <35EB3B71.ED6D4066@ibm.net> Biju Thomas writes: > These tools may be generating gotos since they are decades old, and > nobody ever tried to improve upon them. NO! Excuse the shouting. If I am implementing your LALR(k) grammar as a state machine, the only realization that makes sense is to have hundreds of (sometimes thousands of) states. I label the states, and the code moves from state to state, recognizing that some states shift information onto the stack, and others reduce the stack (thus the old name of a shift-reduce parser). The final program makes spaghetti code look well organized, but the maintenance is done on the grammer not on its realization. If you have a "more modern" tool, building the tables is just the first step. Now your tool applies various transformations to the tables which further complexify the resulting code. The resulting compacted and optimized tables bear little or no resemblence to the grammar, but the tables take a few thousand bytes of space, not a few million, and the parser executes ten or so times as fast. It is worth the effort, but now the optimized grammar realization bears little resemblence to the original parser output. (To be more formal, the parser generator might accept some superset of LALR(1) grammars as input, and produce LR(1) tables as output. The final optimized tables may not be in LR(k) for any k.) The final representation (in machine code) is going to use jumps and branches in any case. But the code generated by the tool, if in a high-level language can use a case statement or gotos. Best however, is to put addresses in the tables and have the state machine "table driven." Each state corresponds to executing the core of the driver program with the address of the next state, and the stack as nominal inputs. This core can either be written as a procedure, or as just a block of statements wrapped in a loop. But what you end up with is a driver program that is itself a realization of an FSM. So far so good, but this FSM must handle are several exceptional cases/states. One is the final state, another is when due to the way the tables were compressed, you want to return to a previous point in the processing. (You reach the end of a table, but instead of an error, it says to contine with another table--but you don't want to repeat the setup code...) The final case of course, is error handling. It usually turns out that when writing this driver program, you can use loops, exception handling, continue statements, etc., to cover all but one of the loop backs. But much cleaner and clearer--and I have written those driver programs in PL/I, Ada, and C--is to use one or two well placed gotos. A different way of stating it is that any flowchart of the driver cannot be embedded in a plane. So we are back to where this discussion started. There appear to be some circumstances which justify use of gotos in Ada. But the only cases that anyone in this group has seen involve implementing finite state machines of one kind or another. I think that the structure that makes gotos appropriate is exactly when the flowchart cannot be embedded. I'd like to find more cases if they exist. -- Robert I. Eachus with Standard_Disclaimer; use Standard_Disclaimer; function Message (Text: in Clever_Ideas) return Better_Ideas is...