# Parsing puzzle, avoid look-ahead?

**URL:** <https://discourse.elm-lang.org/t/parsing-puzzle-avoid-look-ahead/663>\
**Category:** Learn\
**Created:** [February 11, 2018, 1:44pm UTC](https://discourse.elm-lang.org/t/parsing-puzzle-avoid-look-ahead/663 "2018-02-11T13:44:53Z")\
**Posts on this page:** 8\
**Page:** 1

<div class="post-metadata">

**Author:** ![rob](https://yyz1.discourse-cdn.com/flex035/user_avatar/discourse.elm-lang.org/rob/32/589_2.png) [@rob](https://discourse.elm-lang.org/u/rob)\
**Post date:** [February 11, 2018, 1:44pm UTC](https://discourse.elm-lang.org/t/parsing-puzzle-avoid-look-ahead/663/1 "2018-02-11T13:44:53Z")

</div>

Here’s a little parsing problem I ran into while writing a parser for [EDN](http://edn-format.org) (planning to announce that package soon). I used [elm-tools/parser](http://package.elm-lang.org/packages/elm-tools/parser/latest), but failed to find a good solution without adding a look-ahead primitive. I’m curious whether there’s a nice way to solve this with `delayedCommit`, or in some other way?

Here’s a reduced version: We want to parse a nested datastructure of Lisp-like lists and integers, where the list parentheses are “self-delimited” for lack of a better term:

```auto
data Thing = Number Int | Things (List Thing)

(1 2 3) == ( 1 2 3 ) --> Things [Number 1, Number 2, Number 3]
((1) 2) == ( (1)2 ) --> Things [Things [ Number 1], Number 2 ]
(()1()) == ( () 1 () ) --> Things [Things [], 1, Things [] ]

```

With look-ahead, we can make a parser for numbers that ensures the number is delimited:

```auto
import Parser as P exposing ((|.), (|=), Parser)

-- run a parser, then rewind input
lookAhead : Parser a -> Parser a

sep : Parser ()
sep = P.oneOf
    [ P.ignore P.oneOrMore (\c -> c == ' ')
    , lookAhead (P.oneOf [P.symbol "(", P.symbol ")"])
    ]

number : Parser Thing
number = P.succeed Number |= P.int |. sep

```

and put the whole thing together with a list parser:

```auto
thing : Parser Thing
thing = P.oneOf [number, things]

things : Parser Thing
things = P.succeed Things
    |. P.symbol "("
    |= P.repeat P.zeroOrMore thing
    |. P.symbol ")"

```

(This doesn’t quite work, since it doesn’t eat all the optional whitespace this way, and lacks some `lazy`. Here’s a [complete version](https://gist.github.com/robx/482a71be0438a4d02d7d00ba75a679ae).)

I think the core issue I’m running into is that I need the closing parenthesis both to terminate the number, and to terminate the list. So trying to do this without look-ahead I found my number parser had to return both the number and the closing token, which made things … messy.

I hope I haven’t broken the problem down too far to illustrate the issue! And am very curious if you have some suggestions for how to tackle this.

---

<div class="post-metadata">

**Author:** ![ilias](https://yyz1.discourse-cdn.com/flex035/user_avatar/discourse.elm-lang.org/ilias/32/6_2.png) [@ilias](https://discourse.elm-lang.org/u/ilias)\
**Post date:** [February 11, 2018, 7:31pm UTC](https://discourse.elm-lang.org/t/parsing-puzzle-avoid-look-ahead/663/2 "2018-02-11T19:31:16Z")

</div>

I don’t know EDN so I’m most likely missing something. It’s not clear to me - from the example inputs - why the look-ahead is needed. Is something like [this](https://ellie-app.com/d6kt4qwjca1/1) unable to parse certain “good” inputs (or does it give false positives, perhaps?)

---

<div class="post-metadata">

**Author:** ![rob](https://yyz1.discourse-cdn.com/flex035/user_avatar/discourse.elm-lang.org/rob/32/589_2.png) [@rob](https://discourse.elm-lang.org/u/rob)\
**Post date:** [February 12, 2018, 8:48am UTC](https://discourse.elm-lang.org/t/parsing-puzzle-avoid-look-ahead/663/3 "2018-02-12T08:48:19Z")

</div>

Thank you Ilias, this certainly helps me narrow it down! And yes, that’s a correct parser, and I was kind of afraid this would happen. 🙂 I do think I broke it down too far, but this might turn out into a moving goal-posts kind of thing.

I’ll give it another attempt for the full language and report back.

---

<div class="post-metadata">

**Author:** ![rob](https://yyz1.discourse-cdn.com/flex035/user_avatar/discourse.elm-lang.org/rob/32/589_2.png) [@rob](https://discourse.elm-lang.org/u/rob)\
**Post date:** [February 12, 2018, 10:05am UTC](https://discourse.elm-lang.org/t/parsing-puzzle-avoid-look-ahead/663/4 "2018-02-12T10:05:15Z")

</div>

I’ve made some progress.

1. `Parser.int` is sneaky! It actually does look-ahead under the hood, and will fail on e.g. “1a” but not “1(”. Parsing numbers using `P.keep P.oneOrMore Char.isDigit` gets us closer. (But that still works fine on my proposed simple language.)
2. To show the issue, I need two different token types that we require to be separated by whitespace, but that would parse separately just fine without. So I’ll add a token consisting of lower-case letters. So things like `(hello 1(2 world) bye )` are in, but `(hello1 2bye)` are not.

I’ve updated the [Ellie](https://ellie-app.com/336wWwxyBa1/0) to illustrate this.

---

<div class="post-metadata">

**Author:** ![ilias](https://yyz1.discourse-cdn.com/flex035/user_avatar/discourse.elm-lang.org/ilias/32/6_2.png) [@ilias](https://discourse.elm-lang.org/u/ilias)\
**Post date:** [February 12, 2018, 10:54am UTC](https://discourse.elm-lang.org/t/parsing-puzzle-avoid-look-ahead/663/5 "2018-02-12T10:54:29Z")

</div>

Right, yeah. The way I usually see this done is to write something custom for `repeat` (or use the `list` thing in `Parser.LanguageKit`. Basically what you’d do is parse the first thing, then require whitespace for subsequent things.

Now, the annoying thing in this case is that whitespace requirement depends on what the previous and next thing are. With some minor cleverness, we can encode that: check what the last thing parsed was, and only require whitespace if it was not a list and the next thing is not a list.

I threw together [an example](https://ellie-app.com/3T2MbFKZca1/2) though there is probably some room for improvement, there. Hope that helps!

---

<div class="post-metadata">

**Author:** ![MarkHamburg](https://avatars.discourse-cdn.com/v4/letter/m/cdc98d/32.png) [@MarkHamburg](https://discourse.elm-lang.org/u/MarkHamburg)\
**Post date:** [February 12, 2018, 12:44pm UTC](https://discourse.elm-lang.org/t/parsing-puzzle-avoid-look-ahead/663/6 "2018-02-12T12:44:03Z")

</div>

This is a good tutorial on building parsers with combinators.

> **[Understanding Parser Combinators | F# for fun and profit](https://fsharpforfunandprofit.com/posts/understanding-parser-combinators/)**
>
> Building a parser combinator library from scratch

It’s in F# as opposed to Elm but the ideas all flow from the same source. And here is a post about building a Scheme parser in F#:

> **[Write Yourself a Scheme in 48 Hours in F# – Part VI](https://lucabolognese.wordpress.com/2011/08/05/write-yourself-a-scheme-in-48-hours-in-f-part-vi/)**
>
> The evaluator takes as an input a LispVal. Where does it come from? There must be something that converts your textual input into it. That is the job of the parser. I have used FParsec to build my …

Mark

---

<div class="post-metadata">

**Author:** ![rob](https://yyz1.discourse-cdn.com/flex035/user_avatar/discourse.elm-lang.org/rob/32/589_2.png) [@rob](https://discourse.elm-lang.org/u/rob)\
**Post date:** [February 12, 2018, 1:18pm UTC](https://discourse.elm-lang.org/t/parsing-puzzle-avoid-look-ahead/663/7 "2018-02-12T13:18:17Z")

</div>

Mark, thanks, but I’m not sure how this helps with the concrete issue here? The scheme parsing example in particular requires space separators everywhere.

I’m struggling with `elm-tools/parser`'s lack of an explicit look-ahead combinator. Compare e.g. the remarks on look-ahead in this [article](http://book.realworldhaskell.org/read/using-parsec.html) on Parsec.

---

<div class="post-metadata">

**Author:** ![rob](https://yyz1.discourse-cdn.com/flex035/user_avatar/discourse.elm-lang.org/rob/32/589_2.png) [@rob](https://discourse.elm-lang.org/u/rob)\
**Post date:** [February 12, 2018, 1:20pm UTC](https://discourse.elm-lang.org/t/parsing-puzzle-avoid-look-ahead/663/8 "2018-02-12T13:20:24Z")

</div>

Yes I think this is getting to the core of it, thank you! Your solution keeps things nicely to the list parser and doesn’t touch the other token parsers, which I like a lot. I wasn’t sure how to do that.