Commentary by cpressey on Linguistics works

Essentials of English Grammar

English Transformational Grammar

Modern English Linguistics

Towards a Semantic Description of English

An Introduction to Unification-based Approaches to Grammar

Unification grammars are sort of semantics-based (instead of syntax-based) grammar for language. We have these "feature structures" or "functional descriptions" which are, basically, dictionaries; keys are atoms and values can be atoms or further functional descriptions. These structures also have a worked-out notation in the literate, which depicts the nesting.

The idea, for parsing, is just to successively unify these structures with the input. This is "monotonic" in the sense that the structure keeps building up. This allows things like agreement to happen (the number/etc word must agree with the context it is in, or vice versa).

The idea evolves over time but seems to keep going under different names. In general they are called "unification-based grammars". Wikipedia has an entry about https://en.wikipedia.org/wiki/Model-theoretic_grammar which seems to be the same thing.

An interesting upshot of this is that the syntax is "just another feature" of the... underlying semantic lexical item.

Another is that the parsing order doesn't really matter (as long as you know which words go with which).

A less interesting upshot is that if you get all reductionist about it, it seems to reduce to... "just Prolog programming". More generously, it is a restricted style of Prolog programming, perhaps. But it's reversible for the same reason Prolog is.

While the idea very elegantly explains certain kinds of agreement and so forth in natural language, in a way that the languages of (and nestled inside) the Chomsky hierarchy don't, there are real real performance issues with general parsing algorithms for these structures. I believe that is why they don't generally get as much attention.

The Language Complexity Game

CFG is in P but is not P-complete.

But CFG is not quite enough it seems.

CSG is PSPACE-complete. That's way too big.

It makes sense that evolutionarily there would be a tension between maximizing expressivity and minimizing complexity.

Thus, the mildly context-sensitive languages.

RCG is P-complete.

ACL Anthology - ACL Anthology