Access Restriction

Author Crowe, David
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Language English
Subject Keyword Floyd production language ♦ Bottom-up parsing ♦ Parsing ♦ Syntax directed compiling ♦ Algorithmic language processing ♦ Translator writing systems ♦ Two-level grammars
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.
Description Affiliation: Univ. of British Columbia, Vancouver, British Columbia, Canada (Crowe, David)
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2005-08-01
Publisher Place New York
Journal Communications of the ACM (CACM)
Volume Number 15
Issue Number 8
Page Count 7
Starting Page 728
Ending Page 734

Open content in new tab

   Open content in new tab
Source: ACM Digital Library