Title :
A predictive parser for visual languages specified by relation grammars
Author :
Ferrucci, F. ; Tortora, G. ; Tucci, M. ; Vitiello, G.
Author_Institution :
Dipartimento di Inf. ed Applicazioni, Salerno Univ., Italy
Abstract :
We define a class of relation grammars that satisfy the context-freeness property, which is an essential condition to solve the membership problem in polynomial time. The context-freeness property is used to design a predictive parsing algorithm for such grammars. The algorithm has a polynomial time behaviour when applied to grammars which generate languages having the additional properties of connections and degree-boundedness. One remarkable result is that a polynomial time complexity is obtained without imposing (total or partial) ordering on the symbols of input sentences
Keywords :
computational complexity; context-free grammars; graphical user interfaces; visual languages; visual programming; connections; context-freeness property; degree-boundedness; input sentences; membership problem; polynomial time; polynomial time behaviour; polynomial time complexity; predictive parser; predictive parsing algorithm; relation grammars; specification; symbols; visual languages; Algorithm design and analysis; Computer languages; Multidimensional systems; Performance analysis; Polynomials; Prediction algorithms; Predictive models; Production; Roentgenium; Tree graphs;
Conference_Titel :
Visual Languages, 1994. Proceedings., IEEE Symposium on
Conference_Location :
St. Louis, MO
Print_ISBN :
0-8186-6660-9
DOI :
10.1109/VL.1994.363611
