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

fYear

1994

fDate

4-7 Oct 1994

Firstpage

245

Lastpage

252

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;

fLanguage

English

Publisher

ieee

Conference_Titel

Visual Languages, 1994. Proceedings., IEEE Symposium on

Conference_Location

St. Louis, MO

Print_ISBN

0-8186-6660-9

Type

conf

DOI

10.1109/VL.1994.363611

Filename

363611