From 34ccc296b6265be09501917fe3deae89549edaf4 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Juan=20Manuel=20Tom=C3=A1s?= Date: Wed, 9 Oct 2024 15:56:45 -0300 Subject: Implement bind sweep --- notes.md | 16 ++++++++++------ parser.lisp | 51 +++++++++++++++++++++++++++++++-------------------- 2 files changed, 41 insertions(+), 26 deletions(-) diff --git a/notes.md b/notes.md index 9eddec5..03ea43e 100644 --- a/notes.md +++ b/notes.md @@ -1,22 +1,26 @@ -# Problem +# one-of in parallel +## Problem When in a one-of block, it's harder to tell where an error came from. -# Current solution +## Current solution We have critical blocks that stop parsing when the parser inside fails. -# Problem with current solution +## Problem with current solution We need to be dilligent in placing critical blocks. -# Another approach +## 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 +## 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 +## 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. diff --git a/parser.lisp b/parser.lisp index 5495f74..6bb1cf5 100644 --- a/parser.lisp +++ b/parser.lisp @@ -28,40 +28,51 @@ (format stream "~a: ~a" (cursor (failure-place obj)) (failure-message obj))))) (defun new (tree) - (lambda (input &optional lazy) - (declare (ignore lazy)) + (lambda (input &key limit lazy) + (declare (ignore lazy limit)) (make-parsing :tree tree :left input))) (defun bind-with-input (p f) - (lambda (input &optional lazy) + (lambda (input &key limit lazy) (let ((r (funcall p input))) (if (parsing-p r) (if lazy - (lambda (ignored-input &optional lazy) + (lambda (ignored-input &key lazy limit) (declare (ignore ignored-input)) - (funcall (funcall f (parsing-tree r) input) (parsing-left r) lazy)) + (funcall (funcall f (parsing-tree r) input) (parsing-left r) :lazy lazy :limit limit)) (funcall (funcall f (parsing-tree r) input) (parsing-left r))) r)))) -(defun bind (p f) - (lambda (input &optional lazy) - (let ((r (funcall p input))) +(defun bind (p f &key (greedy t)) + (lambda (input &key limit lazy) + (let (r) + (if greedy + (setf r (funcall p input)) + (let ((next-parser (funcall f (make-parsing :tree nil :left input))) + (limit 0)) + (do ((sweep-input input (advance sweep-input))) (limit nil) + (when (and (has-data? sweep-input) + (functionp (funcall next-parser sweep-input t))) + (setf limit (input-sub sweep-input input)))) + (if (= limit 0) + (setf r (make-failure :place input :message "Reached end of input while sweeping.")) + (setf r (funcall p input :limit limit))))) (if (parsing-p r) (if lazy - (lambda (ignored-input &optional lazy) + (lambda (ignored-input &key lazy limit) (declare (ignore ignored-input)) - (funcall (funcall f (parsing-tree r)) (parsing-left r) lazy)) + (funcall (funcall f (parsing-tree r)) (parsing-left r) :lazy lazy :limit limit)) (funcall (funcall f (parsing-tree r)) (parsing-left r))) r)))) (defun discarding-bind (p f) - (lambda (input &optional lazy) + (lambda (input &key limit lazy) (let ((r (funcall p input))) (if (parsing-p r) (if lazy - (lambda (ignored-input &optional lazy) + (lambda (ignored-input &key lazy limit) (declare (ignore ignored-input)) - (funcall (funcall f) (parsing-left r) lazy)) + (funcall (funcall f) (parsing-left r) :lazy lazy :limit limit)) (funcall (funcall f) (parsing-left r))) r)))) @@ -79,13 +90,13 @@ (error "Binding must be either a symbol or a cons of symbols.")))))) (defun one-of (first-parser second-parser &rest other-parsers) - (lambda (input &optional lazy) - (declare (ignore lazy)) + (lambda (input &key limit lazy) + (declare (ignore lazy limit)) (labels ((one-of-rec (parsers) (let ((intermediate-parsers '()) (result nil)) (dolist (p parsers) - (let ((r (funcall p input (> (length parsers) 1)))) + (let ((r (funcall p input :lazy (> (length parsers) 1)))) (cond ((functionp r) (push r intermediate-parsers)) ((parsing-p r) @@ -114,8 +125,8 @@ (lambda (x) (and (symbolp x) (string-equal (symbol-name x) "IT"))) predicate)))) - `(lambda (input &optional lazy) - (declare (ignore lazy)) + `(lambda (input &key limit lazy) + (declare (ignore lazy limit)) (if (has-data? input) (let ((it (peek input))) (if ,predicate @@ -125,8 +136,8 @@ (make-failure :place input :message "Reached end of input.")))) (defun literal (target) - (lambda (input &optional lazy) - (declare (ignore lazy)) + (lambda (input &key limit lazy) + (declare (ignore lazy limit)) (if (has-data? input) (if (prefix? target input) (make-parsing :tree target :left (advance input (length target))) -- cgit v1.2.3