Haskell interface to Bison for LR(1) parsing

A small Haskell toolchain that drives GNU Bison to produce LR(1) parse tables and a runnable pushdown automaton (PDA) parser for very small grammars. It generates a Bison grammar from a compact custom format, runs Bison with XML reports, parses the report, and exposes the automaton & tables in Haskell for interactive parsing.

Features

• Convert a simple plaintext grammar description into a Bison .y file.
• Run bison --xml and parse the XML report to extract LR(1) states, transitions and reductions.
• Build internal action/goto tables and run a stack-based LR(1) parser in a REPL.
• Normalizes token names between Bison and single-character terminals used in the input grammar.
• Generates intermediate code (three-address code) for parsed input strings.

Requirements

• GHC (8.x or later)
• Cabal or Stack (optional; you can also ghc --make)
• GNU Bison (with --xml report support)
• Haskell packages: text, containers, xml-conduit (used by Text.XML)

Project layout

• exe/Main.hs — main program: reads grammar.txt, generates grammar.y, runs Bison, builds automaton and starts a REPL parser.
• exe/GenBison.hs — generates Bison .y from compact productions.
• exe/BisonXML.hs — parses Bison XML report into Haskell data structures.
• grammar.txt — example grammar input format (see below).
• table.rep / grammar.xml — example Bison output produced in a run.

Input format (grammar.txt)

Plain text file with:

1. Non-terminals line (space separated single characters)
2. Terminals line (space separated single characters)
3. Start symbol (single character)
4. Blank line
5. Productions, one per line as LHS RHS where LHS and RHS are sequences of characters (LHS typically single character). Example:

E T F
a + - * / ( )
E

E E+T
E T
T T*F
T F
F (E)
F a

The tool maps terminals to Bison token names and emits a .y file.

Quick start

1. Place your grammar in grammar.txt.
2. Build and run the executable:
   • with GHC: ghc -o bison_parser exe/Main.hs exe/GenBison.hs exe/BisonXML.hs && ./bison_parser
   • or with Stack/Cabal if you create a project file.
3. The program will:
   • create grammar.y
   • run Bison to produce grammar.xml and table.rep
   • parse the report and print states and tables
   • start a REPL to parse input strings interactively and output intermediate code.

Notes

• The tool assumes very small, single-character tokens and nonterminals. Token name mapping for common symbols is built-in (e.g. + → PLUS).
• Bison must be available in PATH. The program invokes bison to create the XML report.

Files of interest

• Main.hs — orchestration, I/O, parsing REPL
• GenBison.hs — grammar → Bison generator
• BisonXML.hs — XML → internal representation
• grammar.txt — example grammar used during development

Designed as a university project for learning about parser generators and LR parsing.