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 Compact disk icon for source code download. to view and download the source files below.
Compact disk icon for source code download. Parser generator program LR(1) and LALR(1) parser generator program in Common LISP.
Compact disk icon for source code download. Grammar file for the grammar, S → SaSb | ε containing productions and terminal symbols.
Compact disk icon for source code download. LR(1) parse tables file for the grammar S → SaSb | ε generated by the parser generator program containing goto graph, action and goto tables.
Compact disk icon for source code download. LALR(1) parse tables file for the grammar S → SaSb | ε generated by the parser generator program containing goto graph, action and goto tables.
Compact disk icon for source code download. Grammar file for a grammar of arithmetic expressions.
Compact disk icon for source code download. LR(1) parse tables file for arithmetic expression grammar generated by the program.
Compact disk icon for source code download. LALR(1) parse tables file for arithmetic expression grammar generated by the program.

 

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

Install and Run

  1. Install Common Lisp.
  2. 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.
  3. 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")
  4. 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


Copyright © 1986-2014 by Sean Erik O'Connor. All Rights Reserved.     last updated 01 Jan 14.