Skip to content
/ LERGC Public

Lazy Evaluation Recursive Grammar Combinators for Clojure

Notifications You must be signed in to change notification settings

lambder/LERGC

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

2 Commits
 
 
 
 
 
 

Repository files navigation

LERGC - is Lazy Evaluation Recursive Grammar Combinators for Clojure.
It is inspired by Monadic Parser Combinators (Hutton & Meijer 1996; http://www.itu.dk/~carsten/courses/f02/handouts/MonadicParserCombinators.pdf)
which shows how to build parser combinators in Gofer (statically typed, lazy functional language).
The LERGC implementation differs from the Gofer one since Clojure is not lazy. Laziness was realised by changing the monadic value signature
in state monad from 'S -> [V, S]' to 'unit -> S -> [V, S]', so monadic values combinators execute them only as required.
Another addition is that of representing failed computation (parser not matching). Rather than representing the failure as universal zero, it is represented
 as variant in 'Either' data type, here in Clojure implemented as closures (see: Error-handling Monads http://mvanier.livejournal.com/5103.html).

The state is not just simple string of characters but a structure denoting coordinates of characters consumption position (column/row),
  so the input is on the form of {:i INPUT_STRING, :c COLUMN_INT, :r ROW_INT} for convenience if we feed the {:i SOME_STRING} the default column/row will be set to 0:0.

 Roadmap:

 1.) add memoization to reduce the cost from O(n^p) to O(n) - Packard parser (Practical Linear-Time Algorithm with Backtracking http://pdos.csail.mit.edu/~baford/packrat/thesis/thesis.pdf)
 2.) implement the performance benchmarks showing the benefits of memoization.

About

Lazy Evaluation Recursive Grammar Combinators for Clojure

Resources

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published