Browse Prior Art Database

The Cellar Principle of State Transition and Storage Allocation

IP.com Disclosure Number: IPCOM000129633D
Original Publication Date: 1990-Dec-31
Included in the Prior Art Database: 2005-Oct-06
Document File: 10 page(s) / 41K

Publishing Venue

Software Patent Institute

Related People

F. L. Bauer: AUTHOR [+2]

Abstract

The grammar of arithmetic formulas was the pilot example for developing parsing techniques for Chomsky grammars. It is shown how stacks were introduced and how they tufted out to be powerful instruments within compilers by controlling state transitions at compile time and storage allocation at run time.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 11% of the total text.

Page 1 of 10

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

Copyright ©; 1990 by the American Federation of Information Processing Societies, Inc. Used with permission.

The Cellar Principle of State Transition and Storage Allocation

F. L. Bauer

(Image Omitted: Authors Address: Villenstrasse 19, D-8081 Kottgeisering; West Germany.)

The grammar of arithmetic formulas was the pilot example for developing parsing techniques for Chomsky grammars. It is shown how stacks were introduced and how they tufted out to be powerful instruments within compilers by controlling state transitions at compile time and storage allocation at run time.

Categories and Subject Descriptors: K.2 [Computing Milieux]: History of Computing -- hardware, people, software, systems, theory. D.3. 1 [Software]: Programming Languages -- former definitions and theory; syntax. F.4.2 [Theory of Computation]: Mathematical Logic and Formal Language -- grammars and other rewriting systems, Parsing.

General Terms -- Algorithms, Languages, Theory.

Additional Terms -- Chomsky Grammars, Parsing Techniques, Compilers, Stacks.

Formal Description of Formulas

As late as 1930, no mathematician felt a need for a formal description of the syntax of arithmetical or other formulas: common usage was "clear." Logicians, however, with their desire to question everything, were not that easily satisfied. Jan Lukasiewicz's and Alfred Tarski's parenthesis-free Polish notation appeared in 1930's (Lukasiewicz 1930), and in the same year Karl Menger (Menger 1935) gave a talk at a colloquium entitled "Eine elementare Bemerkung uber die Struktur logischer Formeln" (An Elementary Remark on the Structure of Logical Formulas). For the special case of binary connectors, Menger stated a formation rule.l1

In 1943, Karl Schroter generalized the rule to arbitrary n-ary connectives (Schroter, 1943) 22 In more modern wording, "a parenthesis-free formula is well formed, if its rank is 1 and if the rank of every proper tail of that formula is greater than 1." The rank of a formula is intuitively defined to be an additive function over the string, where the rank of a variable is 1, the rank of a n- ary connective is 1-n (Figure 1). The rule was rediscovered in 1948 by D.C. Gerneth. Philip Hall also devoted some interest to this subject (Rosenbloom 1950 p. 205). Paul Rosenbloom, in 1950, recognized the syntactical importance of the formation rule and used it for his definition of a simple language (Rosenbloom 1950 p. 154).

Angstl's Proposal

1 1 According to a note in one of Lukasiewicz's papers, Adjukiewicz obtained it independently [Rosenbloom 1950].

2 2 Schroter was possibly not aware of Kleene in 1934 (proof by cases in formal logic. Annals of Mathematics 35, pp. 529544) and Church in 1941 (The calculi of lambda conversions. Annals of Mathematics Studies No. 6 Princeton (1941) dealing incidentally with the subject.)

IEEE Computer Society, Dec 31, 1990 Page 1 IEEE Annals of the History of Computing Volum...