Abstract
Many applications make use of diagrams to represent complex objects. In such applications it is often necessary to recognise how some diagram has been pieced together from other diagrams. Examples are electrical circuit analysis, and program understanding in the plan calculus (Rich, 1981). In these applications the recognition process can be formalised as flowgraph parsing, where a flowgraph is a special case of a plex (Feder 1971) . Nodes in a flowgraph are connected to each other via intermediate points known as tie-points. Lutz (1986, 1989) generalised chart parsing of context-free string languages (Thompson – Ritchie, 1984) to context-free flowgraph languages, enabling bottom-up and top-down recognition of flowgraphs. However, there are various features of the plan calculus that complicate this - in particular attributes, structure sharing, and relationships between tie-points. This paper will present a chart parsing algorithm for analysing graphs with all these features, suitable for both program understanding and digital circuit analysis. For a fixed grammar, this algorithm runs in time polynomial in the number of tie-points in the input graph.- Anthology ID:
- 1993.iwpt-1.14
- Volume:
- Proceedings of the Third International Workshop on Parsing Technologies
- Month:
- August 10-13
- Year:
- 1993
- Address:
- Tilburg, Netherlands and Durbuy, Belgium
- Editors:
- Harry Bunt, Robert Berwick, Ken Church, Aravind Joshi, Ronald Kaplan, Martin Kay, Bernard Lang, Makoto Nagao, Anton Nijholt, Mark Steedman, Henry Thompson, Masaru Tomita, K. Vijay-Shanker, Yorick Wilks, Kent Wittenburg
- Venue:
- IWPT
- SIG:
- SIGPARSE
- Publisher:
- Association for Computational Linguistics
- Note:
- Pages:
- 145–170
- Language:
- URL:
- https://aclanthology.org/1993.iwpt-1.14
- DOI:
- Cite (ACL):
- Rudi Lutz. 1993. Chart Parsing of Attributed Structure-Sharing Flowgraphs with Tie-Point Relationships. In Proceedings of the Third International Workshop on Parsing Technologies, pages 145–170, Tilburg, Netherlands and Durbuy, Belgium. Association for Computational Linguistics.
- Cite (Informal):
- Chart Parsing of Attributed Structure-Sharing Flowgraphs with Tie-Point Relationships (Lutz, IWPT 1993)
- PDF:
- https://preview.aclanthology.org/nschneid-patch-4/1993.iwpt-1.14.pdf