Basic Polynomial Parser

A C++ parser and interpreter for a small polynomial language with semantic validation, program execution, static warnings, and degree analysis.

Overview

Basic Polynomial Parser reads a structured program from standard input, validates polynomial declarations and execution statements, then runs the tasks requested by the input file. It is useful as a compact compiler-construction project: the code moves from lexical analysis to recursive-descent parsing, AST-like data structures, semantic checks, interpretation, and static analysis.

The strongest part of the project is that it does more than parse syntax. It builds enough program representation to evaluate nested polynomial calls, track memory for variables, report semantic errors with line numbers, detect uninitialized variable usage, flag useless assignments, and compute polynomial degrees.

Preview

TASKS
    1 5 2
POLY
    T(X, Y) = 2 Y^2 (X^2 + Y)^2;
    Y = x + 5555;
EXECUTE
    INPUT A;
    w = Y(A);
    OUTPUT w;
    w = T(A, 10);
INPUTS
    9

Example output:

5564
T: 6
Y: 1

Highlights

• Implements a recursive-descent parser for a sectioned polynomial language: TASKS, POLY, EXECUTE, and INPUTS.
• Evaluates polynomial programs with variables, integer inputs, assignments, outputs, nested polynomial calls, coefficients, exponents, and grouped terms.
• Performs semantic validation for duplicate polynomial declarations, invalid monomial variables, undeclared polynomial calls, and wrong argument counts.
• Adds static analysis tasks for uninitialized variable use and overwritten assignments whose values are never read.
• Computes polynomial degree recursively, including nested parenthesized term lists and exponent multiplication.
• Includes a supplied regression suite covering syntax errors, semantic error codes, execution output, warnings, and degree reporting.

Features

Parsing and validation

• Tokenizes keywords, identifiers, numbers, operators, parentheses, commas, and semicolons.
• Parses polynomial headers with explicit parameter lists or implicit single-variable x.
• Reports syntax failures using the project-specified SYNTAX ERROR !!!!!&%!! output.

Semantic analysis

• Semantic Error Code 1: duplicate polynomial declarations.
• Semantic Error Code 2: monomial variables not declared in the polynomial header.
• Semantic Error Code 3: calls to undeclared polynomials.
• Semantic Error Code 4: polynomial calls with the wrong number of arguments.

Execution and analysis tasks

• Task 2 executes the program and prints requested outputs.
• Task 3 warns about uninitialized variables used in outputs or polynomial arguments.
• Task 4 warns about assignments overwritten or left unread.
• Task 5 prints each polynomial's degree.

Tech Stack

Layer	Technology	Purpose
Language	C++	Parser, semantic analyzer, interpreter, and analysis logic.
Input model	Standard input	Reads complete source programs without file-specific coupling.
Lexer	Custom LexicalAnalyzer	Converts characters into tokens and supports lookahead with peek().
Parser	Recursive descent	Mirrors the grammar with focused parse_* methods.
Test runner	Bash + diff	Runs supplied input fixtures against expected outputs.

Architecture

flowchart TD
    A[Source program on stdin] --> B[InputBuffer]
    B --> C[LexicalAnalyzer]
    C --> D[Recursive-descent Parser]
    D --> E[Polynomial declarations]
    D --> F[Statement list]
    D --> G[Input values]
    E --> H[Semantic checks]
    F --> H
    H --> I{Requested TASKS}
    I -->|Task 1| J[Syntax and semantic error output]
    I -->|Task 2| K[Interpreter output]
    I -->|Task 3| L[Uninitialized variable warnings]
    I -->|Task 4| M[Useless assignment warnings]
    I -->|Task 5| N[Polynomial degree report]

Loading

How It Works

1. The lexer reads all tokens from standard input and stores them for parser lookahead.
2. The parser consumes the required sections in order: TASKS, POLY, EXECUTE, then INPUTS.
3. Polynomial declarations are stored with headers, parameter lists, and linked term-list structures.
4. Execution statements are parsed into a linked statement list while variable memory slots and warning candidates are tracked.
5. Semantic errors, warnings, execution results, and degree reports are emitted according to the task numbers requested by the program.

Setup

Prerequisites

• A C++ compiler with C++11 support, such as g++ or clang++.
• Bash for the supplied provided_code/test1.sh regression script.

Build

From the repository root:

g++ provided_code/*.cc -std=c++11 -o a.out

If using clang++:

clang++ provided_code/*.cc -std=c++11 -o a.out

Run

./a.out < provided_tests/Task_2/t1.txt

Expected output:

5

Test

bash provided_code/test1.sh

The script expects an executable named a.out in the repository root and compares every provided_tests/**/*.txt input against its .expected output.

Usage

A program has four sections:

TASKS
    1 2 3 4 5
POLY
    F = x + 2;
    G(X, Y) = X^2 + 3 Y;
EXECUTE
    INPUT a;
    w = G(F(a), 4);
    OUTPUT w;
INPUTS
    3

Task numbers control which behaviors run:

Task	Output
1	Syntax and semantic error reporting.
2	Program execution output.
3	Warning Code 1 for uninitialized variable use.
4	Warning Code 2 for useless assignments.
5	Polynomial degree report.

Key Decisions

Decision	Rationale	Tradeoff
Recursive-descent parser	Keeps grammar rules visible as small parser methods and makes syntax errors easy to localize.	Grammar changes require direct code changes instead of regenerating a parser.
Pre-tokenized lexer with lookahead	Simplifies parser decisions such as distinguishing identifiers from polynomial calls.	Stores the token stream in memory before parsing begins.
Linked statement and term-list structures	Matches the recursive grammar and supports sequential execution.	Manual allocation keeps the code low-level and requires care if extended.
Global memory table for execution variables	Provides a compact interpreter model for INPUT, assignment, and OUTPUT.	Shared global state makes repeated interpreter runs in one process harder without reset logic.
Task-driven output	Follows the input contract and lets one program request multiple analyses.	Output behavior is coupled to task ordering and project-specific formatting.

Repository Layout

.
|-- provided_code/
|   |-- inputbuf.*              # Character input buffer
|   |-- lexer.*                 # Tokenizer and lookahead
|   |-- parser.*                # Parser, semantic checks, interpreter, main
|   `-- test1.sh                # Fixture test runner
`-- provided_tests/             # Inputs and expected outputs by task/error type