Parsing

This page details the GLaDOS parser implementation, which transforms source code into an Abstract Syntax Tree (AST) using Megaparsec parser combinators.

Overview

The parser is implemented in the src/Parser/ module and consists of two main phases:

1. Lexical Analysis (Lexing): Convert source code into tokens
2. Syntactic Analysis (Parsing): Build AST from tokens

Both phases are implemented using Megaparsec, a powerful parser combinator library for Haskell.

Lexical Analysis

Token Types

The lexer recognizes several categories of tokens:

Keywords:

keywords = ["int", "bool", "if", "else", "while", "return", "true", "false"]

Operators:

operators =
  [ "+", "-", "*", "/"        -- Arithmetic
  , "==", "!=", "<", ">", "<=", ">="  -- Comparison
  , "&&", "||"                 -- Logical
  , "="                        -- Assignment
  ]

Delimiters:

delimiters = ["(", ")", "{", "}", ";", ","]

Identifiers:

<identifier> ::= [a-zA-Z_][a-zA-Z0-9_]*

Integer Literals:

<integer> ::= [0-9]+

Boolean Literals:

<boolean> ::= "true" | "false"

Whitespace and Comments

The lexer automatically handles:

• Whitespace: Spaces, tabs, newlines
• Line comments: // comment text
• Block comments: /* comment text */

All whitespace and comments are ignored during parsing.

Lexer Implementation

The lexer is built using Megaparsec's built-in lexer utilities:

-- Space consumer (handles whitespace and comments)
sc :: Parser ()
sc = L.space
  space1
  (L.skipLineComment "//")
  (L.skipBlockComment "/*" "*/")

-- Lexeme parser (parses token and trailing whitespace)
lexeme :: Parser a -> Parser a
lexeme = L.lexeme sc

-- Symbol parser (parses specific string)
symbol :: String -> Parser String
symbol = L.symbol sc

-- Identifier parser
identifier :: Parser String
identifier = lexeme (p >>= check)
  where
    p = (:) <$> letterChar <*> many alphaNumChar
    check x = if x `elem` keywords
                then fail $ "keyword " ++ show x ++ " cannot be an identifier"
                else return x

-- Integer parser
integer :: Parser Int64
integer = lexeme L.decimal

-- Keyword parser
keyword :: String -> Parser ()
keyword w = lexeme (string w *> notFollowedBy alphaNumChar)

Syntactic Analysis

Parser Combinators

Parser combinators allow building complex parsers from simple ones:

-- Sequence: parse p, then q
p <*> q

-- Alternative: try p, if it fails try q
p <|> q

-- Map: parse p and apply function f
f <$> p

-- Bind: parse p, use result in computation
p >>= \result -> ...

-- Many: parse p zero or more times
many p

-- Some: parse p one or more times
some p

-- Optional: parse p or return Nothing
optional p

Expression Parsing

GLaDOS uses operator precedence parsing for expressions:

-- Expression parser with precedence
expr :: Parser Expr
expr = makeExprParser term operatorTable

-- Operator precedence table
operatorTable :: [[Operator Parser Expr]]
operatorTable =
  [ [ binary "*" Mul, binary "/" Div ]                    -- Precedence 6 (highest)
  , [ binary "+" Add, binary "-" Sub ]                    -- Precedence 5
  , [ binary "<" Lt, binary ">" Gt
    , binary "<=" Le, binary ">=" Ge ]                    -- Precedence 4
  , [ binary "==" Eq, binary "!=" Neq ]                   -- Precedence 3
  , [ binary "&&" And ]                                    -- Precedence 2
  , [ binary "||" Or ]                                     -- Precedence 1 (lowest)
  ]

-- Binary operator helper
binary :: String -> Op -> Operator Parser Expr
binary name op = InfixL (BinOp op <$ symbol name)

-- Term (atomic expression)
-- Note: Simplified pseudocode. Actual implementation uses BoolLit, NumLit, FloatLit
-- constructors with Located wrappers for source position tracking.
term :: Parser Expr
term = parens expr
   <|> literal              -- Parses to BoolLit/NumLit/FloatLit (Located)
   <|> try functionCall
   <|> identifier           -- Parses to Var (Located String)

Key Points:

• Operators at the top of the table bind tighter (higher precedence)
• All operators are left-associative (InfixL)
• Terms include literals, variables, function calls, and parenthesized expressions

Statement Parsing

Statements are parsed using pattern matching:

statement :: Parser Statement
statement = choice
  [ ifStatement
  , whileStatement
  , returnStatement
  , try varDeclaration
  , try assignment
  , expressionStatement
  ]

-- If statement
ifStatement :: Parser Statement
ifStatement = do
  keyword "if"
  condition <- parens expr
  thenBody <- braces (many statement)
  elseBody <- optional (keyword "else" >> braces (many statement))
  return $ If condition thenBody elseBody

-- While loop
whileStatement :: Parser Statement
whileStatement = do
  keyword "while"
  condition <- parens expr
  body <- braces (many statement)
  return $ While condition body

-- Return statement
returnStatement :: Parser Statement
returnStatement = do
  keyword "return"
  value <- expr
  optional (symbol ";")
  return $ Return value

-- Variable declaration
varDeclaration :: Parser Statement
varDeclaration = do
  varType <- typeParser
  varName <- identifier
  value <- optional (symbol "=" >> expr)
  optional (symbol ";")
  return $ Decl varType varName value

-- Assignment
assignment :: Parser Statement
assignment = do
  varName <- identifier
  symbol "="
  value <- expr
  optional (symbol ";")
  return $ Assign varName value

-- Expression statement (function call as statement)
expressionStatement :: Parser Statement
expressionStatement = do
  e <- expr
  optional (symbol ";")
  return $ ExprStmt e

Function Parsing

Functions are the top-level program structure:

-- Function definition
functionDef :: Parser FuncDef
functionDef = do
  returnType <- typeParser
  name <- identifier
  params <- parens paramList
  body <- braces (many statement)
  return $ FuncDef
    { funcName = name
    , funcReturnType = returnType
    , funcParams = params
    , funcBody = body
    }

-- Parameter list
paramList :: Parser [(String, Type)]
paramList = param `sepBy` symbol ","
  where
    param = (,) <$> typeParser <*> identifier

-- Type parser
typeParser :: Parser Type
typeParser = (TypeInt <$ keyword "int")
         <|> (TypeFloat <$ keyword "float")
         <|> (TypeBool <$ keyword "bool")
         <|> (TypeVoid <$ keyword "void")

-- Program (list of functions)
program :: Parser Program
program = sc *> many functionDef <* eof

Function Calls

Function calls require special handling:

functionCall :: Parser Expr
functionCall = do
  name <- identifier
  args <- parens (expr `sepBy` symbol ",")
  return $ Call name args

Note: try combinator is used to backtrack if parsing fails (useful for distinguishing variable from function call).

AST Structure

The parser produces an Abstract Syntax Tree with the following structure:

Program Node

data Program = Program [FuncDef]

Function Definition Node

data FuncDef = FuncDef
  { funcName :: String
  , funcReturnType :: Type
  , funcParams :: [(String, Type)]
  , funcBody :: [Statement]
  }

Statement Nodes

data Statement
  = Decl Type String (Maybe Expr)      -- int x = 5;
  | Assign String Expr                 -- x = 10;
  | If Expr [Statement] (Maybe [Statement])  -- if (...) {...} else {...}
  | While Expr [Statement]             -- while (...) {...}
  | For (Maybe Statement)              -- for (init; cond; incr) {...}
        (Maybe Expr)
        (Maybe Statement)
        [Statement]
  | Return Expr                        -- return x;
  | ExprStmt Expr                      -- functionCall();

For Loop Structure:

• First Maybe Statement: Optional initialization (declaration or assignment)
• Maybe Expr: Optional condition expression
• Second Maybe Statement: Optional increment statement
• [Statement]: Loop body

Expression Nodes

data Expr
  = BoolLit (Located Bool)             -- true, false (with source position)
  | NumLit (Located Int)               -- 42, -10 (with source position)
  | FloatLit (Located Double)          -- 3.14, -0.5 (with source position)
  | Var (Located String)               -- x (with source position)
  | BinOp Op (Located Expr) (Located Expr)  -- a + b
  | UnOp UnOp (Located Expr)           -- -x, !flag
  | Call (Located String) [Expr]       -- foo(a, b)

Note: All expressions are wrapped with Located to track source positions for better error messages.

Binary Operators

data Op
  = Add | Sub | Mul | Div              -- Arithmetic
  | Eq | Neq | Lt | Gt | Le | Ge       -- Comparison
  | And | Or                           -- Logical

Unary Operators

data UnOp
  = Neg                                -- Negation: -x
  | Not                                -- Logical NOT: !x

Literals

Literals are now represented directly in expression nodes rather than a separate Literal type:

• NumLit (Located Int): Integer literals like 42, -10
• FloatLit (Located Double): Floating-point literals like 3.14, -0.5
• BoolLit (Located Bool): Boolean literals true, false

Types

data Type
  = TypeInt                            -- int
  | TypeFloat                          -- float
  | TypeBool                           -- bool
  | TypeVoid                           -- void
  | TypeInfer                          -- Internal use only

Note: TypeInfer is used internally by the compiler for type inference and should not appear in parsed AST.

Located Wrapper

All AST nodes that require error reporting are wrapped with source position information:

data Located a = Located
  { pos :: SourcePos                   -- Source file position
  , value :: a                         -- Actual value
  }

data SourcePos = SourcePos
  { sourceName :: String               -- File name
  , sourceLine :: Int                  -- Line number
  , sourceColumn :: Int                -- Column number
  }

Purpose: The Located wrapper enables precise error messages by tracking where each construct appears in the source code.

Example Error Message:

Type error at line 10, column 5:
  Variable 'x' used before initialization

Without Located, the compiler could only report "Variable 'x' used before initialization" without indicating where in the code this occurred.

Error Handling

Parse Errors

Megaparsec provides detailed error messages:

-- Example error messages
Parse error at line 5, column 10:
  unexpected '{'
  expecting ';', ')', or identifier

Parse error at line 10:
  unexpected end of input
  expecting statement

Error Recovery

The parser uses:

• try combinator: Backtrack on failure
• <|> operator: Try alternative parsers
• optional: Make parts of syntax optional (e.g., semicolons)

Source Position Tracking

Megaparsec automatically tracks:

• Line number
• Column number
• File name (if provided)

This information is included in error messages.

Parser Usage

Parsing Source Code

-- Parse from string
parseGLaDOS :: String -> Either String Program
parseGLaDOS input =
  case parse program "<stdin>" input of
    Left err -> Left (errorBundlePretty err)
    Right ast -> Right ast

Example

Input:

int add(int a, int b) {
    return a + b;
}

Output AST:

Program
  [ FuncDef
      { funcName = "add"
      , funcReturnType = TypeInt
      , funcParams = [("a", TypeInt), ("b", TypeInt)]
      , funcBody =
          [ Return
              (BinOp Add
                (Var "a")
                (Var "b")
              )
          ]
      }
  ]

Parser Features

Semicolon Flexibility

GLaDOS makes semicolons optional after statements:

optionalSemi :: Parser ()
optionalSemi = optional semi >> return ()

This allows both styles:

int x = 5;
return x;

int x = 5
return x

Exception: Semicolons are required in for loop syntax to separate the clauses:

void semi

The for loop parser uses void semi (not optionalSemi) for the clause separators, making them mandatory.

Expression Precedence

The operator table ensures correct precedence:

int x = 2 + 3 * 4;

bool b = 5 > 3 && 10 < 20;

Nested Expressions

The parser handles arbitrary nesting:

int result = ((a + b) * c) / (d - e);
bool flag = (x > 0) && ((y < 10) || (z == 5));

Recursive Functions

Functions can call themselves:

int factorial(int n) {
    if (n <= 1) {
        return 1;
    }
    return n * factorial(n - 1);
}

Parser Limitations

Limited Error Recovery

The parser stops at the first error. It doesn't attempt to recover and continue parsing.

Implementation Details

Megaparsec Advantages

1. Composability: Build complex parsers from simple ones
2. Error Messages: Detailed, helpful error reporting
3. Performance: Efficient parsing with minimal overhead
4. Type Safety: Strong typing prevents many parser bugs
5. Flexibility: Easy to extend with new syntax

Parser Performance

• Time Complexity: O(n) where n is input length
• Space Complexity: O(n) for AST storage
• Backtracking: Minimal, limited to specific cases (function calls vs variables)

Testing the Parser

Example Test Cases

-- Test: Simple function
testSimpleFunction = "int main() { return 42; }"

-- Test: Complex expression
testExpression = "int x = 2 + 3 * 4 - 5 / 2;"

-- Test: Control flow
testControlFlow = "if (x > 0) { return 1; } else { return 0; }"

-- Test: Recursion
testRecursion = "int fib(int n) { if (n <= 1) { return n; } return fib(n-1) + fib(n-2); }"

Running Tests

stack test --test-arguments="--match Parser"

Next Steps

After parsing, the AST is passed to:

1. Security Analysis: Check for division by zero and other issues
2. Type Checking: Verify type correctness
3. IR Generation: Convert to bytecode

See:

• Type Checking
• IR Generation