Source
r/haskell•
MachineGunPablo

Megaparsec - Asking for advice on a parsing problem

question

Hello Haskellers of the internet, I need your help.

I'm currently writing a parser using Megaparsec and have reached a point where I could use some input from smarter coders.

I have a grammar with multiple top-level statements, which can appear any number of times in any order, in EBNF, this would be something like:

topLevelStament -> Variant1 | Variant2
Variant1 -> ...
Variant2 -> ...

For this, I defined the following Haskell types:

data Variant1 = Variant1 String
data Variant2 = Variant2 String

I want the AST to have the following final structure:

data AST = { variants1 :: [Variant1], variants2 :: [Variant2] }

For parsing, I created a type topLevelStament:

data TopLevelStament = V1 Variant1 | V2 Variant2

And use the many and choice parser combinators with backtracking:

variants <- many $ choice [try . parseVariant1, try . parseVariant2]

with individual parsers for each variant:

parseVariant1 :: Parser TopLevelStament
parseVariant2 :: Parser TopLevelStament

Now my question are,

a) is this in general a good approach for my problem? Is it something that I'm missing, something I could do better?

b) what is the best (i.e. most efficient, elegant) way of assembling the AST back from the parsed [TopLevelStament], this is where I am currently struggling the most. If I have a list of [TopLevelStatement], how can it turn it back into individual [Variant1], [Variant2] lists to assemble the AST?

Thanks a lot and happy haskelling.

Posted Apr 17, 2021, 9:04 PM UTC · edited

811
brandonchinn178•

The approach seems fine. I'd make a dedicated parseTopLevelStatement and then do

topLevelStatements <- many parseTopLevelStatements
let (variants1, variants2) = ...
return $ AST variants1 variants2

for your second question, I'd recommend using partitionEithers if you only have two variants. If you plan on extending it, you can just implement it on your own. Here's a hint:

toVariants :: [TopLevelStatement] -> ([Variant1], [Variant2])
toVariants [] = ...
toVariants (stmt:rest) =
  let (variant1s, variant2s) = toVariants rest
  in ...
4
MachineGunPabloOP•

Thanks a lot, I indeed inspired myself a lot from the partitionEiher's implementation:

partitionTopLevelStatements :: [TopLevelStatement] -> ([ImportStatement], [PackageDefinition])
partitionTopLevelStatements = foldr acc init
  where
    init = ([], [])
    acc (ImportStmt e) (imports, packages) = (e : imports, packages)
    acc (PackageDef e) (imports, packages) = (imports, e : packages)
0
backtickbot•

Fixed formatting.

Hello, MachineGunPablo: code blocks using triple backticks (```) don't work on all versions of Reddit!

Some users see this / this instead.

To fix this, indent every line with 4 spaces instead.

FAQ

^(You can opt out by replying with backtickopt6 to this comment.)

2
blamario•

You should keep your types specific. parseVariant1 clearly cannot parse any TopLevelStatement, so its type is misleading. Better define them to do their jobs

parseVariant1 :: Parser Variant1
parseVariant2 :: Parser Variant2

and then wrap them where you use them

variants <- many $ choice [V1 <$> try parseVariant1, V2 <$> try parseVariant2]
3
MachineGunPabloOP•

yes, great suggestion just did it like that :)

2
Tarmen•

Data.Either has a partitionEithers function which is pretty close to what you want. But notice that this can put the lists into memory, fine if you have tens of thousands of elements but think about using vectors if you have millions.

https://hackage.haskell.org/package/base-4.15.0.0/docs/src/Data-Either.html#partitionEithers

2
MachineGunPabloOP•

Yes!! Thanks a lot, that's what I'm going to do, a foldr that pattern matches and accumulates in the corresponding independent lists.

I don't think we'll ever reach anything close to those numbers, we are dealing with manually typed input after all.

Thanks a lot!

1
MachineGunPabloOP•

I came up with this:

partitionTopLevelStatements :: [TopLevelStatement] -> ([ImportStatement], [PackageDefinition])
partitionTopLevelStatements = foldr acc init
  where
    init = ([], [])
    acc (ImportStmt e) (imports, packages) = (e : imports, packages)
    acc (PackageDef e) (imports, packages) = (imports, e : packages)
0
Tarmen•

Note that this is less lazy than you might expect because the pattern is strict https://gitlab.haskell.org/ghc/ghc/-/issues/3709

The ~ is a lazy pattern which is equivalent to using fst and snd for destructuring. Without it ghc can't give you the first result before checking that nothing in the rest of the list crashes/loops forever so the entire list is in memory before you get the first result - this is like using case vs let in brandonchinns solution.

3
MachineGunPabloOP•

oh wow thank you, to be honest I didn't know about lazy pattern matching, currently reading https://wiki.haskell.org/Lazy_pattern_match. I've have changed the pair constructor in my code to match lazily, great suggestion :)

1
backtickbot•

Fixed formatting.

Hello, MachineGunPablo: code blocks using triple backticks (```) don't work on all versions of Reddit!

Some users see this / this instead.

To fix this, indent every line with 4 spaces instead.

FAQ

^(You can opt out by replying with backtickopt6 to this comment.)

2