q_parser.org

Parser for the RECURSIVE-FUNCTIONS Language

This parser is written using the Haskell parser library parsec, because handwriting the parser became too tedious. You do not need to understand the parser code to use it in the assignment.

Abstract Syntax Tree

type ID = String

data Binding = Bind ID AST
               deriving Show

data FBind = FBind ID [ID] AST
             deriving (Show)
  
data AST =
    Number Int
  | Boolean Bool                              
  | Reference ID                              
  | Assume [Binding] AST                      
  | If AST AST AST                            
  | Function [ID] AST
  | RecFun [FBind] AST
  | App [AST]  -- 'app' meaning 'Application' 
  deriving Show

Lexer

languageDef =
   emptyDef { Token.identStart      = letter <|> oneOf "+-*/|&~"
            , Token.identLetter     = alphaNum <|> oneOf "+-*/|&~"
            , Token.opLetter        = oneOf "+-*/&|~" 
            , Token.reservedNames   = [ "if", "assume", "True", "False", "function"]
            }

lexer = Token.makeTokenParser languageDef

-- specific token parsers
parens = Token.parens lexer -- parentheses
identifier =    (Token.identifier lexer)
            <|> (Token.operator lexer)
                -- identifier
reserved   = Token.reserved lexer -- reserved name
integer    = Token.natural    lexer -- integer
whiteSpace = Token.whiteSpace lexer --  whitespace
symbol = Token.symbol lexer ","
dot = Token.dot lexer

Parser For AST

astParser :: Parser AST
astParser =    integerParser
           <|> booleanTrue
           <|> booleanFalse
           <|> identifierParser
           <|> parens astInParens

-- to parse complex AST expressions within parentheses
astInParens :: Parser AST
astInParens =    assumeParser
             <|> ifParser
             <|> funcParser
             <|> appParser
             <|> recFunParser

The various parsers for the sub-components are:

integerParser

integerParser :: Parser AST
integerParser = do
  val <- integer
  return $ Number $ fromIntegral val

boolean

booleanTrue :: Parser AST
booleanTrue = do
  reserved "True"
  return $ Boolean True

booleanFalse :: Parser AST
booleanFalse = do
  reserved "False"
  return $ Boolean False

identifierParser

identifierParser :: Parser AST
identifierParser = do
  id <- identifier
  return $ Reference id

assumeParser

assumeParser :: Parser AST
assumeParser = do
  reserved "assume"
  bindings <- parens bindListParser
  expr <- astParser
  return $ Assume bindings expr

To Parse Binds

bindListParser :: Parser [Binding]
bindListParser = do
  bindList <- (sepBy1 (parens bindParser) dot)
  return bindList
  
bindParser :: Parser Binding
bindParser = do
  id <- identifier
  expr <- astParser
  return $ Bind id expr

ifParser

ifParser :: Parser AST
ifParser = do
    reserved "if"
    cond <- astParser
    thenExpr <- astParser
    elseExpr <- astParser
    return $ If cond thenExpr elseExpr

funcParser

funcParser :: Parser AST
funcParser = do
  reserved "function"
  argList <- parens argParser
  body <- astParser
  return $ Function argList body

argParser :: Parser [ID]
argParser = do
  argList <- (sepBy1 identifier dot)
  return argList

appParser

appParser :: Parser AST
appParser = do
  exprList <- (sepBy1 astParser whiteSpace)
  return $ App exprList

recFunParser

-- to parse fbinds
fbindListParser :: Parser [FBind]
fbindListParser = do
  fbindList <- (sepBy1 (parens fbindParser) dot)
  return fbindList
  
fbindParser :: Parser FBind
fbindParser = do
  id <- identifier
  argList <- parens argParser
  body <- astParser
  return $ FBind id argList body
  
recFunParser :: Parser AST
recFunParser = do
    reserved "recfun"
    fbinds <- parens fbindListParser
    body <- astParser
    return $ RecFun fbinds body

Driver Function

parseString :: String -> AST
parseString str =
  case parse astParser "" str of
     Left e  -> error $ show e
     Right r -> r

Imports And Tangling

module ASTParser where

import System.IO
import Control.Monad
import Text.ParserCombinators.Parsec
import Text.ParserCombinators.Parsec.Expr
import Text.ParserCombinators.Parsec.Language
import qualified Text.ParserCombinators.Parsec.Token as Token

<<ast>>
<<lexer>>
<<ast_parser>>
<<integer_parser>>
<<boolean>>
<<identifier_parser>>
<<binds_parser>>
<<assume_parser>>
<<if_parser>>
<<func_parser>>
<<rec_fun_parser>>
<<app_parser>>
<<parse_string>>