DOES APL REALLY NEED RUN-TIME PARSING
Original Publication Date: 1975-Jul-31
Included in the Prior Art Database: 2007-Mar-29
Software Patent Institute
Strawn, George O.: AUTHOR [+2]
DOES APL REALLY NEED RUN-TIME PARSING? by George 0. Strawn Technical Report 76-1
DOES APL REALLY NEED RUN-TIME PARSING?
George 0. Strawn
Technical Report # 76-1
To appear in forthcoming issue of Software: Practice and Experience.
Most APL systems delay all parsing until run-time. Because
the APL expression language is inherently ambiguous and because identifier binding is delayed until run-time, some run-time parsing is shown to be necessary. Nevertheless we argue that most APL statement parsing can be done at entry time and that there are several reasons for doing so. Then a technique is described whereby 'APT., statements are partially parsed at entry time and are parse completed at run-time.
APL, ambiguous granmkirs, parsing techniques, precedence parsing
Does APL Really Need Run-Time Parsing?
Most present APL implementations delay parsing until run- time, and indeed, APL does need some run-time parsing. But most of the parsing of APL statements can be done when the statements are entered. Statement entry-time parsing, where possible, is preferable since it gives the user hmediate detection of syntax errors, eliminates unnecessary interpretation overhead, and facilitates other optimizations such as reducing the amount of run- t h e checking,
In this paper we present a way to minimize the amount of run-time parsing done by an APL interpreter. We describe an entry-time Ifpartial parser" for APL statements and a run-time "parser completer." The partial parser that we describe is syntax- driven. It is known, however, that every grammar that describes the syntax of APL statements is ambiguous. Therefore the partial parser needs to make use of non-standard techniques to parse an ambiguous grammar. The general subject of parsing ambiguous grammars has recently received some attention in the literature
(2,3). Thus the methods used in solving this problem may be of some interest in their own right. The formal validation of soft- ware is a subject whose importance is now recognized. In another
paper (5), we present an algebraic treatment of programming languages and use it to prove that the distributed parsing method described
here is equivalent to the method in which all parsing i s accom- plished during interpretation. We feel that the algebraic approach presented there w i l l prove to be of general use in the study of syntax-based semantics of programming languages.
The Benefits of Statement Entry-Time Parsing
There i s a need for two types of APT, systems: "checkout" systems for program development and "optimiz...