Lambda Calculus Parser (C)

This project is a small standalone parser for untyped lambda calculus expressions, written in C.

It takes a lambda expression as a command-line argument, lexes it, parses it into an abstract syntax tree (AST), and prints a structured representation of that AST to standard output.

The implementation is intentionally minimal and self-contained, focusing on parsing mechanics rather than evaluation or reduction.

Features

• Lexer for a minimal lambda calculus syntax

• Recursive Pratt-style parser with explicit precedence handling

• AST construction for:

  • identifiers

  • lambda abstractions

  • applications

• Tree-shaped, human-readable AST output

• No external dependencies beyond the C standard library

Syntax

The supported lambda calculus syntax is:

Lambda abstraction: λx.<expr>

Application: juxtaposition (f x)

Parentheses for grouping: (expr)

Identifiers: single alphabetic characters (a–z, A–Z)

The lambda symbol is represented internally as the UTF-8 sequence for λ.

Examples of valid expressions:

λx.x
(λx.x) y
λx.λy.(x y)

Build

make

No additional libraries are required.

Usage

Run the parser by passing a lambda expression as a single argument:

./lambda "λx.x"

Example output:

Lambda(x)
└── BODY
    Ident(x)

Another example:

./lambda "λx.(x λy.y ((λx.x) b)) a"

Produces :

λx.(xλy.y((λx.x)b))a
Lambda(x)
└── BODY
    Application
    ├── LEFT
    │   Application
    │   ├── LEFT
    │   │   Ident(x)
    │   └── RIGHT
    │       Lambda(y)
    │       └── BODY
    │           Application
    │           ├── LEFT
    │           │   Ident(y)
    │           └── RIGHT
    │               Application
    │               ├── LEFT
    │               │   Lambda(x)
    │               │   └── BODY
    │               │       Ident(x)
    │               └── RIGHT
    │                   Ident(b)
    └── RIGHT
        Ident(a)

Implementation Notes

The lexer produces a flat token stream with explicit END termination.

Parsing is done using a precedence-based approach:

lambda abstraction has lower precedence

application binds more tightly

Memory management is manual; the entire AST is recursively freed after use.

Error handling is minimal and designed for experimentation rather than user-facing robustness.

Current limitations

No evaluation or beta-reduction

Identifiers are single characters

No alpha-conversion or variable capture handling

Error reporting is basic

This project is intended as a parsing experiment and educational reference, not a full lambda calculus interpreter.