More Web Proxy on the site http://driver.im/

research-article

Parsing Nonlinear Languages

Authors:

Maurizio Tucci,

Giuliana Vitiello,

Gennaro CostagliolaAuthors Info & Claims

IEEE Transactions on Software Engineering, Volume 20, Issue 9

Pages 720 - 739

https://doi.org/10.1109/32.317427

Published: 01 September 1994 Publication History

Abstract

The diagrammatic approach to user interfaces for computer-aided software development toolkits, visual query systems, and visual programming environments, is based on the use of diagrams and charts traditionally drawn on paper. In particular, the VLG system (Visual Language Generator) has been proposed to generate icon-oriented visual languages customized for given applications. The syntactical model underlying the interpretation of a visual language in VLG has been designed to describe icon-oriented visual languages. In order to enable the VLG system to apply to any kind of graphical languages, like diagrammatic ones, it is necessary to find a more general syntactical model able to support both their generation and interpretation. This paper addresses the comprehension of the features that a grammatical formalism for nonlinear languages must have to match any requirement for an efficient parsing. To this aim, relation grammars support an easy implementation of a general parsing algorithm for multidimensional languages, parametric with respect to the rewriting rules of the grammar. We compare the expressive power of relation grammars to grammatical formalisms for graph grammars.

References

[1]

{1} M. Angelaccio, T. Catarci, and G. Santucci, "QBD<sup>*</sup>: A graphical query language with recursion," IEEE Trans. Software Eng., vol. 16, no. 10, pp. 1150-1163, Oct. 1990.

Digital Library

[2]

{2} H. Bunke, "Graph grammars as a generative tool in image understanding," Lecture Notes on Comput. Sci. vol. 153, pp. 8-19.

Digital Library

[3]

{3} S. K. Chang, "A visual language compiler for information retrieval by visual reasoning," IEEE Trans. Software Eng., vol. 16, no. 10, pp. 1136-1149, Oct. 1990.

Digital Library

[4]

{4} S. K. Chang, M. J. Tauber, B. Yu, and J. S. Yu, "A visual language compiler," IEEE Trans. Software Eng., vol. 15, no. 5, pp. 506-525, May 1989.

Digital Library

[5]

{5} S. K. Chang, Ed., Visual Languages and Visual Programming. New York: Plenum Publishing, 1990.

Digital Library

[6]

{6} C. Crimi, A. Guercio, G. Pacini, G. Tortora, and M. Tucci, "Grammatical inference algorithms for the generation of visual languages," J. Visual Languages and Comput., vol. 1, pp. 355-368, 1990.

Digital Library

[7]

{7} C. Crimi, A. Guercio, G. Pacini, G. Tortora, and M. Tucci, "Automating visual language generation," IEEE Trans. Software Eng., vol. 16, no. 10, pp. 1122-1135, Oct. 1990.

Digital Library

[8]

{8} C. Crimi, A. Guercio, G. Nota, G. Pacini, G. Tortora and M. Tucci, "Relation grammars for modelling multidimensional structures," in Proc. IEEE Workshop Visual Languages, Skokie, IL, 1990, pp. 168-173.

[9]

{9} C. Crimi, A. Guercio, G. Nota, G. Pacini, G. Tortora and M. Tucci, "Relation grammars and their application to multidimensional languages," in J. Visual Languages and Comput, New York: Academic Press, 1991, vol. 2, pp. 333-346.

[10]

{10} P. Della Vigna and C. Ghezzi, "Context-free graph grammars," Inform. Contr., vol. 37, pp. 207-233, 1978.

[11]

{11} A. Ehrenfeucht and G. Rozenberg, "Restriction on NLC graph grammars," Theoretical Comput. Sci., vol. 31, pp. 211-223, 1984.

[12]

{12} F. Ferrucci, G. Pacini, G. Tortora, M. Tucci, and G. Vitiello, "Efficient parsing of multi-dimensional structures," in Proc. IEEE Workshop on Visual Languages, Kobe, Japan, Oct. 1991, pp. 105-110.

[13]

{13} M. Flasinski, "Characteristics of edNLC-graph grammars for syntactic pattern recognition," Comput. Vision, Graphics and Image Processing, vol. 47, pp. 1-21, 1989.

Digital Library

[14]

{14} M. Flasinski, "Parsing of edNLC-graph grammars for scene analysis," Pattern Recognit., vol. 21, no. 6, 1989, pp. 623-629.

Digital Library

[15]

{15} R. Franck, "A class of linearly parsable graph grammars," Acta Informatica vol. 10, 1978, pp. 175-201.

Digital Library

[16]

{16} E. P. Glinert and S. L. Tanimoto, "Pict: An interactive graphical programming environment," IEEE Comput., vol. 17, no. 11, pp. 7-25, Nov. 1984.

Digital Library

[17]

{17} E. J. Golin and S. P. Reiss, "The specification of visual language syntax," in Proc. IEEE Workshop on Visual Languages, Rome, Italy, Oct. 1989, pp. 105-110.

[18]

{18} M. Graf, "The design of a distributed system using a visual language," in Proc. IEEE Workshop on Languages for Automation, Vienna, Austria, Aug. 26-27, 1987, pp. 208-212.

[19]

{19} A. Habel and H. J. Kreowski, "Pretty patterns produced by hyperedge replacement," Lecture Notes on Computer Science, vol. 314, New York: Springer-Verlag, 1987, pp. 32-45.

Digital Library

[20]

{20} D. Harel, "StateCharts: A visual formalism for complex systems," Sci. of Comput. Programming, no. 8, pp. 231-274, 1987.

Digital Library

[21]

{21} R. Helm and K. Marriott, "Declarative specification of visual languages," in Proc. IEEE Workshop on Visual Languages, Skokie, IL, 1990, pp. 98-103.

[22]

{22} M. Hirakawa, M. Tanaka, and T. Ichikawa, "An iconic programming system, HI-VISUAL," IEEE Trans. Software Eng., vol. 16, no. 10, pp. 1178-1184, Oct. 1990.

Digital Library

[23]

{23} T. Ichikawa and S.-K. Chang, "Guest editors' introduction: visual programming," Special Section on Visual Programming, IEEE Trans. Software Eng., vol. 16, no. 10, p. 1105, Oct. 1990.

Digital Library

[24]

{24} R. J. K. Jacob, "A state transition diagram language for visual programming," IEEE Comput., vol. 18, no. 8, pp. 51-59, Aug. 1985.

Digital Library

[25]

{25} D. Janssens and G. Rozenberg, "On the structure of node-label controlled graph languages," Inform. Sci., vol. 20, pp. 191-216, 1980.

[26]

{26} D. Janssens and G. Rozenberg, "Graph grammars with node-label controlled rewriting and embedding," in Proc. 2nd Int. Workshop on Graph-Grammars and their Applicat. to Comput. Sci., H. Ehrig, M. A. Nagel, and G. Rozenberg, Eds., Osnabruk, West Germany, Oct. 1982. Lecture Notes on Computer Science, Berlin: Springer-Verlag, vol. 153, pp. 186-205, 1983.

Digital Library

[27]

{27} D. Janssens and G. Rozenberg, "On sequential and parallel node-rewriting graph grammars," Comput. Graphics and Image Processing, 18, 1982, pp. 279-304.

[28]

{28} M. Kaul, "Parsing of graphs in linear time," in Lecture Notes in Comput. Sci., vol. 153, 1983, pp. 206-218.

Digital Library

[29]

{29} H. J. Kreowski and G. Rozenberg, "On structured graph grammars I," Informat. Sci. vol. 52, pp. 185-210, 1990.

Digital Library

[30]

{30} H. J. Kreowski and G. Rozenberg, "On structured graph grammars II," Inform. Sci, vol. 52, 1990, pp. 221-246.

Digital Library

[31]

{31} P. McLain and T. D. Kimura, "Show and Tell user's manual," Washington Univ. Tech. Rep. WUCS-86-4, Mar. 1986.

[32]

{32} M. G. Main and G. Rozenberg, "Handle NLC grammars and R. E. languages," J. Comput. and Syst. Sci, vol. 35, pp. 192-205, 1987.

Digital Library

[33]

{33} M. Moriconi and D. F. Hare, "Visualizing program design through PegaSys," IEEE Comput., vol. 18, no. 8, Aug. 1985.

[34]

{34} T. Pavlidis, "Linear and context-free graph," J. ACM, vol. 19, no. 1, 1972, pp. 11-22.

Digital Library

[35]

{35} T. W. Pratt, "Pair grammars, graph languages and string-to-graph translation," J. Comput. Syst. Sci. vol. 5, 1971, pp. 560-595.

Digital Library

[36]

{36} S. R. Reiss, "Graphical program development with PECAN program development system," Sigplan Notices, vol. 19, no. 5, pp. 30-41, May 1984.

Digital Library

[37]

{37} G. Rozenberg and E. Welzl, "Boundary NLC graph grammars--basic definitions, normal forms, and complexity," Inform. Contr. vol. 69, pp. 136-167, 1986.

Digital Library

[38]

{38} R. V. Rubin, J. Walker, II, and E. J. Golin, "Early experience with the visual programmer's workbench," IEEE Trans. Software Eng., vol. 16, no. 10, pp. 1107-1121, Oct. 1990.

Digital Library

[39]

{39} Q. Y. Shi and K. S. Fu, "Parsing and translation of attribute expansive graph languages for scene analysis," IEEE Trans. Pattern Anal. Machine Intell., vol. 5, 1983, pp. 472-485.

Digital Library

[40]

{40} K. Wittenburg and L. Weitzman, "Visual grammars and incremental parsing for interface languages," in Proc. IEEE Workshop on Visual Languages, Skokie, IL, 1990, pp. 111-118.

[41]

{41} K. Wittenburg, "Earley-style parsing for relational grammars," in Proc. 1992 IEEE Workshop on Visual Languages, Seattle, WA, 1992, pp. 192-199.

Cited By

Huenerfauth MSears APontelli E(2005)Representing coordination and non-coordination in an american sign language animationProceedings of the 7th international ACM SIGACCESS conference on Computers and accessibility10.1145/1090785.1090796(44-51)Online publication date: 9-Oct-2005
https://dl.acm.org/doi/10.1145/1090785.1090796
Chok SMarriott K(2003)Automatic generation of intelligent diagram editorsACM Transactions on Computer-Human Interaction10.1145/937549.93755310:3(244-276)Online publication date: 1-Sep-2003
https://dl.acm.org/doi/10.1145/937549.937553
COSTAGLIOLA GOREFICE SPOLESE GTUCCI MTORTORA G(1999)On the generation of interactive iconic environmentsInternational Journal of Human-Computer Studies10.1006/ijhc.1999.024850:5(363-390)Online publication date: 1-May-1999
https://dl.acm.org/doi/10.1006/ijhc.1999.0248
Show More Cited By

Index Terms

Parsing Nonlinear Languages
1. Software and its engineering
  1. Software notations and tools
2. Theory of computation
  1. Formal languages and automata theory

Recommendations

A graph grammar approach to graphical parsing
VL '95: Proceedings of the 11th International IEEE Symposium on Visual Languages

We present a new graph grammar based approach for defining the syntax of visual languages and for generating visual language parsers. Its main advantage-in comparison to other visual language parsing approaches-is its ability to handle context-sensitive ...
DiaGen: a generator for diagram editors providing direct manipulation and execution of diagrams
VL '95: Proceedings of the 11th International IEEE Symposium on Visual Languages

Diagrams (e.g., flowcharts, trees for hierarchical structures, or graphs for finite state machines) are often needed as part of visual language systems and advanced user interfaces, and are frequently application specific. The implementation of editors ...
Automatic construction of user interfaces from constraint multiset grammars
VL '95: Proceedings of the 11th International IEEE Symposium on Visual Languages

Describes tools which automatically generate a sophisticated user interface from a constraint multiset grammar specification of a visual language. The user interface allows the user to construct diagrams in the visual language from primitive tokens such ...

Reviews

Reviewer: John A. N. Lee

The subject of this paper is actually a generator of icon-oriented visual languages—the Visual Language Generator (VLG) system, which features a grammatical formalism for nonlinear languages and multidimensional languages. The authors seek to show that their parser is efficient. In some respects, this paper begs to modify the definition of syntax to something like “a set of rules that provide the spatial relationships between objects in a language.” It goes on to discuss the features that a grammatical formalization must possess to support language generation and interpretation. The system chosen is relational grammars. The paper develops a set of transformational evaluation rules that fulfill the needs of the proposed system. The presentation is theoretical. As mentioned in the conclusion , “further work has to be done to make effective use of the new syntactic model.”

Access critical reviews of Computing literature here

Become a reviewer for Computing Reviews.

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image IEEE Transactions on Software Engineering

IEEE Transactions on Software Engineering Volume 20, Issue 9

September 1994

83 pages

ISSN:0098-5589

Editor:
Nancy G. Leveson
Univ. of Washington, Seattle

Issue’s Table of Contents

Copyright © Copyright © 1994 IEEE. All Rights Reserved.

Publisher

IEEE Press

Publication History

Published: 01 September 1994

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 23 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Huenerfauth MSears APontelli E(2005)Representing coordination and non-coordination in an american sign language animationProceedings of the 7th international ACM SIGACCESS conference on Computers and accessibility10.1145/1090785.1090796(44-51)Online publication date: 9-Oct-2005
https://dl.acm.org/doi/10.1145/1090785.1090796
Chok SMarriott K(2003)Automatic generation of intelligent diagram editorsACM Transactions on Computer-Human Interaction10.1145/937549.93755310:3(244-276)Online publication date: 1-Sep-2003
https://dl.acm.org/doi/10.1145/937549.937553
COSTAGLIOLA GOREFICE SPOLESE GTUCCI MTORTORA G(1999)On the generation of interactive iconic environmentsInternational Journal of Human-Computer Studies10.1006/ijhc.1999.024850:5(363-390)Online publication date: 1-May-1999
https://dl.acm.org/doi/10.1006/ijhc.1999.0248
Costagliola GDe Lucia AOrefice STortor G(1997)A Parsing Methodology for the Implementation of Visual SystemsIEEE Transactions on Software Engineering10.1109/32.63739223:12(777-799)Online publication date: 1-Dec-1997
https://dl.acm.org/doi/10.1109/32.637392
Ferrucci FTortora GTucci MVitiello G(1996)Semantics-Based Inference Algorithms for Adaptive Visual EnvironmentsIEEE Transactions on Software Engineering10.1109/32.54435122:10(730-750)Online publication date: 1-Oct-1996
https://dl.acm.org/doi/10.1109/32.544351
Ferrucci FPacini GSatta GSessa MTortora GTucci MVitiello G(1996)Symbol-Relation GrammarsInformation and Computation10.1006/inco.1996.0090131:1(1-46)Online publication date: 25-Nov-1996
https://dl.acm.org/doi/10.1006/inco.1996.0090

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents