transparent gif


Ej inloggad.

Göteborgs universitets publikationer

Pure Functional Parsing - an advanced tutorial

Författare och institution:
Peter Ljunglöf (Institutionen för data- och informationsteknik, datavetenskap (GU))
Utgiven i serie vid Göteborgs universitet:
Technical report L - School of Computer Science and Engineering, Chalmers University of Technology, ISSN 1651-4963; nr 6L
Antal sidor:
154 pages
Chalmers University of Technology
Datum för examination:
Paul Callaghan, University of Durham
Inkluderade delarbeten:
Sammanfattning (abstract):
Parsing is the problem of deciding whether a sequence of tokens is recognized by a given grammar, and in that case returning the grammatical structure of the sequence. This thesis investigates di erent aspects of the parsing problem from the viewpoint of a functional programmer. It is conceptually divided into two parts, discussing the parsing problem from di erent perspectives; rst as a comprehensive survey of possible implementations of combinator parsers; and second as pure functional implementations of standard context-free parsing algorithms. The rst part of the thesis is a survey of the possible implementations of combinator parsers that have previously been suggested in the litterature, relating their dirrefent usages. A number of previously unknown parser implementations are also given, especially e cient for small and medium-sized natural language applications. The second part of the thesis de ne elegant and declarative, pure functional versions of some standard parsing algorithms for context-free grammars. The goal has been to implement the algorithms in a way that is close to their intuitive formulations, not sacri cing computational e ciency. The implementations only use simple data structures not relying on a global updateable state, thus opening the way for nice functional implementations. Finally the thesis implements parser combinators that can collect the grammatical structure in the program, to be able to use any suitable parsing algorithm and not just recursive descent. However, this requires an mildly impure extension of the host language Haskell.
Ämne (baseras på Högskoleverkets indelning av forskningsämnen):
Data- och informationsvetenskap ->
Datavetenskap (datalogi) ->
Data- och informationsvetenskap ->
Språkteknologi (språkvetenskaplig databehandling)
context-free grammars, parsing algorithms, parser combinators, functional programming
Postens nummer:
Posten skapad:
2006-09-28 10:24
Posten ändrad:
2013-01-10 12:56

Visa i Endnote-format

Göteborgs universitet • Tel. 031-786 0000
© Göteborgs universitet 2007