Home Table of Contents News Blogs Opinion Research Practice Contributed Articles Review Articles Careers Archive Videos About Communications
Sign In
advertisement

Home → Magazine Archive → August 1972 (Vol. 15, No. 8) → Generating parsers for affix grammars → Abstract

Generating parsers for affix grammars

By David Crowe

Communications of the ACM, Vol. 15 No. 8, Pages 728-734
10.1145/361532.361539

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.

The full text of this article is premium content

0 Comments

No entries found