Automatic parser generation for pictorial languages

While in a string grammar the only possible spatial relation is the string concatenation, in a positional grammar other spatial relations can be defined and then used for describing high dimensional languages. We characterize a new class of positional grammars, the extended pLALR grammars, which can be translated into traditional LALR context free grammars with positional actions. A positional action is a procedure implementing a spatial relation. In this way, the parser for an extended pLALR language can be generated automatically by the tool Yacc with no more effort. Moreover, we show that the class of extended pLALR grammars properly contains the class of pSLR grammars for which a Yacc implementation has already been given