Hostname: page-component-586b7cd67f-dsjbd Total loading time: 0 Render date: 2024-11-23T22:11:05.127Z Has data issue: false hasContentIssue false
  • English
  • Français

FUNCTIONAL PEARL Functional chart parsing of context-free grammars

Published online by Cambridge University Press:  27 October 2004

PETER LJUNGLÖF
PETER LJUNGLÖF
Affiliation:
Department of Computing Science, Göteborg University and Chalmers University of Technology, Gothenburg, Sweden (email: [email protected])
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

This paper implements a simple and elegant version of bottom-up Kilbury chart parsing (Kilbury, 1985; Wirén, 1992). This is one of the many chart parsing variants, which are all based on the data structure of charts. The chart parsing process uses inference rules to add new edges to the chart, and parsing is complete when no further edges can be added. One novel aspect of this implementation is that it doesn't have to rely on a global state for the implementation of the chart. This makes the code clean, elegant and declarative, while still having the same space and time complexity as the standard imperative implementations.

Type
Functional pearls
Information
Journal of Functional Programming , Volume 14 , Issue 6 , November 2004 , pp. 669 - 680
Copyright
© 2004 Cambridge University Press
Submit a response

Discussions

No Discussions have been published for this article.