[Haskell-cafe] Generating AST using Parsec

[CK Kashyap]

Hi All,
I recently came across the paper titled "Monadic Parser Combinators" - After going through it a few times, I think I am beginning to understand monads.
However, the parser developed in the paper does not generate an AST - I feel, I'd grasp the whole thing a lot better if I could go over a sample that generates an AST from a simple expression (or even a standard language such as C or Java) ... Can someone please point me to a sample that generates AST - preferably with the simple parser combinator given in the paper.
Regards,
Kashyap

_______________________________________________
Haskell-Cafe mailing list
Haskel...@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Stephen Tetley]

Hi Kashyap

Algebraic data types in Haskell and other modern functional languages
are so convenient for describing syntax trees that you don't have need
for a 'tree builder' vis-a-vis Java Tree Builder or JJTree that you
might use in Java.

The original Parsec distribution has parsers and ASTs for Henk and
Andrew Appel's Tiger language and is available here:

http://legacy.cs.uu.nl/daan/parsec.html

Unfortunately the package on Hackage has removed the examples. Parsec
can be considered a progression of the ideas detailed in Hutton and
Meijer's "Monadic Parser Combinators".

Best wishes

Stephen

2009/12/27 CK Kashyap <ck_ka...@yahoo.com>:

> However, the parser developed in the paper does not generate an AST - I feel, I'd grasp the whole thing a lot better if I could go over a sample that generates an AST from a simple expression (or even a standard language such as C or Java) ... Can someone please point me to a sample that generates AST - preferably with the simple parser combinator given in the paper.

[Tom Davie]

This isn't quite what you're asking for, but by using the applicative interface to parsers, you need do little more than spell out what your AST looks like:

import Control.Applicative

import Control.Applicative.Infix

data Equation = String :=: Expression

data Expression = EApp fun arg | EInt Int | EId String

parseEquation :: Parser Equation

parseEquation = parseIdentifier <^(:=:)^> parseExpression

parseExpression :: Parser Expression

parseExpression =

      (EApp <$> parseExpression <*> parseExpression)

  <|> (EInt <$> parseInt)

  <|> (EId <$> parseIdentifier)

parseIdentifier :: Parser String

parseIdentifier = parseLowercaseChar <^(:)^> parseString

etc

Bob

[Maciej Piechotka]

On Sun, 2009-12-27 at 02:18 -0800, CK Kashyap wrote:
> Hi All,
> I recently came across the paper titled "Monadic Parser Combinators" - After going through it a few times, I think I am beginning to understand monads.
> However, the parser developed in the paper does not generate an AST - I feel, I'd grasp the whole thing a lot better if I could go over a sample that generates an AST from a simple expression (or even a standard language such as C or Java) ... Can someone please point me to a sample that generates AST - preferably with the simple parser combinator given in the paper.
> Regards,
> Kashyap

It parses something like "x+y+z*pi"

import Control.Applicative
import Text.ParserCombinators.Parsec hiding ((<|>))

data Expr = Variable String
| Add Expr Expr
| Mul Expr Expr deriving (Show)

parseAST :: Parser Expr
parseAST = parseAdd

parseAdd :: Parser Expr
parseAdd = parseMul >>= \e -> ((string "+" >> (Add e <$> parseAdd)) <|>
(return e))

parseMul :: Parser Expr
parseMul = parseBase >>= \e -> ((string "*" >> (Mul e <$> parseMul)) <|>
(return e))

parseBase :: Parser Expr
parseBase = (string "(" *> parseAST <* string ")") <|>
(Variable <$> many1 letter)

Regards