David Crowe
Abstract
Affix grammars are two-level grammars which are similar to van Wijngaarden's two-level grammars used in the definition of Algol 68. Affix grammars are shown by Koster to be equal in power to van Wijngaarden grammars. They are much more suited to parsing than are the latter, however. Koster, the inventor of affix grammars, suggests a top-down scheme for parsing them, based on recursive procedures. This paper presents a bottom-up scheme for parsing them, based on an extension of Floyd Production Language (FPL). Included is an algorithm, similar to that of DeRemer's, for converting a large class of affix grammars into FPL. The paper concludes by discussing briefly the applicabilities of the conversion algorithm and affix grammars in general, and some possible extensions to Koster's definition of affix grammars.
- 1 DeRemer, F.L. Generating parsers for BNF grammars. Proc. AFIPS 1969 SJCC, Vol. 34, AFIPS Press, Montvale, N.J., pp. 795-799.Google Scholar
- 2 Floyd, R. A descriptive language for symbol manipulation. J. ACM 8, 4 (Oct. 1961), 579-584. Google ScholarDigital Library
- 3 Koster, C.H.A. Affix grammars. In ALGOL 68 Implementation, North-Holland Pub. Co., Amsterdam, 1971, p. 95.Google Scholar
- 4 Koster, C.H.A. Two-level Grammars. Seminar on Automata and Mathematical Linguistics, Mathematisch Instituut, Budapest, May 1970.Google Scholar
- 5 Koster, C.H.A. Syntax-directed parsing of ALGOL 68 programs. Proc. Informal Conf. on ALGOL 68 Implementation, U. of British Columbia, Vancouver, Aug. 1969.Google Scholar
Recommendations
Regular right part grammars and their parsers
This paper introduces an alternative to context-free grammars called regular right part (RRP) grammars, which resemble PASCAL syntax diagrams. Formally, RRP grammars have production right parts, which are nondeterministic finite state machines (FSMs), ...
Deterministic parsing of ambiguous grammars
Methods of describing the syntax of programming languages in ways that are more flexible and natural than conventional BNF descriptions are considered. These methods involve the use of ambiguous context-free grammars together with rules to resolve ...
Left recursion in Parsing Expression Grammars
Parsing Expression Grammars (PEGs) are a formalism that can describe all deterministic context-free languages through a set of rules that specify a top-down parser for some language. PEGs are easy to use, and there are efficient implementations of PEG ...
Comments