Parsing of edNLC-graph grammars for scene analysis

摘要

An edNLC-graph grammar, introduced by Janssens,(4) is a strong formalism for generating scene representations. This grammar generates directed node- and edge-labelled graphs, EDG-graphs. A method of construction of unambiguous string EDG-graph representation is briefly described. The characteristics of edNLC-graph grammar for syntactic pattern recognition allows us to construct the parsing algorithm. The deterministic top-down syntax analyzer is constructed for the subfamily of an edNLC-graph grammar, called an ETL/1-graph grammar. An ETL/1-graph grammar is parallel to a finite state string grammar. The notions introduced in the paper are useful for researches in less restricted edNLC-graph grammars, for example grammars analogical to context-free string grammars.