A parser for LALR(1) grammars in Haskell

Usage:

lr-demo MyGrammar.cf < MyInput.txt

Prints the generated LALR(1) parse table for context-free grammar MyGrammar.cf and a trace of shift and reduce actions of the parser when accepting MyInput.txt.

The input .cf file consists of labelled BNF rules (LBNF) of the form:

LABEL "." NONTERMINAL "::=" (NONTERMINAL | TERMINAL)* ";"

For example:

Par.  S ::= "(" S ")" S ;
Done. S ::= ;

This format is compatible with BNFC (but BNFC pragmas are not recognized).

Limitation: terminals can only be single characters.

Getting started

1. Have Haskell Stack installed.
2. Clone and enter this repository.
3. Execute: stack run lr-demo -- test/BalancedParentheses.cf < test/BalPar.txt

Using the following grammar:

Done . S ::=;
Par . S ::= "(" S ")" S;

Generated parse table:

State 0

	eof	reduce with rule Done
	'('	shift to state 1

	S 	goto state 2

State 1

	'('	shift to state 1
	')'	reduce with rule Done

	S 	goto state 3

State 2

	eof	reduce with rule %start

State 3

	')'	shift to state 4

State 4

	eof	reduce with rule Done
	'('	shift to state 1
	')'	reduce with rule Done

	S 	goto state 5

State 5

	eof	reduce with rule Par
	')'	reduce with rule Par


Parsing stdin...
            . '(' ')'  -- shift
'('         . ')'      -- reduce with rule Done
'(' S       . ')'      -- shift
'(' S ')'   .          -- reduce with rule Done
'(' S ')' S .          -- reduce with rule Par
S           .          -- halt

Reference

stack run -- --help

License

BSD 3-clause.