Search

We propose and study a model of the graphical syllable using Marcus contextual grammars. For this purpose we introduce two new variants of Marcus contextual grammars: total Marcus contextual grammar with total leftmost derivation, and total Marcus contextual grammar with total leftmost derivation constrained by maximal use of selectors.

Given two context-free grammars (CFGs), G1 and G2, the language generated by the union of the grammars is not the union of the languages generated by each grammar: L(G1∪ G2)≠ L(G1∪ L(G2). In order to account for modularity of grammars, another way of defining the meaning of grammars is needed. This paper adapts results from the semantics of logic programming languages to CFGs. We discuss alternative approaches for defining the denotation of a grammar, culminating in one which we show to be both compositional and fully-abstract. We then show how grammar modules can be defined such that their semantics retains these desirable properties. This gives a clear, mathematically sound way for composing parts of grammars.

In this paper, we investigate various concepts of leftmost derivation in grammars controlled by bicoloured digraphs, paying specific attention to their descriptive capacity. This approach allows us to unify the presentation of known results regarding especially programmed and matrix grammars, and to obtain new results concerning grammars with regular control, and periodically time-variant grammars. Moreover, we consider leftmost derivations in grammars with (regular) context conditions.

The concept of cooperation and distribution as known from the area of grammar systems is introduced to graph grammars; more precisely, to hyperedge replacement (for short, HR) grammars. This can be seen as a modest approach to controlled HR. Two different derivation modes are considered, the so-called t-mode and the =k-mode. For the t-mode it is shown that the class of hypergraph languages obtained is equal to the class of ET0L HR languages which is a natural generalization of the class of ET0L languages to hypergraphs.

In this paper we present a grammar formalism for the generation and parsing of two-dimensional symbolic languages. Linear Positional Grammars (or LPGs for short) are an immediate generalization of the context-free string grammars. Through the use of general spatial relations they allow the definition of pictures whose symbols span on a two-dimensional space. Due to their analogy to context-free string grammars, LPGs can be used to construct an LR-based parser which uses the spatial relations to navigate the input. We study ambiguous grammars and present several ways to solve them. Moreover we provide an algorithm to translate a linear positional grammar into a context-free grammar with actions and suggest a general methodology to parse two-dimensional symbolic languages by making use of the well-known tool YACC (Yet Another Compiler-Compiler [25]). As an example, we construct a parser for a subset of the two-dimensional arithmetical expression language.

The aim of this paper is to start investigations on the possibilities of introducing a structure in the strings generated by internal contextual grammars. First, we consider the idea of associating a tree to a derivation in such a grammar. This can be done in a natural way, by associating parentheses to the contexts of the grammar. In this way we obtain a restriction on the derivation in a contextual grammar, as well as a direct manner of defining the ambiguity of contextual grammars. Then, we consider a relation on the set of symbols appearing in a string, in the sense already used in descriptive linguistics. By starting from a set of axioms which are structured strings and adjoining to them contexts as usual in contextual grammars, but having prescribed dependences between their symbols, we obtain a set of structured strings. By imposing conditions on the structure of the strings (crossed-noncrossed dependences, a tree structure, a link structure in the sense of link grammars, etc), we obtain a restriction on the derivation in a contextual grammar, as well as a direct manner of defining the structure of languages generated by contextual grammars. The linguistic relevance of these structures associated to strings generated by contextual grammars remains to be further explored.