Practical Parser Projects

Real-world parser implementation guide with AST construction, symbol tables, and code generation

Learning parser generation through practical projects accelerates understanding. Here are realistic project ideas with implementation guidance.

Project Ideas by Difficulty

Beginner: Simple Calculator

Features:

Basic arithmetic: +, -, *, /
Parentheses for grouping
Error handling

Lexer:

Example

[0-9]+ { yylval = atoi(yytext); return NUMBER; } [+*/-()] { return yytext[0]; }

Parser:

bison example

expr : NUMBER           { $$ = $1; }
     | expr '+' expr    { $$ = $1 + $3; }
     | expr '*' expr    { $$ = $1 * $3; }
     | '(' expr ')'     { $$ = $2; }
     ;

Intermediate: Variable Assignment

Features:

Variable declaration: int x = 5;
Variable usage: y = x + 3;
Symbol table

Grammar Additions:

bison example

statement : TYPE IDENTIFIER '=' expr ';'  { declare($2, $1, $4); }
          | IDENTIFIER '=' expr ';'       { assign($1, $3); }
          ;

Advanced: Small Programming Language

Features:

Functions: int add(int a, int b) { return a + b; }
Control flow: if/else, while, for
Arrays
Type system
Scope management

Complexity:

Symbol table with scoping
Type checking
AST generation
Code generation or interpretation

Building AST (Abstract Syntax Tree)

Instead of evaluating directly, build a tree:

c example

struct ASTNode {
    char *type;        // "binop", "number", "var", etc
    char *op;          // for binop: "+", "-", etc
    int value;         // for number
    char *name;        // for identifier
    struct ASTNode *left;
    struct ASTNode *right;
};

typedef struct ASTNode* ASTPtr;

ASTPtr makeNode(char *type) {
    ASTPtr node = malloc(sizeof(struct ASTNode));
    node->type = strdup(type);
    return node;
}

ASTPtr makeBinOp(ASTPtr left, char *op, ASTPtr right) {
    ASTPtr node = makeNode("binop");
    node->left = left;
    node->op = strdup(op);
    node->right = right;
    return node;
}

Bison Usage:

bison example

%union {
    int intval;
    struct ASTNode *node;
}

%type <node> expr
%type <intval> NUMBER

expr : expr PLUS expr   { $$ = makeBinOp($1, "+", $3); }
     | NUMBER           { ASTPtr n = makeNode("number");
                          n->value = $1; $$ = n; }
     ;

Symbol Table Implementation

Track variables and their properties:

Example

#define SYMBOL_TABLE_SIZE 100 struct Symbol { char *name; char *type; // "int", "float", "string" int scope; // function depth int value; // for constants }; struct Symbol symbol_table[SYMBOL_TABLE_SIZE]; int symbol_count = 0; int current_scope = 0; void declare_symbol(char *name, char *type) { if (symbol_count >= SYMBOL_TABLE_SIZE) { printf("Symbol table full\n"); return; } symbol_table[symbol_count].name = strdup(name); symbol_table[symbol_count].type = strdup(type); symbol_table[symbol_count].scope = current_scope; symbol_count++; } struct Symbol* lookup_symbol(char *name) { for (int i = symbol_count - 1; i >= 0; i--) { if (strcmp(symbol_table[i].name, name) == 0) return &symbol_table[i]; } return NULL; }

Type Checking

Validate type compatibility:

Example

int check_type(ASTPtr expr1, ASTPtr expr2, char *operation) { if (expr1->type == NULL || expr2->type == NULL) { printf("Type error\n"); return 0; } // Different type combinations if (strcmp(expr1->type, "int") == 0 && strcmp(expr2->type, "int") == 0) { return 1; // Valid } if (strcmp(expr1->type, "float") == 0 && strcmp(expr2->type, "float") == 0) { return 1; // Valid } printf("Type mismatch: %s and %s\n", expr1->type, expr2->type); return 0; }

Code Generation

Output intermediate or machine code:

Example

int code_count = 0; void gen_code(char *op, char *arg1, char *arg2, char *result) { printf("t%d = %s %s %s\n", code_count++, op, arg1, arg2); printf("%s = t%d\n", result, code_count-1); } // Example: code for 5 + 3 gen_code("ADD", "5", "3", "t0"); // Output: // t0 = ADD 5 3 // t0 = t0

Testing Your Parser

Example

#!/bin/bash # Test cases tests=( "5+3" "10*2" "(2+3)*4" "100/5" ) for test in "${tests[@]}"; do echo "Testing: $test" echo "$test" | ./parser echo "---" done

Interview Q&A

Q: How do you build an AST with Bison? A: Define a union with AST node pointers, use %type directives, create nodes in semantic actions with pointers, build tree by setting left/right pointers.

Q: How do you manage symbol tables? A: Use an array or hash table, store name/type/scope. Handle scoping by tracking function depth. Implement lookup to search most recent scope first.

Q: What's the difference between code generation and interpretation? A: Code generation produces intermediate or machine code. Interpretation directly executes AST or bytecode. Generation is faster for repeated execution.

Q: How do you handle variable scopes? A: Track scope depth (global=0, function=1, nested block=2, etc.). When looking up variables, find most recent declaration in current or outer scopes.

Q: What errors should parser projects detect? A: Syntax errors (invalid tokens), semantic errors (type mismatches, undefined variables), scope errors (variable not declared), and runtime errors (division by zero).

Learning parser generation through practical projects accelerates understanding. Here are realistic project ideas with implementation guidance.

Project Ideas by Difficulty

Beginner: Simple Calculator

Features:

Basic arithmetic: +, -, *, /
Parentheses for grouping
Error handling

Lexer:

Example

[0-9]+ { yylval = atoi(yytext); return NUMBER; } [+*/-()] { return yytext[0]; }

Parser:

bison example

expr : NUMBER           { $$ = $1; }
     | expr '+' expr    { $$ = $1 + $3; }
     | expr '*' expr    { $$ = $1 * $3; }
     | '(' expr ')'     { $$ = $2; }
     ;

Intermediate: Variable Assignment

Features:

Variable declaration: int x = 5;
Variable usage: y = x + 3;
Symbol table

Grammar Additions:

bison example

statement : TYPE IDENTIFIER '=' expr ';'  { declare($2, $1, $4); }
          | IDENTIFIER '=' expr ';'       { assign($1, $3); }
          ;

Advanced: Small Programming Language

Features:

Functions: int add(int a, int b) { return a + b; }
Control flow: if/else, while, for
Arrays
Type system
Scope management

Complexity:

Symbol table with scoping
Type checking
AST generation
Code generation or interpretation

Building AST (Abstract Syntax Tree)

Instead of evaluating directly, build a tree:

c example

struct ASTNode {
    char *type;        // "binop", "number", "var", etc
    char *op;          // for binop: "+", "-", etc
    int value;         // for number
    char *name;        // for identifier
    struct ASTNode *left;
    struct ASTNode *right;
};

typedef struct ASTNode* ASTPtr;

ASTPtr makeNode(char *type) {
    ASTPtr node = malloc(sizeof(struct ASTNode));
    node->type = strdup(type);
    return node;
}

ASTPtr makeBinOp(ASTPtr left, char *op, ASTPtr right) {
    ASTPtr node = makeNode("binop");
    node->left = left;
    node->op = strdup(op);
    node->right = right;
    return node;
}

Bison Usage:

bison example

%union {
    int intval;
    struct ASTNode *node;
}

%type <node> expr
%type <intval> NUMBER

expr : expr PLUS expr   { $$ = makeBinOp($1, "+", $3); }
     | NUMBER           { ASTPtr n = makeNode("number");
                          n->value = $1; $$ = n; }
     ;

Symbol Table Implementation

Track variables and their properties:

Example

Type Checking

Validate type compatibility:

Example

Code Generation

Output intermediate or machine code:

Example

Testing Your Parser

Example

#!/bin/bash # Test cases tests=( "5+3" "10*2" "(2+3)*4" "100/5" ) for test in "${tests[@]}"; do echo "Testing: $test" echo "$test" | ./parser echo "---" done

Interview Q&A

Q: How do you build an AST with Bison? A: Define a union with AST node pointers, use %type directives, create nodes in semantic actions with pointers, build tree by setting left/right pointers.

Q: How do you manage symbol tables? A: Use an array or hash table, store name/type/scope. Handle scoping by tracking function depth. Implement lookup to search most recent scope first.

Q: How do you handle variable scopes? A: Track scope depth (global=0, function=1, nested block=2, etc.). When looking up variables, find most recent declaration in current or outer scopes.

Practical Parser Projects

Project Ideas by Difficulty

Beginner: Simple Calculator

Intermediate: Variable Assignment

Advanced: Small Programming Language

Building AST (Abstract Syntax Tree)

Symbol Table Implementation

Type Checking

Code Generation

Testing Your Parser

Interview Q&A

Continue learning this concept

Practical Parser Projects

Project Ideas by Difficulty

Beginner: Simple Calculator

Intermediate: Variable Assignment

Advanced: Small Programming Language

Building AST (Abstract Syntax Tree)

Symbol Table Implementation

Type Checking

Code Generation

Testing Your Parser

Interview Q&A

Continue learning this concept