current work on affix grammar code generators (Marc Seutter)
Mon, 18 Jan 1993 12:17:13 GMT

          From comp.compilers

Related articles
current work on affix grammar code generators (1993-01-11)
current work on affix grammar code generators (1993-01-18)
Re: current work on affix grammar code generators (1993-01-27)
| List of all articles for this month |

Newsgroups: comp.compilers
From: (Marc Seutter)
Organization: University of Nijmegen, The Netherlands
Date: Mon, 18 Jan 1993 12:17:13 GMT
Keywords: parse, bibliography
References: 93-01-062


The research group on affix grammars at the Catholic University of
Nijmegen (KUN) has for many years been concerned with "syntactic methods",
which comprizes both parsing methods and syntactic programming. Apart for
some work on LR(k) and LC(k) parsing, most of the research has affix
grammars as either the object or the means of research.

We consider affix grammars as a broad family of two-level grammars, which
have in common the distinction of a lower level of CF rules (or, rather,
rule schemata) and a upper level of (restricted) CF rules serving to
define the domains of affixes. coupled by the "consistent substitution"
rule. The lower level also involves operations on the affixes, which may
be sugared away to the parameter positions. Affix grammars may be
interpreted deterministically or nondeterministically, according to
certain wellformedness rules imposed upon them.

The various members of the family are thus obtained by making different
choices, as shown in the following table for a number of formalisms:

deterministic domain operations name of formalisms
yes integers open-ended CDL1, CDL2
yes,2-pass terms,INT,TEXT guards CDL3
nondet. strings split, join EAG
nondet. powersets guards AGFL

CDL (1, 2 and now 3) is the workhorse for syntactic programming. CDL1
(1970) was a compiler compiler formalism, which gave us the first
impression of the force of syntactic programming. CDL2 (1974) was a System
Implementation Language, complete with extensive mechanisms for
modularity, portability and the generation of efficient code on highly
divers machines. It was available in the form of a very powerful
programming environment. CDL3 (1991) was the result of collaboration with
Jean Beney from Lyon, bringing together the CDL and (STAR)LET lines. It is
now our standard implementation for all compiler development, even though
the working environment is by no means completed.

EAG is a formalism with the power and much of the flavour of PROLOG, which
is intended as a specification formalism. It has been used in describing
very complicated formalisms and generating a prototype implementation. An
efficient implementation of this formalism is currently under development.
In the near future we will be concerned with the transformational
development of CDL3 programs from EAG specifications.

AGFL is a formalism intended for the syntactic description of natural
languages. It is being used by the linguistic department at KUN for the
description of English, Dutch, Spanish, Modern Standard Arabic and German,
whereas other groups use it for Modern Greek and Russian. We have
developed a Parser Generator for AGFL, generating very efficient parsers,
and a Grammar Work Bench for the development of grammars for natural

Let me end this short overview with a short bibliography of recent papers.
I hope to have shown that my small group at KUN (4 persons) still manages
to find much of its inspration in the study, implementation and use of
Affix Grammars.
C.H.A. Koster


Meijer, H., The Project on Extended Affix Grammars at
Nijmegen. In: Attribute Grammars and their Applications (P.
Deransart, M. Jourdan, eds.), proceedings WAGA, Paris, ,

C.H.A. Koster - Affix Grammars for Natural Languages.
In: H. Alblas & B. Melichar (Eds.), Attribute Grammars,
applications and systems. Springer Lecture Notes in Computer
Science 545, Heidelberg, pag. 469-484.

E. Farkas, C.H.A. Koster, P. Koves & M. Naszodi, Towards an
Affix Grammar for the Hungarian language. In: A. Gyoergy
(Ed.), Proceedings CIS '91 conference on intelligent
Systems. John von Neumann Society for Computing Sciences,
Budapest 1991, pag. 233-246.

C.H.A. Koster & R. Willems, Towards an Affix Grammar for
Turkish. In: M. Baray & B. Ozguc (Eds.), Computer and
Information Science VI, Elsevier, Amsterdam 1991, pag. 1067-
1076. .

C. Dekkers, C.H.A. Koster, M.-J. Nederhof & A. van Zwol, GWB
- Manual for the Grammar Work Bench Version 1.0.
Technical Report no. 91-28, Dept. of Informatics, University
of Nijmegen, december 1991, 12 pag..

J.M.I.M. Leo, A general Context-Free Parsing Algorithm
running in linear time on every LR(k) Grammar without using
Lookahead, Theoretical Computer Science 82, 1991, pp 165-176.

C.H.A. Koster - Affix Grammars for Programming languages,
In: H. Alblas & B. Melichar (Eds.); Attribute Grammars,
Applications and Systems, SLNCS 545, Springer Verlag 1991,
pp 358-373.

C.H.A. Koster - On the Borderline between Grammars and
Programs, In: Proceedings PLILP'91, Passau, 12 pp.

Nederhof, M.J., Left Corner Parsing Rehabilitated. Accepted
by Theoretical Computer Science.

{M. van den Brand,
``PREGMATIC, A generator for incremental programming environments",\\
Ph.D. thesis, University of Nijmegen, 1992.}


Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.