CC-assingment-2

Stars
5
Language
Python
Updated
View on GitHub

Mini Compiler — Lexical & Syntactic Front-End

This project implements the lexical analysis and CFG-based syntactic analysis (recursive-descent parser) phases for the course assignment. The repository is designed to consume the token stream produced by the lexer, parse the program according to a context-free grammar, and demonstrate leftmost/rightmost derivations and parse trees as required by Question 2.

Question 2: What is required

Question 2 asks you to:

  • Design a complete Context-Free Grammar (CFG) that generates the core language (declarations, assignments, arithmetic and boolean expressions, if-else, while, blocks, print).
  • Ensure the grammar can generate the provided evaluation program without modification.
  • Demonstrate syntactic validation by showing a leftmost derivation, a rightmost derivation, and the parse tree for at least one non-trivial statement.
  • The parser must consume the token stream produced by the lexical analyzer.

How this implementation satisfies Q2

  • Grammar: The CFG is printed by parser.py via the print_cfg() function and is the grammar implemented by the parser. It includes productions for program, stmt_list, stmt, decl_stmt, assign_stmt, if_stmt, while_stmt, print_stmt, block, bool_expr, bool_term, bool_factor, comparison, expr, term, and factor.
  • Lexer → Parser: main() in parser.py creates a Lexer(source), calls tokenize() and then passes the returned token list to Parser(tokens) — so the parser directly consumes the lexer’s token stream.
  • Derivations & Parse Tree: After successful parsing the program, parser.py collects top-level statements and prompts the user to select a statement (or all). For each selected statement it prints:
    • leftmost derivation (via derive_leftmost),
    • rightmost derivation (via derive_rightmost), and
    • the parse tree (via print_tree).

These outputs directly demonstrate syntactic validation exactly as required by Question 2.

Files and key code explanation

  • lexer.py

    • Implements token definitions using regex and a Lexer class.
    • tokenize() returns a list of Token(type, lexeme, line, column) and appends an EOF token.
    • print_token_table() shows the token stream (used for Question 1).

  • parser.py

    • Node: lightweight parse-tree node (name, children, optional token).
    • Parser (recursive-descent): operates over a token list with methods:
      • program(), stmt_list(), stmt() — top-level control
      • declaration(), assignment(), if_stmt(), while_stmt(), print_stmt(), block() — statement-level rules
      • bool_expr(), bool_term(), bool_factor(), comparison() — boolean and relational handling
      • expr(), term(), factor() — arithmetic expressions with precedence
    • Error handling: expect() raises ParseError with line/col for clear diagnostics.
    • Derivation helpers: derive_leftmost, derive_rightmost, render_form build and show derivation steps.
    • collect_statements() finds derivable statements for demonstration; show_derivations() prints derivations + parse tree.

How to run (examples you can demo)

  1. Print tokens (Question 1):
python lexer.py evaluation_program.src
  1. Parse and interactively show derivations (Question 2):
python parser.py evaluation_program.src

When prompted, enter a statement number, a source line number, comma list, or all. To script showing the while statement (example):

printf '8\n' | python parser.py evaluation_program.src

To show derivations for all statements:

printf 'all\n' | python parser.py evaluation_program.src

What to present for the evaluation (suggestion)

  • Show the token stream from lexer.py to demonstrate Question 1.
  • Use parser.py and select a non-trivial statement (e.g., the while loop or the if (!(avg < 5.0)) statement) and present:
    • leftmost derivation
    • rightmost derivation
    • the parse tree

These three outputs satisfy the syntactic validation requirements of Question 2.

  • Add semantic analysis: symbol table with scopes, undeclared/multiple declaration checks, and type checking.
  • Generate intermediate code (three-address code) and apply simple optimizations.
  • Add a small README section for how to present outputs in the viva.

If you want, I can now:

  • add a short “presenter’s notes” section to this README with exact terminal commands and sample screenshots of outputs, or
  • implement the symbol table and basic semantic checks next.

If you want me to proceed, tell me which next step to take.

hello world