Mini Arithmetic Language Compiler

A complete implementation of a compiler for a simple arithmetic expression language, demonstrating lexical analysis, syntactic analysis, and formal language concepts.

Output

📋 Table of Contents

• Overview
• Features
• Project Structure
• Installation
• Usage
• Language Specification
• Compiler Architecture
• Examples
• Technical Details
• Contributing
• License

📖 Overview

This project implements a mini compiler for an arithmetic expression language as part of a formal language theory demonstration. It covers the fundamental stages of compiler front-end design including:

• Lexical Analysis: Token identification using Deterministic Finite Automata (DFA)
• Syntactic Analysis: Recursive descent parsing with Context-Free Grammar (CFG)
• Grammar Analysis: Left recursion elimination, FIRST and FOLLOW sets
• Semantic Analysis: Expression validation and error detection

The project demonstrates how formal language theory provides the theoretical foundation for modern compilers and interpreters.

✨ Features

Core Features

• ✅ Tokenization: Identifies identifiers, numbers, operators, and parentheses
• ✅ DFA Implementation: Deterministic Finite Automata for identifiers and numbers
• ✅ Grammar Analysis: Original grammar with left recursion elimination
• ✅ Recursive Descent Parser: Predictive parsing using grammar after left recursion removal
• ✅ Parse Tree Generation: Visual representation of syntactic structure
• ✅ Expression Validation: Accepts/rejects expressions based on language rules
• ✅ Error Detection: Clear error messages for syntax and semantic errors

Language Support

• Identifiers: a, b, x, total1, num2
• Numbers: 12, 50, 1000
• Operators: +, -, *, /
• Parentheses: (, )

Modes of Operation

• Demonstration Mode: Shows complete compilation pipeline with examples
• Interactive Mode: Enter expressions to compile in real-time
• Command-Line Mode: Compile specific expressions directly

📁 Project Structure

mini_compiler/
├── main.py # Entry point and demonstration
├── lexer/
│ ├── **init**.py
│ ├── token.py # Token classes and enums
│ └── lexer.py # Lexical analyzer with DFA
├── parser/
│ ├── **init**.py
│ ├── ast.py # Abstract Syntax Tree nodes
│ └── parser.py # Recursive descent parser
├── analyzer/
│ ├── **init**.py
│ ├── grammar.py # Grammar analysis utilities
│ └── validator.py # Expression validation
└── utils/
├── **init**.py
└── printer.py # Pretty printing utilities

🔧 Installation

Prerequisites

• Python 3.6 or higher
• No external dependencies required

Setup

1. Clone the repository:

git clone link
cd mini-compiler

2. Verify installation:

python main.py --help

🚀 Usage

Method 1: Run Full Demonstration

python main.py

This runs a comprehensive demonstration with:

• All test expressions
• Grammar analysis
• DFA diagrams
• Parse tree visualization

Method 2: Compile a Specific Expression

python main.py "a+b*c"
python main.py "(a+b)*(c+d)"
python main.py "100+25*2"

Method 3: Interactive Mode

python main.py
# Then type 'y' when prompted for interactive mode
# Enter expressions one by one

Method 4: Use as a Module

from lexer import Lexer
from parser import Parser

# Lexical analysis
lexer = Lexer("a+b*c")
tokens = lexer.tokenize()

# Syntactic analysis
parser = Parser(tokens)
ast = parser.parse()

📚 Language Specification

Grammar (After Left Recursion Elimination)

E  -> T E'
E' -> + T E' | - T E' | ε
T  -> F T'
T' -> * F T' | / F T' | ε
F  -> (E) | id | num

Token Definitions

Token Type	Pattern	Example
IDENTIFIER	letter(letter|digit)*	a, b, x1
NUMBER	digit+	12, 50, 1000
PLUS	+	+
MINUS	-	-
MULT	*	*
DIV	/	/
LPAREN	(	(
RPAREN	)	)

Accepted Expressions

• a+b
• a*b+c
• (a+b)*c
• x+y*z
• (a+b)*(c+d)
• 100+25
• num1*value2

Rejected Expressions

• +a (starts with operator)
• a+ (ends with operator)
• a** (invalid operator sequence)
• (a+b (unbalanced parentheses)
• a+b) (unbalanced parentheses)
• */ab (invalid operator sequence)
• a+*b (invalid operator sequence)

🏗️ Compiler Architecture

┌─────────────────────────────────────────────────┐
│           SOURCE PROGRAM                        │
│         (a+b*c, x+y*z, etc.)                   │
└──────────────────┬──────────────────────────────┘
                   │
                   ▼
┌─────────────────────────────────────────────────┐
│           LEXICAL ANALYZER                      │
│         (Scanner/Tokenizer)                    │
│      Identifies: id, num, +, -, *, /, (, )    │
└──────────────────┬──────────────────────────────┘
                   │
                   ▼
┌─────────────────────────────────────────────────┐
│           TOKEN STREAM                         │
│   [id, +, id, *, id, EOF]                     │
└──────────────────┬──────────────────────────────┘
                   │
                   ▼
┌─────────────────────────────────────────────────┐
│           SYNTAX ANALYZER                      │
│         (Parser)                              │
│      Recursive Descent Parsing                │
│      Grammar: E -> T E'                       │
└──────────────────┬──────────────────────────────┘
                   │
                   ▼
┌─────────────────────────────────────────────────┐
│           PARSE TREE                          │
│          (AST)                                │
│      Represents the syntactic structure       │
└──────────────────┬──────────────────────────────┘
                   │
                   ▼
┌─────────────────────────────────────────────────┐
│           SEMANTIC ANALYSIS                    │
│         (Optional)                            │
│      Type checking, validation                │
└─────────────────────────────────────────────────┘

💡 Examples

Example 1: Compiling "a+b*c"

Token Stream:

Token(IDENTIFIER, 'a', line=1, col=1)
Token(PLUS, '+', line=1, col=2)
Token(IDENTIFIER, 'b', line=1, col=3)
Token(MULT, '*', line=1, col=4)
Token(IDENTIFIER, 'c', line=1, col=5)
Token(EOF, 'EOF', line=1, col=6)

Parse Tree:

E
├── T
│   ├── F
│   │   └── a
│   └── T'
│       └── ε
└── E'
    ├── '+'
    ├── T
    │   ├── F
    │   │   └── b
    │   └── T'
    │       ├── '*'
    │       ├── F
    │       │   └── c
    │       └── T'
    │           └── ε
    └── E'
        └── ε

Example 2: Leftmost Derivation for "a+b*c"

E
=> T E'
=> F T' E'
=> id T' E'
=> a E'
=> a + T E'
=> a + F T' E'
=> a + b T' E'
=> a + b * F T' E'
=> a + b * c

Example 3: Rightmost Derivation for "a+b*c"

E
=> T E'
=> T + T E'
=> T + T
=> T + F T'
=> T + b T'
=> T + b * F
=> T + b * c
=> a + b * c

🔬 Technical Details

DFA for Identifiers

State q0 = Start
State q1 = Accept

q0 --letter--> q1
q1 --letter/digit--> q1

DFA for Numbers

State q0 = Start
State q1 = Accept

q0 --digit--> q1
q1 --digit--> q1

FIRST and FOLLOW Sets

Symbol	FIRST	FOLLOW
E	{(, id, num}	{), $}
T	{(, id, num}	{+, -, ), $}
F	{(, id, num}	{*, /, +, -, ), $}
E'	{+, -, ε}	{), $}
T'	{*, /, ε}	{+, -, ), $}

Operator Precedence

1. Highest: Parentheses ( )
2. Medium: Multiplication *, Division /
3. Lowest: Addition +, Subtraction -

🧪 Testing

Test Expressions

The project includes a comprehensive test suite with both accepted and rejected expressions:

Accepted:

test_expressions = [
    "a+b",
    "a*b+c",
    "(a+b)*c",
    "x+y*z",
    "(a+b)*(c+d)",
    "100+25",
    "num1*value2"
]

Rejected:

test_expressions = [
    "+a",      # Starts with operator
    "a+",      # Ends with operator
    "a**",     # Invalid operator sequence
    "(a+b",    # Unbalanced parentheses
    "a+b)",    # Unbalanced parentheses
    "*/ab",    # Invalid operator sequence
    "a+*b"     # Invalid operator sequence
]

Running Tests

# Run all tests
python main.py

# Test specific expression
python main.py "a+b*c"

📖 Educational Value

This project demonstrates:

1. Formal Language Theory in practice
2. Compiler Design fundamentals
3. Automata Theory (DFA implementation)
4. Grammar Theory (left recursion elimination)
5. Parsing Techniques (recursive descent)
6. Software Engineering principles (modular design)

🤝 Contributing

Contributions are welcome! Here's how you can help:

1. Fork the repository
2. Create a feature branch (git checkout -b feature/AmazingFeature)
3. Commit your changes (git commit -m 'Add some AmazingFeature')
4. Push to the branch (git push origin feature/AmazingFeature)
5. Open a Pull Request

Areas for Improvement

• Add support for more operators (e.g., %, ^)
• Implement semantic analysis (type checking)
• Add code generation (e.g., generate Python bytecode)
• Implement error recovery in the parser
• Add unit tests
• Create a web interface

📝 License

This project is licensed under the MIT License - see the LICENSE file for details.

🙏 Acknowledgments

• Based on the project requirements from the Faculty of Engineering and Technology, Department of Computer Engineering
• Inspired by the formal language theory concepts from:
  • "Compilers: Principles, Techniques and Tools" by Aho, Lam, Sethi, and Ullman
  • "Introduction to Automata Theory, Languages and Computation" by Hopcroft, Motwani, and Ullman

📧 Contact

For questions or feedback, please contact:

• Project Lead: [SIAHA TOUKO AUBIN]
• Email: [[email protected]]
• Department: Department of Computer Engineering
• Faculty: Faculty of Engineering and Technology

📚 References

1. A. V. Aho, M. Lam, R. Sethi, and J. Ullman, Compilers: Principles, Techniques and Tools, 2nd Edition.
2. J. Hopcroft, R. Motwani, and J. Ullman, Introduction to Automata Theory, Languages and Computation.
3. K. Louden, Compiler Construction: Principles and Practice.
4. M. Sipser, Introduction to the Theory of Computation.

🌟 Quick Start

# Clone the repository
git clone [Repo_link]
cd mini-compiler

# Run the demonstration
python main.py

# Compile an expression
python main.py "a+b*c"