Compiler Construction Project — BSCS 7th Semester (2024)

University of Central Punjab (UCP) Program: Bachelor of Science in Computer Science (BSCS) Semester: 7th Semester — Fall 2024 Course: Compiler Construction Instructor: Ma'am Arooj Zahra

---

👨💻 Author

Ali Zaman

• 📧 Email: alizaman6780@gmail.com
• 🔗 LinkedIn: linkedin.com/in/ali-zaman-web-developer
• 🐙 GitHub: github.com/MyProVerse
• 📦 Repository: Compiler-Construction-BSCS-F24-Batch-Project-UCP

---

📌 Project Overview

This project is a two-phase implementation of a Compiler Front-End built as part of the Compiler Construction course in the 7th semester. The project covers the first two stages of compiler design: Lexical Analysis (Phase 1) and Syntax Analysis (Phase 2). It targets a custom language that extends standard C++ constructs with Urdu-inspired keywords (agar, magar, loop), designed as an educational exploration of compiler design principles.

The project is implemented entirely in C++ and processes plain text source code files, producing structured token streams and parse trees as output.

---

🗂️ Repository Structure

Compiler-Construction-BSCS-F24-Batch-Project-UCP/
│
├── Phase1/
│   ├── code.cpp              # Lexical analyzer (scanner) source
│   ├── sourcecode.txt        # Input: source code to be analyzed
│   ├── Token.txt             # Output: classified tokens with line numbers
│   ├── Error.txt             # Output: lexical error log
│   └── RE and FA.pdf         # Documentation: Regular Expressions & Finite Automata
│
├── phase2/
│   ├── grammar, first and follow and LL1 table/
│   │   ├── first and follow.txt   # First and Follow sets documentation
│   │   ├── LL1.docx               # LL(1) Parsing Table (Word document)
│   │   └── revised grammar.txt    # Grammar rules used by the parser
│   ├── scanner.cpp           # Updated scanner (lexer) for Phase 2
│   ├── main.cpp              # LL(1) recursive descent parser
│   ├── sourcecode.txt        # Input: source code to be parsed
│   ├── Token.txt             # Output: token stream from scanner
│   ├── TokenError.txt        # Output: lexical error log (Phase 2)
│   ├── Error.txt             # Output: syntax/parse error log
│   └── parse_tree.txt        # Output: parse tree derivations
│
└── README.md

---

⚙️ Phase 1 — Lexical Analysis

What Is Lexical Analysis?

Lexical analysis is the first phase of a compiler. It reads raw source code character by character and groups characters into meaningful units called tokens. Each token is classified by type (keyword, identifier, number, operator, etc.) and associated with a line number for error reporting.

Task & Requirements

The task for Phase 1 was to:

1. Define Regular Expressions (REs) for each token category
2. Design corresponding Finite Automata (FAs) for each RE
3. Implement a working lexical analyzer in C++ that:
   • Reads source code from a plain text file
   • Classifies every lexeme into its correct token category
   • Records the line number of each token
   • Outputs all recognized tokens to a file
   • Logs any unrecognized characters as errors

Token Categories Recognized

Token Type	Examples
KEYWORD	int, float, for, if, else, return, agar, magar, loop
IDENTIFIER	main, _num1, num_2, sum, result
NUMBER	10, 20, 3.14, 0
OPERATOR	+, -, *, /, =, <, >, <<, ==, !=
PUNCTUATION	(, ), {, }, [, ], ,, ;
STRING LITERAL	"Sum is greater than 20"

Custom Keywords

The language includes Urdu-derived keywords alongside standard C++ keywords:

Custom Keyword	Meaning
agar	if
magar	else
loop	custom loop construct

Files — Phase 1

File	Role	Direction
sourcecode.txt	The source code to be lexically analyzed	Input
code.cpp	The lexical analyzer program	Source
Token.txt	All recognized tokens with type and line number	Output
Error.txt	All unrecognized/invalid tokens with line number	Output
RE and FA.pdf	Theoretical documentation of REs and FAs for each token class	Documentation

How It Works

1. The program opens sourcecode.txt and reads the entire file into a string
2. It scans character by character using a processCode() function
3. Comments (// and /* */) are detected and skipped
4. String literals between double quotes are captured whole
5. Each other sequence is matched against: letters/underscore (→ keyword or identifier), digits (→ number), known operator characters (→ operator), or known punctuation characters (→ punctuation)
6. Unmatched characters are written to the error log
7. All tokens are written to Token.txt with format: TYPE: lexeme (Line N)

How to Run — Phase 1

Prerequisites: A C++ compiler (g++ recommended)

# Step 1: Place your source code in sourcecode.txt
# Step 2: Compile the lexer
g++ -o lexer code.cpp

# Step 3: Run the lexer
./lexer

# Step 4: View output
cat Token.txt
cat Error.txt

Expected output in Token.txt:

KEYWORD: int (Line 1)
IDENTIFIER: main (Line 1)
PUNCTUATION: ( (Line 1)
PUNCTUATION: ) (Line 1)
...

---

⚙️ Phase 2 — Syntax Analysis (LL(1) Parser)

What Is Syntax Analysis?

Syntax analysis is the second phase of a compiler. It takes the stream of tokens produced by the lexical analyzer and checks whether they conform to the grammatical rules of the language. The result is a parse tree (or derivation sequence) that represents the hierarchical structure of the source program.

This phase implements a top-down, recursive descent LL(1) parser — meaning it parses input from Left to right, produces a Leftmost derivation, and uses 1 token of lookahead.

Task & Requirements

The task for Phase 2 was to:

1. Define a context-free grammar (CFG) for the language, eliminating left recursion and left factoring to make it LL(1) compatible
2. Compute First and Follow sets for all non-terminals
3. Construct the LL(1) Parsing Table with panic-mode error recovery entries
4. Implement a recursive descent parser in C++ that:
   • Reads tokens from the token file produced by the scanner
   • Applies grammar productions to derive the program structure
   • Outputs each production applied as a parse tree derivation
   • Reports syntax errors with line numbers

Grammar Overview (revised grammar.txt)

The grammar covers the following constructs:

Construct	Production
Function definition	Function → Type identifier < ArgList > CompoundStmt
Argument list	ArgList → Arg ArgList' with comma-separated repetition
Type	Type → int | float
Variable declaration	Declaration → Type IdentList ;
Statements	Stmt → ForStmt | IfStmt | LoopStmt | Declaration | Expr ; | CompoundStmt | ;
For loop	ForStmt → for < Expr ; OptExpr ; OptExpr > Stmt
Custom if/else	IfStmt → agar < Expr > Stmt MagarPart
Custom loop	LoopStmt → loop < Expr > Stmt
Expression hierarchy	Expr → Rvalue → Mag → Term → Factor
Grouping	Factor → < Expr > | identifier | number

First & Follow Sets (first and follow.txt)

First and Follow sets were computed for all 20+ non-terminals in the grammar. These sets are the mathematical foundation used to build the LL(1) parsing table — they determine which production to apply given the current input token.

Sample sets:

Non-Terminal	FIRST Set	FOLLOW Set
Function	{int, float}	{$}
Stmt	{for, loop, agar, {, int, float, ;, <, identifier, number}	{}, magar, $, ...}
Expr	{<, identifier, number}	{;, >}
MagarPart	{magar, ε}	Follow(Stmt)

LL(1) Parsing Table (LL1.docx)

The parsing table maps every (Non-Terminal, Input Token) pair to the production to apply. Every non-terminal includes panic-mode error recovery — when an unexpected token is encountered, the parser skips input tokens until it finds a token in the non-terminal's Follow set, at which point parsing resumes.

Files — Phase 2

File	Role	Direction
sourcecode.txt	Source code to be compiled	Input
scanner.cpp	Lexical analyzer — produces tokens from source	Source / Step 1
Token.txt	Token stream output from scanner	Intermediate Output
TokenError.txt	Lexical errors detected during scanning	Output
main.cpp	LL(1) recursive descent parser	Source / Step 2
Error.txt	Syntax errors detected during parsing	Output
parse_tree.txt	Grammar productions applied during parsing	Output
grammar, first and follow and LL1 table/revised grammar.txt	Formal grammar rules for the language	Documentation
grammar, first and follow and LL1 table/first and follow.txt	Computed First and Follow sets	Documentation
grammar, first and follow and LL1 table/LL1.docx	LL(1) parsing table with panic-mode recovery	Documentation

How It Works

1. Scanner runs first: scanner.cpp reads sourcecode.txt and writes classified tokens to Token.txt and any lexical errors to TokenError.txt
2. Parser reads tokens: main.cpp opens Token.txt and parses each line to reconstruct the token stream into Token structs (type, lexeme, line number)
3. Recursive descent parsing: Starting from parseFunction(), the parser calls sub-functions for each non-terminal. Each function checks the current lookahead token and applies the matching production
4. Production output: Every production applied is written to parse_tree.txt, forming a textual derivation trace
5. Error handling: When a mismatch is found, the error is logged to Error.txt with the line number and expected token, then panic-mode recovery is applied

How to Run — Phase 2

Prerequisites: A C++ compiler (g++ recommended)

# Step 1: Place your source code in sourcecode.txt

# Step 2: Compile and run the scanner first
g++ -o scanner scanner.cpp
./scanner
# This generates Token.txt and TokenError.txt

# Step 3: Compile and run the parser
g++ -o parser main.cpp
./parser
# This generates parse_tree.txt and Error.txt

# Step 4: View outputs
cat Token.txt        # Token stream
cat TokenError.txt   # Lexical errors
cat parse_tree.txt   # Parse derivations
cat Error.txt        # Syntax errors

---

🧪 Sample Source Code & Expected Output

Input (sourcecode.txt — Phase 1 sample)

int main() {
    int _num1 = 10;
    int num_2 = 20;
    int sum = _num1 + num_2;

    if (sum > 20) {
        cout << "Sum is greater than 20" << endl;
    } else {
        cout << "Sum is less than or equal to 20" << endl;
    }

    return 0;
}

Output (Token.txt — Phase 1 sample)

KEYWORD: int (Line 1)
IDENTIFIER: main (Line 1)
PUNCTUATION: ( (Line 1)
PUNCTUATION: ) (Line 1)
PUNCTUATION: { (Line 1)
KEYWORD: int (Line 2)
IDENTIFIER: _num1 (Line 2)
OPERATOR: = (Line 2)
NUMBER: 10 (Line 2)
PUNCTUATION: ; (Line 2)
...
STRING LITERAL: "Sum is greater than 20" (Line 6)
...

Parse Tree Output (parse_tree.txt — Phase 2 sample)

Function → Type identifier < ArgList > CompoundStmt
Type → int
ArgList → Arg ArgList'
Arg → Type identifier
ArgList' → ε
CompoundStmt → { StmtList }
StmtList → ε

---

📐 Theoretical Foundations

Regular Expressions (Phase 1)

Each token category was formally defined using regular expressions before implementation:

• Identifiers: ^[_a-zA-Z][_a-zA-Z0-9]*$
• Numbers: ^[+-]?([0-9]+(\.[0-9]+)?([Ee][+-]?[0-9]+)?)$
• Operators: Union of all single and double-character operator symbols
• Keywords: Union of all reserved words including agar, magar, loop

Finite Automata (Phase 1)

For each RE, a corresponding Finite Automaton (FA) was designed with defined states, transitions, start states, and accept states. These are documented with full diagrams in RE and FA.pdf.

LL(1) Parsing (Phase 2)

The grammar was designed to satisfy the LL(1) property — no left recursion and no ambiguity in production selection. This was verified by confirming that for every non-terminal, its First/Follow sets have no conflicts. The recursive descent parser is a direct implementation of the LL(1) parsing algorithm.

---

🎓 What Was Achieved

This project delivered a complete compiler front-end pipeline as an educational implementation:

• A fully functional lexical analyzer that tokenizes C++ and custom-language source code, handles comments, string literals, compound operators, and underscore-prefixed identifiers
• A formally defined, LL(1)-compatible context-free grammar with proper left-factoring and elimination of left recursion
• Mathematically computed First and Follow sets for all grammar non-terminals
• A complete LL(1) parsing table with panic-mode error recovery for all non-terminals
• A working recursive descent parser that produces a derivation trace and reports syntax errors with line numbers
• Integration of Urdu-inspired custom keywords (agar, magar, loop) into a formal grammar, demonstrating extensibility of language design

Both phases together implement the theoretical concepts of a compiler front-end as taught in the Compiler Construction course, covering the full pipeline from raw source text to a structured parse tree.

---

🛠️ Technologies Used

• Language: C++
• Standard Libraries: <iostream>, <fstream>, <string>, <vector>
• Compiler: g++ (GCC)
• Documentation: PDF (RE & FA diagrams), DOCX (LL(1) table), plain text

---

📄 License

MIT License

Copyright (c) 2024 Ali Zaman

Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.