search

djspiewak / parseback

A Scala implementation of parsing with derivatives
http://parseback.io
Apache License 2.0
197 stars 22 forks source link

Implement negation classes #28

Open djspiewak opened 7 years ago

djspiewak commented 7 years ago

Straight out of the ASF+SDF playbook. Identifiers are usually ambiguous with keywords. It's important to be able to address this with negation disambiguation. It's technically possible to implement this by hand now on top of the filter construct, but there may be a nicer algorithmic way. At the very least, the syntax can be made a lot better.

danleh commented 7 years ago

Just a quick question: Is there documentation or an example of how to use the filter construct? In the README you mention it under

Other useful features that are implemented or planned

Thanks in advance and very cool work! (I have worked with SDF3 before and loved its features, but it really isn't very accessible, so this project looks nice indeed!)

djspiewak commented 7 years ago

I think a good starting point for filter is the more limited \ construct implemented in gll-combinators. Basically the essence of the idea is that you have something like this:

lazy val keywords = "def" | "val" | "var" | ...

lazy val id: Parser[Id] = ("""[a-zA-Z][a-zA-Z0-9]*""".r \ keywords) ^^ Id

It's literally just a negation matcher. This is decidable in any regular context (and undecidable in general context-free contexts). The idea is that you check the match against both sides, and it only matches if the left side matches and the right side does not match.

danleh commented 7 years ago

Wow, thanks for the quick answer. Nice, didn't know about \. For more complicated things (e.g. disambiguation filter for precedence and associativity), I have now looked into the filter tests on how to use them (for other people searching for that).