epsil / gll Goto Github PK
View Code? Open in Web Editor NEWGeneral Parser Combinators in Racket
Home Page: https://epsil.github.io/gll/
License: MIT License
General Parser Combinators in Racket
Home Page: https://epsil.github.io/gll/
License: MIT License
The Graph-Structured Stack (GSS) is the trick which gets GLL's worst-case parse time down to O(n^3).
Masaru Tomlta's paper describes the GSS in detail:
http://acl.ldc.upenn.edu/P/P88/P88-1031.pdf
Without a correct GSS, the parser isn't really GLL. The worst-case performance would be at least O(n^4).
The example output after implementing seq
using bind
the first time is not what Racket outputs.
The complete code I have from the tutorial, with a few variable renamers:
#lang racket
(struct success (val remaining) #:transparent)
(struct failure (remaining) #:transparent)
;; ================
;; TERMINAL PARSERS
;; ================
#|
(1) They are calles terminal parsers, because they match against terminal expressions in the underlying grammar.
(2) They are parser generators, because they return parsers.
|#
;; paper: `result`
(define (succeed val)
(lambda (str)
(success val str)))
;; paper: instead of matching single characters, a whole prefix is matched
;; paper: `sat` or `satisfies`
(define (string prefix-to-match)
(lambda (str)
(let* ([prefix-len (min (string-length prefix-to-match)
(string-length str))]
[str-prefix (substring str 0 prefix-len)]
[str-suffix (substring str prefix-len)])
(if (string=? str-prefix prefix-to-match)
(success str-prefix str-suffix)
(failure str)))))
;; ==================
;; PARSER COMBINATORS
;; ==================
#|They make use of parsers combining them in useful ways to enable more complex functionality.|#
;; PAPER: `plus`
(define (alternative alt-1 alt-2)
(lambda (str)
(let ([alt-1-result (alt-1 str)])
(match alt-1-result
[(success val remaining) remaining]
[failure (alt-2 str)]))))
;; PAPER: `bind`
(define (bind a-parser a-parser-generator)
(lambda (str)
(match (a-parser str)
[(success val remaining) ((a-parser-generator val) remaining)]
[failure failure])))
;; PAPER: seq
(define (seq parser-1 parser-2)
(bind parser-1
(lambda (inp-1)
(bind parser-2
(lambda (inp-2)
(succeed (list inp-1 inp-2)))))))
(define article
(alternative (string "the ")
(string "a ")))
(define noun
(alternative (string "student ")
(string "professor ")))
(define verb
(alternative (string "studies ")
(string "lectures ")))
(define noun-phrase
(seq article noun))
(define verb-phrase
(seq verb noun-phrase))
(define sentence
(seq noun-phrase verb-phrase))
(sentence "the professor lectures the student ")
This outputs simply the string:
"the professor lectures the student "
Racket version: 6.10.1
https://pkgd.racket-lang.org/pkgn/search?q=gll does not show up here
This is a fantastic article! It seems to me that since the final version lazily produces complete parse successes and ignores everything else, there's no good way to get at the failures. Actually, since so many intermediate failures are potentially produced in a complex or ambiguous grammar, it's not even clear what would be the "right" failure to display.
Can you demonstrate a version with better error handling? Thanks.
Hi ,
Please add the racket
topic to this repo - I think others will be interested and this will help them find it at https://github.com/topics/racket
https://help.github.com/en/articles/classifying-your-repository-with-topics
Kind regards,
Stephen
A declarative, efficient, and flexible JavaScript library for building user interfaces.
๐ Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. ๐๐๐
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google โค๏ธ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.