Head grammar (HG) is a grammar formalism introduced in
Carl Pollard
Carl Jesse Pollard (born June 28, 1947) is a Professor of Linguistics at the Ohio State University. He is the inventor of head grammar and higher-order grammar, as well as co-inventor of head-driven phrase structure grammar (HPSG).
He is current ...
(1984)
[ Pollard, C. 1984. ''Generalized Phrase Structure Grammars, Head Grammars, and Natural Language''. Ph.D. thesis, Stanford University, CA.] as an extension of the
context-free grammar
In formal language theory, a context-free grammar (CFG) is a formal grammar whose production rules are of the form
:A\ \to\ \alpha
with A a ''single'' nonterminal symbol, and \alpha a string of terminals and/or nonterminals (\alpha can be empt ...
class of grammars. Head grammar is therefore a type of
phrase structure grammar
The term phrase structure grammar was originally introduced by Noam Chomsky as the term for grammar studied previously by Emil Post and Axel Thue (Post canonical systems). Some authors, however, reserve the term for more restricted grammars in the ...
, as opposed to a
dependency grammar
Dependency grammar (DG) is a class of modern grammatical theories that are all based on the dependency relation (as opposed to the ''constituency relation'' of phrase structure) and that can be traced back primarily to the work of Lucien Tesnià ...
. The class of head grammars is a subset of the
linear context-free rewriting systems.
One typical way of defining head grammars is to replace the terminal strings of CFGs with indexed terminal strings, where the index denotes the "head" word of the string. Thus, for example, a CF rule such as
might instead be
, where the 0th terminal, the ''a'', is the head of the resulting terminal string. For convenience of notation, such a rule could be written as just the terminal string, with the head terminal denoted by some sort of mark, as in
.
Two fundamental operations are then added to all rewrite rules: wrapping and concatenation.
Operations on headed strings
Wrapping
Wrapping is an operation on two headed strings defined as follows:
Let
and
be terminal strings headed by ''x'' and ''y'', respectively.
Concatenation
Concatenation is a family of operations on n > 0 headed strings, defined for n = 1, 2, 3 as follows:
Let
,
, and
be terminal strings headed by ''x'', ''y'', and ''z'', respectively.
And so on for
. One can sum up the pattern here simply as "concatenate some number of terminal strings ''m'', with the head of string ''n'' designated as the head of the resulting string".
Form of rules
Head grammar rules are defined in terms of these two operations, with rules taking either of the forms
where
,
, ... are each either a terminal string or a non-terminal symbol.
Example
Head grammars are capable of generating the language
. We can define the grammar as follows:
The derivation for "abcd" is thus:
And for "":
Formal properties
Equivalencies
Vijay-Shanker and Weir (1994)
[Vijay-Shanker, K. and Weir, David J. 1994. ''The Equivalence of Four Extensions of Context-Free Grammars''. Mathematical Systems Theory 27(6): 511-546.] demonstrate that
linear indexed grammars
Linearity is the property of a mathematical relationship (''function'') that can be graphically represented as a straight line. Linearity is closely related to '' proportionality''. Examples in physics include rectilinear motion, the linear r ...
,
combinatory categorial grammar
Combinatory categorial grammar (CCG) is an efficiently parsable, yet linguistically expressive grammar formalism. It has a transparent interface between surface syntax and underlying semantic representation, including predicate–argument structur ...
,
tree-adjoining grammar
Tree-adjoining grammar (TAG) is a grammar formalism defined by Aravind Joshi. Tree-adjoining grammars are somewhat similar to context-free grammars, but the elementary unit of rewriting is the tree rather than the symbol. Whereas context-free gra ...
s, and head grammars are
weakly equivalent formalisms, in that they all define the same string languages.
References
{{DEFAULTSORT:Head Grammar
Formal languages
Grammar frameworks
Syntax