Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Resume from position of failure? #12

Closed
mthom opened this issue Jul 6, 2020 · 1 comment
Closed

Resume from position of failure? #12

mthom opened this issue Jul 6, 2020 · 1 comment
Assignees
Labels

Comments

@mthom
Copy link

mthom commented Jul 6, 2020

I have a problem with rules that are too greedy, and I'm not sure esrap has a good built-in way of handling it. Suppose I have this grammar:

(defrule parse-expr (and chars "()"))

(defrule chars (* (or (alpha-char-p character) "(")))

chars greedily consumes the "(", and next throws a parse error. Doesn't esrap perform backtracking? If not, shouldn't it be possible to catch an error from one rule, and restart the parse from condition object's position, perhaps using a different rule?

@scymtym
Copy link
Owner

scymtym commented Jul 7, 2020

Doesn't esrap perform backtracking?

Esrap is a recursive descent parser with memoization but without backtracking. Repetition expressions are greedy. For "alternative" (or) expressions, the first succeeding alternative is chosen definitively.

If not, shouldn't it be possible to catch an error from one rule, and restart the parse from condition object's position, perhaps using a different rule?

To guide Esrap towards a different parse locally to make the parse succeed globally, the esrap:! (input must not match) and esrap:& (input must match) constructs can (or must, really) be used:

(esrap:defrule chars
    (* (or (alpha-char-p character)
       (and (esrap:! "()") "(")))
  (:text t))

(esrap:parse 'parse-expr "f(oo(bar()") ; => ("f(oo(bar" "()")

The expression (and (esrap:! "()") "(")) looks at the input at the current position and fails if the it matches (). If the input at the current position does not match (), (esrap:! "()") succeeds without advancing the current position. So the input () does not match but ( does.

@scymtym scymtym self-assigned this Jul 8, 2020
@scymtym scymtym closed this as completed Jul 8, 2020
@scymtym scymtym pinned this issue Jul 8, 2020
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
Projects
None yet
Development

No branches or pull requests

2 participants