Arithmetic Expression Parser

A compiler front-end capable of tokenizing and parsing arithmetic expressions using Flex (Lexer) and Bison (Yacc). It was developed as part of an undergraduate coursework in Language Processors and received recognition for its implementation clarity.

Project Scope

This program is strictly a front-end implementation. It deals exclusively with:

1. Tokenization (Lexical Analysis)
2. Parsing (Syntax Analysis)

It verifies whether the input string conforms to the grammar specified in arithmetic.y. It does not generate machine code or assembly.

Behavior

• Valid Input: If the string is valid according to the grammar, the program interprets it and prints the string representation of the result, indicating the different identifiers, the type of operations performed between them and in what sequence.
• Invalid Input: If the string violates the grammar, the program reports a Syntax Error and prints the partial valid string (the part of the input that was successfully processed before the error occurred).

---

Features

• LALR(1) Parsing: Uses Yacc/Bison to handle grammar rules.
• Tokenization: Uses Lex/Flex to identify integers, identifiers, and operators.
• Operator Support: Handles Addition (+), Subtraction (-), Multiplication (*), Division (/), Modulo (%), and Power (^).
• Error Handling: Reports syntax errors for invalid expressions.

Prerequisites

To build this project, you need the standard C build tools along with Flex and Bison.

Ubuntu/Debian/WSL:

sudo apt-get install flex bison make gcc

MacOS:

brew install flex bison

Build Instructions

This project includes a Makefile for automated building.

1. Clone the repository:

   git clone https://github.com/CellerCity/arithmetic-expression-parser.git
   cd arithmetic-expression-parser

2. Compile the parser:

   make

   This generates the lex.yy.c and y.tab.c intermediate files and compiles them into the arithmetic executable.

3. Clean the build (Optional): To remove the binary and generated source files:

   make clean

Usage

Run the executable and enter any arithmetic string involving +, -, *, /, (, ), ^, % operators. Operands may be integers or any alphanumeric variables (starting with a letter).

./arithmetic

Test Cases

To verify the parser is working correctly, you can try the following inputs. The parser outputs a trace of the identified tokens and operations.

1. Basic Arithmetic:

10 + 20 * 5

2. Parentheses & Variables:

(a + b) * c

3. Power and Modulo:

x ^ 2 % 5

4. Complex Nested Expression:

((2 * x) + 5) / (y - 1)