Confluent Orthogonal Drawings of Syntax Diagrams

Bannister, Michael J. and Brown, David A. and Eppstein, David (2015) Confluent Orthogonal Drawings of Syntax Diagrams. In: Graph Drawing and Network Visualization: 23rd International Symposium, GD 2015, September 24-26, 2015, Los Angeles, CA, USA , pp. 260-271 (Official URL: http://dx.doi.org/10.1007/978-3-319-27261-0_22).

Full text not available from this repository.

Abstract

We provide a pipeline for generating syntax diagrams (also called railroad diagrams) from context free grammars. Syntax diagrams are a graphical representation of a context free language, which we formalize abstractly as a set of mutually recursive nondeterministic finite automata and draw by combining elements from the confluent drawing, layered drawing, and smooth orthogonal drawing styles. Within our pipeline we introduce several heuristics that modify the grammar but preserve the language, improving the aesthetics of the final drawing.

Item Type:Conference Paper
Classifications:J Applications > J.999 Others
P Styles > P.300 Curved
P Styles > P.480 Layered
P Styles > P.600 Poly-line > P.600.300 Mainly Orthogonal
S Software and Systems > S.120 Visualization
ID Code:1494

Repository Staff Only: item control page

References

Jensen, K., Wirth, N.: PASCAL User Manual and Report. Springer, New York (1974)

Burroughs Corporation: Command and Edit (CANDE) Language Information Manual (1971)

McCarthy, J.: LISP 1.5 Programmer’s Manual. MIT Press, Cambridge (1965)

Braz, L.M.: Visual syntax diagrams for programming language statements. SIGDOC Asterisk J. Comput. Doc. 14, 23–27 (1990)

Bell, S., Gilbert, E.J.: Learning recursion with syntax diagrams. SIGCSE Bull. 6, 44–45 (1974)

Goldberg, A., Robson, D.: Smalltalk-80: The Language and Its Implementation. Addison-Wesley Longman Publishing Co., Inc., Boston (1983)

Crockford, D.: Introducing JSON (2015). http://​json.​org. Accessed: 04 June 2015

Atkins, Jr., T., Sapin, S.: CSS Syntax Module Level 3 (2015). http://​www.​w3.​org/​TR/​css-syntax-3. Accessed: 04 June 2015

Dopler, M., Schörgenhumer, S.: EBNF Visualizer (2015). http://​dotnet.​jku.​at/​applications/​Visualizer. Accessed: 04 June 2015

Thiemann, P.: Ebnf2ps: Peter’s Syntax Diagram Drawing Tool (2015). http://​www2.​informatik.​uni-freiburg.​de/​thiemann/​haskell/​ebnf2ps. Accessed: 04 June 2015

Rademacher, G.: Railroad Diagram Generator (2015). http://​bottlecaps.​de/​rr/​ui. Accessed: 04 June 2015

Dickerson, M.T., Eppstein, D., Goodrich, M.T., Meng, J.Y.: Confluent drawings: visualizing non-planar diagrams in a planar way. In: Liotta, G. (ed.) GD 2003. LNCS, vol. 2912, pp. 1–12. Springer, Heidelberg (2004)

Sugiyama, K., Tagawa, S., Toda, M.: Methods for visual understanding of hierarchical system structures. IEEE Trans. Systems Man Cybernet. 11, 109–125 (1981)

Bastert, O., Matuszewski, C.: Layered drawings of digraphs. In: Kaufmann, M., Wagner, D. (eds.) Drawing Graphs. LNCS, vol. 2025, pp. 87–120. Springer, Heidelberg (2001)

Bekos, M.A., Kaufmann, M., Kobourov, S.G., Symvonis, A.: Smooth orthogonal layouts. J. Graph Algorithms Appl. 17, 575–595 (2013)

Eppstein, D., Goodrich, M.T., Meng, J.Y.: Confluent layered drawings. In: Pach, J. (ed.) GD 2004. LNCS, vol. 3383, pp. 184–194. Springer, Heidelberg (2005)

Hunt III, H.B., Rosenkrantz, D.J., Szymanski, T.G.: On the equivalence, containment, and covering problems for the regular and context-free languages. J. Comput. Syst. Sci. 12, 222–268 (1976)

Stockmeyer, L.J., Meyer, A.R.: Word problems requiring exponential time. In: Proceedings 5th ACM Symposium on Theory of Computing (STOC 1973), pp. 1–9 (1973)

Gramlich, G., Schnitger, G.: Minimizing NFA’s and regular expressions. J. Comput. Syst. Sci. 73, 908–923 (2007)

Champarnaud, J.M., Coulon, F.: NFA reduction algorithms by means of regular inequalities. Theor. Comput. Sci. 327, 241–253 (2004)

Han, Y.S., Wood, D.: Obtaining shorter regular expressions from finite-state automata. Theor. Comput. Sci. 370, 110–120 (2007)