← Back to Home

Syntax Analysis (The Parser)

Validating Structure and Building the AST

Once the Lexer has converted the raw text into a stream of tokens, the Parser takes over. Its job is to verify that these tokens follow the structural rules of our language, known as the Grammar.

If the grammar is valid, the Parser groups the tokens to build an Abstract Syntax Tree (AST). This tree strips away formatting (like semicolons and braces) and represents the pure hierarchical logic of the code.

VizLang Context-Free Grammar Rules

Our compiler uses Bison (Yacc) to enforce these rules. Here is the actual structured grammar defined in our parser.y file:

Program        -> FunctionList
FunctionList   -> Function | FunctionList Function

Function       -> Type Identifier '(' ParamList ')' Block
Type           -> 'int' | 'void'
ParamList      -> ε | 'int' Id | 'int' Id '[' ']' | 'int' '*' Id | ParamList ',' ...
Block          -> '{' StatementList '}'

StatementList  -> ε | StatementList Statement
Statement      -> VarDecl | ReturnStmt | IfStmt | WhileStmt | ForStmt
                | 'repeat' '(' Expr ')' Block
                | 'sort' '(' Identifier ',' Expr ')' ';' 
                | 'printarray' '(' Identifier ')' ';' 
                | 'print' '(' Expr | String ')' ';'
                | 'input' '(' Identifier ')' ';' 
                | Expr ';'

VarDecl        -> 'int' Id ';' 
                | 'int' Id '=' Expr ';'
                | 'int' Id '[' Number ']' ['=' '{' ArgList '}'] ';'
                | 'int' '*' Id ['=' Expr] ';'

Expr           -> Number | Identifier 
                | '&' Identifier | '*' Expr | Identifier '[' Expr ']' 
                | Identifier '(' ArgList ')'
                | Expr '+' Expr | Expr '-' Expr | Expr '*' Expr | Expr '/' Expr
                | Expr '==' Expr | Expr '<' Expr | Expr '&&' Expr | Expr '||' Expr
                | Expr '=' Expr | '(' Expr ')'

The Precedence Rule-of-Thumb

In an AST, Depth = Priority. Our Parser uses the following order to decide tree depth:

  1. Grouping: ( ) creates a protected sub-shell.
  2. Multiplicative: * and / are pushed deeper than addition.
  3. Additive: + and - wait for multiplication to finish.
  4. Assignment: = is the root, waiting for everything else to resolve.

Phase 1: Building the AST (Token Stream)

Watch how the parser consumes tokens left-to-right to build a hierarchical tree structure. Notice how it handles Operator Precedence by forcing the * node deeper into the tree than the + node!

Target Code: int result = a + b * (c - 2);

Token Stream (Input)

AST Builder (Output)

Phase 2: Executing the AST (DFS Post-Order Traversal)

The compiler evaluates the tree using a Depth-First Search (DFS) in Post-Order. It must "visit" the bottom-most leaves first because a parent operator cannot calculate its value until its children are fully resolved.

Execution Engine

Target: int result = a + b * (c - 2);

Status: Waiting to start execution...

Abstract Syntax Tree

VarDecl (int)
└─ Assign (=)
  ├─ Identifier (result)
  └─ BinaryOp (+)
    ├─ Identifier (a)
    └─ BinaryOp (*)
      ├─ Identifier (b)
      └─ BinaryOp (-)
        ├─ Identifier (c)
        └─ Number (2)