Sin( x y ) Image Border.

LR( 1 ) and LALR( 1 ) Parser Generator and Parser in Lisp

Overview

This is an implementation in Common Lisp of a parser generator and parser for LR(1) and LALR(1) grammars which can handle ε productions.

Features

The parser generator creates the sets of items, goto graph, and action and goto tables for both LR(1) and LALR(1) grammars. It gives the same parsing tables (and conflicts) as the bison or yacc compiler-compiler utility of UNIX, except for possible renumbering of states. I've tested the program on several grammars, including those with ε productions and parsing conflicts.

The input to the program is the grammar.dat file which lists the productions of the grammar. The output is the parse tables file, parser.dat file which lists the productions, the parser's sets of items (i.e. goto graph), the action table and the goto table.

The companion bottom up parser accepts the LR(1) or LALR(1) a parse tables file generated above and a set of sentences to be parsed. It writes the results of the parsing to an output file.

The parse tables file contains the productions, goto graph (for debugging), action table, goto table, and a table of error messages.

It would be wise to review parsing theory.

Download

Source code is distributed under the terms of the GNU General Public License You will need to download each of the files below. The current version number is 5.6

Click on the symbol to view and download the source files below.
Parser generator program	LR(1) and LALR(1) parser generator program in Common LISP.
Grammar file	for the grammar, S → SaSb \| ε containing productions and terminal symbols.
LR(1) parse tables file	for the grammar S → SaSb \| ε generated by the parser generator program containing goto graph, action and goto tables.
LALR(1) parse tables file	for the grammar S → SaSb \| ε generated by the parser generator program containing goto graph, action and goto tables.
Grammar file	for a grammar of arithmetic expressions.
LR(1) parse tables file	for arithmetic expression grammar generated by the program.
LALR(1) parse tables file	for arithmetic expression grammar generated by the program.

Click on the symbol to view and download the source files below.
Parser program	LR(1) and LALR(1) parser program in Common LISP.
Sentences to be parsed	for the grammar S → SaSb \| ε
Parsed sentences	for the grammar S → SaSb \| ε output using the LALR(1) parse tables.
Sentences to be parsed	for the arithmetic grammar.
Parsed sentences	for the arithmetic grammar using the LALR(1) parse tables.

Install and Run

Install Common Lisp.
Edit the directory paths in the base-path! function in both the files LR(1)AndLALR(1)ParserGenerator.lsp and LR(1)AndLALR(1)Parser.lsp.
Go into the LISP interpreter's read-evaluate-print-loop and load the parser generator and parser (load "LR(1)AndLALR(1)ParserGenerator.lsp") followed by (load "LR(1)AndLALR(1)Parser.lsp")
Run (test-parser-generator) to generate parse tables for a few sample grammars, followed by (test-parser) to parse some sample sentences.

Thanks to the Common Lisp Directory people who have listed my under Parser Generators

Home