Efficient parsing of visual languages based on critical pair analysis and contextual layered graph transformation

摘要

This paper proposes an extension of layered graph grammars (LGGs) which have been introduced for the definition of visual languages (VLs). Offering new constructs like negative application conditions (NACs) it allows one to produce iii ore concise VL definitions. A new layering condition and critical pair analysis are the prereguisites for a new parsing algorithm which avoids the exponential behaviour of LGGs in many cases.