Associative Language Descriptions

The Associative Language Description (ALD) model is a combination of
locally testable and constituent structure ideas. In practice it may equal context-free
grammars in explanatory adequacy,yet it provides a simple description and it excludes
mathematical sets based on counting properties,which are rarely (if ever) used in compiler construction

or in computational linguistics.
The ALD model is an approach consistent with current views on brain organization.
ALD is a “pure ”, i.e.,nonterminal-free definition.

People : Alessandra Cherubini, Stefano Crespi-Reghizzi, Matteo Pradella, Pierluigi San Pietro

Main publications

1) Cherubini, S. Crespi Reghizzi and P. Sanpietro, "Languages based on
structural local testability", in C.S. Calude and M.J. Dinneen (eds),
Combinatorics computation and logic, Springer 1999.

2) S. Crespi Reghizzi, M. Pradella and P.L. San Pietro, "Conciseness of
associative language descriptions", Proc. Workshop Descriptional
Complexity of Automata, Grammars and Related Structures, Magdeburg, 1999.

3) S. Crespi Reghizzi, M. Pradella and P.L. San Pietro, "Associative
definitions of programming languages", Computer Languages, 26, 2001,
105-123.

4) S. Crespi Reghizzi, A. Cherubini and P.L. San Pietro,
“Structural Properties of Associative Language Descriptions”, in A.
Restivo, S. Ronchi Della Rocca and L. Roversi (eds), Theoretical
Computer Science ICTCS 2001, LNCS 2202, Springer Verlag, 2001, 172-183.

5) A. Cherubini, S. Crespi Reghizzi, and P.L. San Pietro, Associative
Language Descriptions, Theoretical Computer Science, 270, 2002,463-491.

6) S. Crespi-Reghizzi and V. Braitenberg "Towards a brain compatible
theory of syntax based on local testability” in C. Martin-Vide and
V. Mitrana (eds), Grammars and Automata for String Processing: from
Mathematics and Computer Science to Biology, and Back, Taylor and
Francis, Topics in Computer Mathematics 9, London, 2003, p. 17-32

7) Christian Biasini and Stefano Crespi Reghizzi, Associative Language Parsing, Tech.Report, DEI-Polimi, 2004.

Examples of ALD Grammars

A large fragment of Java as hypertext

Pascal

ALD parsing tools

A parser generator, with LaTex documentation facilities.