From 16169311d2d39d82a799fd90c77c829767842c9d Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Juan=20Manuel=20Tom=C3=A1s?= Date: Sat, 19 Oct 2024 20:03:50 -0300 Subject: Revert some changes --- README.md | 25 ------------------------- base.lisp | 42 +++++++++--------------------------------- core.lisp | 34 ++++++++++++++-------------------- extra.lisp | 30 +++++++++++++----------------- notes.md | 33 --------------------------------- package.lisp | 2 -- 6 files changed, 36 insertions(+), 130 deletions(-) delete mode 100644 notes.md diff --git a/README.md b/README.md index 6705ffd..9e0546d 100644 --- a/README.md +++ b/README.md @@ -3,28 +3,3 @@ Parser Generator This parser generator expands on [this paper](https://www.cs.nott.ac.uk/~pszgmh/monparsing.pdf). The goal is to have a good enough parser generator for use in my other personal projects. - -# The type of parsers - -Parsers are lambdas that receive some *input* and return either a *parsing* or a *failure*. - -A *parsing* denotes a successful execution of the parser on the given input. - -Failures can be either *normal-failure* or *critical-failure*. - -The distinction of failure types allows to discern between an input that needs to be -parsed with another parser, and a syntax error. - -## Interaction with parser control flow - -### Choice (either) - -- parsing -> exit -- normal-failure -> continue -- critical-failure -> exit - -### Sequence (comp) - -- parsing -> continue -- normal-failure -> exit -- critical-failure -> exit diff --git a/base.lisp b/base.lisp index a5d8b9d..61c47bc 100644 --- a/base.lisp +++ b/base.lisp @@ -2,53 +2,29 @@ (defstruct parsing tree - left - limit) + left) (defstruct failure place message) -(defun lazy-parsing-p (r) - (or (functionp r) - (parsing-p r))) - (defun new (tree) - (lambda (input &key limit lazy) - (declare (ignore limit lazy)) + (lambda (input &key lazy) + (declare (ignore lazy)) (make-parsing :tree tree :left input))) -(defun bind (parser f &key (greedy t)) - (lambda (input &key limit lazy) - (let (r) - (if greedy - (setf r (funcall parser input :limit limit)) - (let ((next-parser (funcall f nil input)) - (inner-limit -1)) - (do ((sweep-input input (advance sweep-input))) - ((or (if limit - (> (cursor-distance sweep-input input) limit) - (not (has-data? sweep-input))) - (> inner-limit -1)) - nil) - (when (lazy-parsing-p (funcall next-parser sweep-input :lazy t)) - (setf inner-limit (cursor-distance sweep-input input)) - (when limit (decf limit inner-limit)))) - (if (< inner-limit 0) - (setf r (make-failure :place input - :message "Reached end of input while sweeping.")) - (setf r (funcall parser input :limit inner-limit))))) +(defun bind (parser f) + (lambda (input &key lazy) + (let ((r (funcall parser input))) (cond ((parsing-p r) (if lazy - (lambda (ignored-input &key lazy limit) + (lambda (ignored-input &key lazy) (declare (ignore ignored-input)) (funcall (funcall f (parsing-tree r) input) (parsing-left r) - :lazy lazy - :limit (if greedy (parsing-limit r) limit))) + :lazy lazy)) (funcall (funcall f (parsing-tree r) input) - (parsing-left r) - :limit (if greedy (parsing-limit r) limit)))) + (parsing-left r)))) ((failure-p r) r) (t (error (format nil "Invalid return value: ~a" r))))))) diff --git a/core.lisp b/core.lisp index be12f99..2870f7b 100644 --- a/core.lisp +++ b/core.lisp @@ -1,7 +1,7 @@ (in-package #:monparser) (defun fail (message) - (lambda (input &key limit lazy) + (lambda (input &key lazy) (make-failure :place input :message message))) (defmacro unit (&optional predicate) @@ -20,20 +20,18 @@ (and (symbolp x) (string-equal (symbol-name x) "IT"))) predicate)))) (t (error (format nil "Invalid predicate: ~a." predicate)))) - `(lambda (input &key limit lazy) + `(lambda (input &key lazy) (declare (ignore lazy)) - (if (and limit (<= limit 0)) - (make-failure :place input :message "Reached established limit.") - (if (has-data? input) - (let ((it (peek input))) - (if ,predicate - (make-parsing :tree it :left (advance input) :limit (if limit (1- limit))) - (make-failure :place input - :message (format nil "Expected: ~a, Got: ~a" ',predicate it)))) - (make-failure :place input :message "Reached end of input."))))) + (if (has-data? input) + (let ((it (peek input))) + (if ,predicate + (make-parsing :tree it :left (advance input)) + (make-failure :place input + :message (format nil "Expected: ~a, Got: ~a" ',predicate it)))) + (make-failure :place input :message "Reached end of input.")))) (defun one-of (first-parser second-parser &rest other-parsers) - (lambda (input &key limit lazy) + (lambda (input &key lazy) (declare (ignore lazy)) (labels ((one-of-rec (parsers) (let ((intermediate-parsers '()) @@ -42,8 +40,7 @@ (dolist (p parsers) (let ((r (funcall p input - :lazy (> (length parsers) 1) - :limit limit))) + :lazy (> (length parsers) 1)))) (cond ((functionp r) (push r intermediate-parsers)) ((parsing-p r) @@ -73,17 +70,14 @@ `(bind ,parser (lambda (&rest ,unused) (declare (ignore ,unused)) - (comp ,(cdr bindings) ,@body)) - :greedy ,(not lazy)) + (comp ,(cdr bindings) ,@body))) `(bind ,parser (lambda (,var &rest ,unused) (declare (ignore ,unused)) - (comp ,(cdr bindings) ,@body)) - :greedy ,(not lazy))) + (comp ,(cdr bindings) ,@body)))) (if (and (consp var) (symbolp (car var)) (symbolp (cdr var))) `(bind ,parser (lambda (,(car var) ,(cdr var) &rest ,unused) (declare (ignore ,unused)) - (comp ,(cdr bindings) ,@body)) - :greedy ,(not lazy)) + (comp ,(cdr bindings) ,@body))) (error "Binding must be either a symbol or a cons of symbols.")))))) diff --git a/extra.lisp b/extra.lisp index 2963e94..67d057c 100644 --- a/extra.lisp +++ b/extra.lisp @@ -21,9 +21,9 @@ (defun many (p) (comp ((x p) - (xs (if (not x) - (fail "Parsing result is empty.") - (optional (many p))))) + (xs (if x + (optional (many p)) + (fail "Parsing result is empty.")))) (cons x xs))) (defun repeat (p min &optional (max 0)) @@ -38,25 +38,21 @@ nothing))) (defun whitespace? (x) - (some (lambda (y) (char= x y)) '(#\Space #\Newline #\Tab))) + (some (lambda (y) (char= x y)) '(#\Space #\Newline #\Return #\Tab))) (defparameter whitespace - (comp ((_ (optional (many (unit whitespace?))))))) + (optional (many (unit whitespace?)))) -(defun separated-list (p separator &key include-separator) +(defun separated-list (p separator) (comp ((v p) (sep (optional separator)) (vn (if sep (separated-list p separator) nothing))) - (if include-separator - (cons v (cons sep vn)) - (cons v vn)))) - -(defun surrounded (left p right &key include-surrounding) - (comp ((l left) - (body p :lazy) - (r right)) - (if include-surrounding - (list l body r) - body))) + (cons v vn))) + +(defun surrounded (p left right) + (comp ((_ left) + (body p) + (_ right)) + body)) diff --git a/notes.md b/notes.md deleted file mode 100644 index 717613a..0000000 --- a/notes.md +++ /dev/null @@ -1,33 +0,0 @@ -# one-of in parallel -## Problem -When in a one-of block, it's harder to tell where an error came from. - -## Current solution -We have critical blocks that stop parsing when the parser inside fails. - -## Problem with current solution -We need to be dilligent in placing critical blocks. - -## Another approach -We could take a page from LR parsers and instead of driving the parsing from the parsers themselves we invert the flow, making the input drive the parsing. This results in a breadth first parsing, where the one-of block parses one step of every of it's children and decides which to keep. In the event there's only one children left, it is critical, so a failure stops parsing and reports the error. - -## How to select between BF and DF when parsing -Add an extra argument to parser type (lambda (input)) for the parsing mode. -one-of will be BF and comp will be DF. -This means that the immediate children of a one-of block will be parsed step by step. - -## Implementing BF in bind -Instead of calling the resulting function with the input, return it. -It will be the caller's responsibility to call the resulting lambda with the appropiate input. -This will give control to the one-of block to call the next parsing step. - -# lazy binding -## Problem -If defining a parser that surrounds another, the inner parser must know about what the delimiter parser is attempting to parse, specially after the inner parser. - -## Solution -Implement lazy binding. This sweeps the next parser across the input until it finds where it first parses, then takes the distance from the current input and calls the current parser with a limit on how much input to parse equal to said difference. - -# TODO -* Change the parser entry so that it takes streams as input. This will make it easier to interact with other packages. -* Change literal parser into a macro that chains unit parsers. This will take advantage of the BF feature in one-of block. diff --git a/package.lisp b/package.lisp index 441c2a2..62846f2 100644 --- a/package.lisp +++ b/package.lisp @@ -6,8 +6,6 @@ #:input-cursor #:input-data #:line-and-column - #:new - #:bind #:comp #:one-of #:unit -- cgit v1.2.3