Recursive Parser

Question

I need to parse, using Megaparsec a data structure like

data Foo
    = Simple String
    | Dotted Foo String

where I can have alphanumeric strings separated by dots.

For example abc should be parsed to Simple "abc" and abc.def to Dotted (Simple "abc") "def".

My parser at the moment is like

fooParser :: Parser Foo
fooParser
    = Simple <$> alphaNum
    <|> do
        foo <- fooParser
        constant "."
        end <- alphaNum
        pure $ Dotted foo end

This works fine for Simple, but it does not parse any Dotted, because the first option always succeeds parsing the first piece of the string.

Which is the best option to fix my parser?

Combinator sepBy1 should fulfill your needs, you then just need to convert a non-empty list into Foo. — Petr
– Petr, Commented Sep 6, 2018 at 8:02

sepp2k · Accepted Answer · 2018-09-06 08:02:58Z

it does not parse any Dotted, because the first option always succeeds parsing the first piece of the string.

That problem can be fixed easily enough by changing the order of your alternatives. Generally, whenever you have an alternative that can always match, that alternative must come last.

However this will only lead you to your next problem: Your Dotted parser is left-recursive, which parsec does not support, meaning it will lead to an infinite recursion once its actually reached.

Generally when we want to use a left-recursive grammar with a parsing algorithm that does not handle left-recursion, we replace the recursion with repetition and then perform a left-fold on the resulting list. So given the original grammar:

foo ::= alphanum
      | foo "." alphanum

We can rewrite it using repetition like this:

foo ::= alphanum ("." alphanum)*

Now the most direct translation to Parsec would use many for the * and then left-fold the resulting list. However, we might notice that the pattern rule ("seperator" rule)* can be more simply matched by sepBy1. So this gives us:

fooParser =
  do
    first : rest <- sepBy1 alphanum $ constant "."
    return $ foldl Dotted (Simple first) rest

Collectives™ on Stack Overflow

Recursive Parser

1 Answer 1

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related