Associative definition of programming languages

Associative language descriptions (ALD) are a recent grammar model, theoret ically less powerful than context free (CF) grammars, but adequate for desc ribing the syntax of programming languages. ALD does not use nonterminal sy mbols, but rely on permissible contexts for specifying valid syntax trees. In order to assess ALD adequacy, we analyze the descriptional complexity of structurally equivalent CF and ALD grammars, finding comparable measures. The compression obtained using CF copy rules is matched by context inherita nce in ALD. The family of hierarchical parentheses languages, an abstract p aradigm of HTML, and of expressions with operator precedences is studied. A complete ALD grammar of Pascal testifies of the practicality of the ALD ap proach. (C) 2001 Elsevier Science Ltd. All rights reserved.