View Source Document

Chris Pressey.md

Commentary by Chris Pressey

This work is distributed under a CC-BY-ND-4.0 license, with the following explicit exception: the ratings may be freely used for any purpose with no limitations.

Attribute Grammars

A Compiler Generator for Microcomputers

Introduces Coco; and its language Cocol. Also, it contains a formal definition of attribute grammars, in section 3.4. However, as it notes, there are many ways to define attribute grammars, and it is merely following Waite and Goos [1984] ("Compiler Construction", Springer-Verlag).

Like 400 pages but like half the book is program listings. Coco was written in Modula-2.

This is not Coco/R (yet (?)). The generated parser is not recursive descent, it is table-driven. The input grammar is reduced to "G-code" which is like an abstract machine for parsing (like WAM is a abstract machine for Prolog).

Semantics of Context-Free Languages

As reflected in the title, Knuth doesn't regard this as a way to bump up the power of the grammar to context-sensitive by having the parsing be affected at all by the attributes; he only regards them as providing a semantics, once collected.

Knuth concedes the technique has been used by previous authors but wants to examine its structure. He gives an attribute grammar that calculates the value of a rational number given in binary. First he uses synthesized attributes. He then compares it to an equivalent solution using inherited attributes.

The following statement later on in the paper:

By contrast, the above definition of Turingol defines each con- struction of the language only in terms of its "immediate environment", minimizing to a large extent the interconnections between the definitions of different parts of the language.

reminded me of "On the Structure of Context-Sensitive Grammars", and its sending "signals" across the string-space to access context; which also brought to mind Kolmogorov machines. It's much more efficient to have direct links to the state (context) that you need to heed (or update) when parsing. (It doesn't fundamentally change the complexity class though; "reasonable models of computation are polynomially closed.")

Higher order attribute grammars | Proceedings of the ACM SIGPLAN 1989 conference on Programming language design and implementation

.

Ch 3.4 Attribute Grammars

.

christoff-buerger/racr: Metacompiler library supporting incremental transformation based on reference attribute grammar controlled rewriting.

.