rd-parser

Recursive-descent parser for arithmetic expressions.

Formal Languages and Computability (UFPB) Authors: Gabriel Bringel Gonçalves, Miguel Mochizuki Silva

Grammar

E  -> ( E Op E )
E  -> a
Op -> +  |  -  |  *  |  /

Terminals: (, ), +, -, *, /, a. Non-terminals: E and Op.

The FIRST sets for the two productions of E are disjoint: FIRST(( E Op E )) = {'('} and FIRST(a) = {'a'}. The four Op productions also begin with distinct terminals. Since there are no empty productions, the grammar is LL(1): one lookahead token is enough to choose a production, without backtracking. That is why recursive-descent parsing works here — each non-terminal becomes a function (parse_E and parse_Op).

Whitespace is not part of the grammar. During lexical analysis, every character recognized by str.isspace() — such as spaces, tabs, and line breaks — is discarded before syntactic analysis.

Running the parser

Requires Python 3.10 or later and no external dependencies.

# analyze an expression passed as an argument
python3 src/main.py "(a * (a + a))"

# interactive mode (without an argument): reads expressions until 'exit' or Ctrl-D
python3 src/main.py

# also show the token list produced by the lexer
python3 src/main.py --tokens "(a + a)"

# explicitly disable ANSI colors
python3 src/main.py --no-color "(a + a)"

# alternatively, run it as a module
python3 -m src.main "(a + a)"

Exit code: 0 for a valid expression and 1 for invalid input. When output is a terminal, the interface uses ANSI colors automatically. Colors are disabled when output is redirected, with --no-color, or when the NO_COLOR environment variable is set.

Valid-expression example

$ python3 src/main.py "(a * (a + a))"
◆ SYNTAX TREE
E
├── (
├── E
│   └── a
├── Op
│   └── *
├── E
│   ├── (
│   ├── E
│   │   └── a
│   ├── Op
│   │   └── +
│   ├── E
│   │   └── a
│   └── )
└── )

✓ Valid expression.

Error examples

Syntax error — note that a + a does not belong to this language because every operation must be enclosed in parentheses:

$ python3 src/main.py "a + a"
✗ Invalid expression.
Syntax error: expected end of input, found '+'
  a + a
    ^
  (column 3)

$ python3 src/main.py "(a + )"
✗ Invalid expression.
Syntax error: expected '(' or 'a', found ')'
  (a + )
       ^
  (column 6)

Lexical error — a character outside the grammar alphabet:

$ python3 src/main.py "a & a"
✗ Invalid expression.
Lexical error: invalid character '&'
  a & a
    ^
  (column 3)

Other rejected inputs: `` (empty), (), `(a)`, `(a a)`, `(a++a)`, `(a + a`, `(a+a)a`, `a)`, `b`, `1`.

Code structure

File	Responsibility
src/__init__.py	identifies src as a Python package
src/errors.py	LexError / ParseError exceptions and the error message with a ^ marker
src/lexer.py	TokenType, Token, and tokenize() — input string → token list
src/tree.py	syntax-tree nodes (one per production) and render_tree()
src/parser.py	Parser: peek/advance/expect, parse_E, parse_Op, parse
src/main.py	command-line interface and interactive mode
src/ui.py	presentation, ANSI colors, banner, sections, and token table
tests/test_parser.py	automated tests (unittest)

The tree is concrete: it retains the consumed parentheses, so traversing its leaves reconstructs the original input.

Tests

python3 -m unittest discover -s tests -v

The tests cover lexical analysis (types, positions, whitespace, and invalid characters), valid expressions, every error case with its expected position, multi-line errors, tabs, exit codes, interactive mode, recursion handling, and tree rendering. They also verify automatic colors, NO_COLOR, --no-color, and the token table.