  Graph-based semantic representations are valuable in natural language
processing, where it is often simple and effective to represent linguistic
concepts as nodes, and relations as edges between them. Several attempts has
been made to find a generative device that is sufficiently powerful to
represent languages of semantic graphs, while at the same allowing efficient
parsing. We add to this line of work by introducing graph extension grammar,
which consists of an algebra over graphs together with a regular tree grammar
that generates expressions over the operations of the algebra. Due to the
design of the operations, these grammars can generate graphs with
non-structural reentrancies; a type of node-sharing that is excessively common
in formalisms such as abstract meaning representation, but for which existing
devices offer little support. We provide a parsing algorithm for graph
extension grammars, which is proved to be correct and run in polynomial time.
