Earley Parser

A Python implementation of the Earley parsing algorithm for context-free grammars.

Overview

This project provides a clean implementation of the Earley parsing algorithm, which can handle any context-free grammar without transformation. The parser reads grammar rules from a text file, processes input strings, and generates parse trees for accepted inputs.

Features

• Supports any context-free grammar, including ambiguous ones
• Handles epsilon (ε) productions
• Generates visual parse trees
• Provides detailed logging of the parsing process
• Simple grammar definition through text files

Installation

Clone the repository:

git clone https://github.com/yourusername/earley-parser.git
cd earley-parser

No additional dependencies required beyond Python's standard library.

Usage

Grammar Format

Define your grammar in a text file with one rule per line:

S → T a | b | ε
T → S | b a T

Where:

• Capital letters represent non-terminal symbols
• Lowercase letters represent terminal symbols
• → separates the head from the body of a rule
• | separates alternative productions
• ε represents an empty string

Running the Parser

python earley-parser.py [grammar_file]

If no grammar file is specified, the program will look for grammar.txt in the current directory.

Example

For the grammar in grammar.txt:

S → T a | b | ε
T → S | b a T

And input string b a b a, the parser will:

1. Trace the parsing process
2. Show the final chart
3. Generate a parse tree
4. Indicate if the string is accepted

Parsing: 'b a b a'
[PREDICT] Expanding S at position 0
...
--- Chart ---
Chart[0]:
  γ → • S (0)
  S → • T a (0)
  S → • b (0)
  S → • (0)
  ...

--- Parse Tree ---
S
└── T
    ├── S
    │   └── b
    └── a
└── a

✓ Accepted by the grammar

How It Works

The Earley algorithm works in three phases:

1. Prediction: Expand non-terminals by adding all their production rules to the current set
2. Scanning: Match terminal symbols with the input and advance the dot
3. Completion: When a rule is completed, advance all rules waiting for that non-terminal

The parser tracks the exact derivation path using backpointers, allowing it to build a parse tree for accepted inputs.

Contributing

Contributions are welcome! Please feel free to submit a Pull Request.

License

This project is licensed under the MIT License - see the LICENSE file for details.

Acknowledgments

• Developed as a seminar work for the Models of Computation course
• Based on Jay Earley's original algorithm from 1970