Generating AST using Parsec
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
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_kashyap@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.
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 On Sun, Dec 27, 2009 at 10:18 AM, CK Kashyap <ck_kashyap@yahoo.com> 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
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
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
participants (4)
-
CK Kashyap -
Maciej Piechotka -
Stephen Tetley -
Tom Davie