Home
Fine Arts
Hobby Electronics
Reading list
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 Version 5.6 is distributed under the terms of the GNU General Public License. You will need to download each of the files below.
| LR(1)AndLALR(1)ParserGenerator.lsp | LR(1) and LALR(1) parser generator program in Common LISP. |
View
Download
|
| GrammarS=SaSbEPSILON.dat | The grammar S → SaSb | ε containing productions and terminal symbols. |
View
Download
|
| ParseTablesLALR(1)_S=SaSbEPSILON.dat | Parse tables for the grammar S → SaSb | ε generated by the parser generator program containing goto graph, action and goto tables. |
View
Download
|
| ParserGenerator/LR(1)AndLALR(1)Parser.lsp | LR(1) and LALR(1) parser program in Common LISP. |
View
Download
|
| SentencesS=SaSbEPSILON.dat | Sentences to be parsed for the grammar S → SaSb | ε. |
View
Download
|
| ParsedSentencesLALR(1)S=SaSbEPSILON.dat | Parsed sentences for the grammar S → SaSb | ε. |
View
Download
|
Install and Run
Let's work through an example of creating a grammar and a parser for it and trying it out on a few test sentences in the language.
Install Common Lisp. I like to use Steel Bank Common Lisp.
Define a grammar in the file grammar.dat. This one happens to be for parsing numbers in a table of factorizations where we have primes to powers separated by . and where really large prime factors are continued on multiple lines using the backslash continuation character \ It took me a few iterations on the productions until they were general enough to avoid failing on some of my test sentences.
; Grammar.dat
;
; ---------------------------------------------------------------------------
; Grammar for Cunningham numbers factorization of p^n - 1.
;
; The factorization is given in the form p n <factors> where
; each factor is of the form p^m. Long numbers are continued on the next line with
; backslashes. Factors are separated by a period.
;
; 398 12 2^4.3.3583.4588543.34266607.2146612951394313997.8670122322845042\
; 61471.3742361194240057889227626965547117.118815764353631151\
; 104263170678136736311820574318029752573406120157089\
; 84828478898969687279497327343
;
; ---------------------------------------------------------------------------
; Productions.
(
(S -> integer integer Factorization)
(Factorization -> Factorization period Factor / Factor)
(Factor -> BigInteger ^ BigInteger / BigInteger)
(BigInteger -> BigInteger backslash integer / integer)
)
; Terminal symbols.
( integer period ^ backslash )
Start the LISP interpreter's read-evaluate-print-loop and load the parser generator.
$ ls
LR(1)AndLALR(1)Parser.lsp LR(1)AndLALR(1)ParserGenerator.lsp grammar.dat
$ sbcl
This is SBCL 1.1.6.0-3c5581a, an implementation of ANSI Common Lisp.
More information about SBCL is available at <http://www.sbcl.org/>.
...
* (load "LR(1)AndLALR(1)ParserGenerator.lsp")
T
* (parser-generator "grammar.dat" "parser.dat")
LR(1)AndLALR(1)ParserGenerator Version 5.6
An LR(1) and LALR(1) Parser Generator written in Common Lisp.
Copyright (C) 1989-2024 by Sean Erik O'Connor. All Rights Reserved.
NIL
* (quit)
The file parser.dat now contains the parse tables,
;---------------------
; LALR(1) parse tables
;---------------------
;
; Suitable for input to the Common Lisp program
;
; LR(1)AndLALR(1)Parser.lsp
;
; TERMINALS
;
(INTEGER PERIOD ^ BACKSLASH $)
; PRODUCTIONS
;
; Productions are numbered starting with 1.
; All alternates were expanded into separate productions.
(
( (1) (S -> INTEGER INTEGER FACTORIZATION) )
( (2) (FACTORIZATION -> FACTORIZATION PERIOD FACTOR) )
( (3) (FACTORIZATION -> FACTOR) )
( (4) (FACTOR -> BIGINTEGER ^ BIGINTEGER) )
( (5) (FACTOR -> BIGINTEGER) )
( (6) (BIGINTEGER -> BIGINTEGER BACKSLASH INTEGER) )
( (7) (BIGINTEGER -> INTEGER) )
)
; GOTO GRAPH
;
; Not needed for the parser, but here for reference and debugging.
; **********
; Goto graph of the LR(1) or LALR(1) grammar of the form
;
; (
; ( <-- List of links.
; (6 |a| 4) <-- Transition in Goto graph from state 6 to
; state 4 on symbol a.
; (1 |a| 2) <-- Transition from state 1 to state 2 on a.
; )
;
; ( <-- List of sets of items.
; ( 0 <-- State number 0.
; 3668 <-- Hash value of core.
; (
; (SP -> DOT S |,| $) ----+
; ( S -> DOT S |a| S |b| |,| $) |
; ( S -> DOT EPSILON |,| $) +---- Set of items for state 0
; ( S -> DOT S |a| S |b| |,| |a|) |
; ( S -> DOT EPSILON |,| |a|) |
; ) ----+
; )
(
(
(-1 NIL 0)
(0 S 1)
(0 INTEGER 2)
(2 INTEGER 3)
(3 INTEGER 4)
(3 FACTORIZATION 5)
(3 FACTOR 6)
(3 BIGINTEGER 7)
(5 PERIOD 8)
(7 ^ 9)
(7 BACKSLASH 10)
(8 INTEGER 4)
(8 FACTOR 11)
(8 BIGINTEGER 7)
(9 INTEGER 4)
(9 BIGINTEGER 13)
(10 INTEGER 14)
(13 BACKSLASH 10)
)
(
(1
1752
(SP -> S DOT |,| $)
)
(0
3968
(SP -> DOT S |,| $)
(S -> DOT INTEGER INTEGER FACTORIZATION |,| $)
)
(2
4356
(S -> INTEGER DOT INTEGER FACTORIZATION |,| $)
)
(4
4800
(BIGINTEGER -> INTEGER DOT |,| ^)
(BIGINTEGER -> INTEGER DOT |,| $)
(BIGINTEGER -> INTEGER DOT |,| PERIOD)
(BIGINTEGER -> INTEGER DOT |,| BACKSLASH)
)
(6
5322
(FACTORIZATION -> FACTOR DOT |,| $)
(FACTORIZATION -> FACTOR DOT |,| PERIOD)
)
(10
10374
(BIGINTEGER -> BIGINTEGER BACKSLASH DOT INTEGER |,| ^)
(BIGINTEGER -> BIGINTEGER BACKSLASH DOT INTEGER |,| $)
(BIGINTEGER -> BIGINTEGER BACKSLASH DOT INTEGER |,| PERIOD)
(BIGINTEGER -> BIGINTEGER BACKSLASH DOT INTEGER |,| BACKSLASH)
)
(9
13932
(FACTOR -> BIGINTEGER ^ DOT BIGINTEGER |,| $)
(FACTOR -> BIGINTEGER ^ DOT BIGINTEGER |,| PERIOD)
(BIGINTEGER -> DOT BIGINTEGER BACKSLASH INTEGER |,| $)
(BIGINTEGER -> DOT INTEGER |,| $)
(BIGINTEGER -> DOT BIGINTEGER BACKSLASH INTEGER |,| PERIOD)
(BIGINTEGER -> DOT INTEGER |,| PERIOD)
(BIGINTEGER -> DOT BIGINTEGER BACKSLASH INTEGER |,| BACKSLASH)
(BIGINTEGER -> DOT INTEGER |,| BACKSLASH)
)
(14
14940
(BIGINTEGER -> BIGINTEGER BACKSLASH INTEGER DOT |,| ^)
(BIGINTEGER -> BIGINTEGER BACKSLASH INTEGER DOT |,| $)
(BIGINTEGER -> BIGINTEGER BACKSLASH INTEGER DOT |,| PERIOD)
(BIGINTEGER -> BIGINTEGER BACKSLASH INTEGER DOT |,| BACKSLASH)
)
(11
16070
(FACTORIZATION -> FACTORIZATION PERIOD FACTOR DOT |,| $)
(FACTORIZATION -> FACTORIZATION PERIOD FACTOR DOT |,| PERIOD)
)
(7
16564
(FACTOR -> BIGINTEGER DOT ^ BIGINTEGER |,| $)
(FACTOR -> BIGINTEGER DOT |,| $)
(FACTOR -> BIGINTEGER DOT ^ BIGINTEGER |,| PERIOD)
(FACTOR -> BIGINTEGER DOT |,| PERIOD)
(BIGINTEGER -> BIGINTEGER DOT BACKSLASH INTEGER |,| ^)
(BIGINTEGER -> BIGINTEGER DOT BACKSLASH INTEGER |,| $)
(BIGINTEGER -> BIGINTEGER DOT BACKSLASH INTEGER |,| PERIOD)
(BIGINTEGER -> BIGINTEGER DOT BACKSLASH INTEGER |,| BACKSLASH)
)
(13
18363
(FACTOR -> BIGINTEGER ^ BIGINTEGER DOT |,| $)
(FACTOR -> BIGINTEGER ^ BIGINTEGER DOT |,| PERIOD)
(BIGINTEGER -> BIGINTEGER DOT BACKSLASH INTEGER |,| $)
(BIGINTEGER -> BIGINTEGER DOT BACKSLASH INTEGER |,| PERIOD)
(BIGINTEGER -> BIGINTEGER DOT BACKSLASH INTEGER |,| BACKSLASH)
)
(5
20156
(S -> INTEGER INTEGER FACTORIZATION DOT |,| $)
(FACTORIZATION -> FACTORIZATION DOT PERIOD FACTOR |,| $)
(FACTORIZATION -> FACTORIZATION DOT PERIOD FACTOR |,| PERIOD)
)
(8
23693
(FACTORIZATION -> FACTORIZATION PERIOD DOT FACTOR |,| $)
(FACTORIZATION -> FACTORIZATION PERIOD DOT FACTOR |,| PERIOD)
(FACTOR -> DOT BIGINTEGER ^ BIGINTEGER |,| $)
(FACTOR -> DOT BIGINTEGER |,| $)
(FACTOR -> DOT BIGINTEGER ^ BIGINTEGER |,| PERIOD)
(FACTOR -> DOT BIGINTEGER |,| PERIOD)
(BIGINTEGER -> DOT BIGINTEGER BACKSLASH INTEGER |,| ^)
(BIGINTEGER -> DOT INTEGER |,| ^)
(BIGINTEGER -> DOT BIGINTEGER BACKSLASH INTEGER |,| $)
(BIGINTEGER -> DOT INTEGER |,| $)
(BIGINTEGER -> DOT BIGINTEGER BACKSLASH INTEGER |,| PERIOD)
(BIGINTEGER -> DOT INTEGER |,| PERIOD)
(BIGINTEGER -> DOT BIGINTEGER BACKSLASH INTEGER |,| BACKSLASH)
(BIGINTEGER -> DOT INTEGER |,| BACKSLASH)
)
(3
26701
(S -> INTEGER INTEGER DOT FACTORIZATION |,| $)
(FACTORIZATION -> DOT FACTORIZATION PERIOD FACTOR |,| $)
(FACTORIZATION -> DOT FACTOR |,| $)
(FACTORIZATION -> DOT FACTORIZATION PERIOD FACTOR |,| PERIOD)
(FACTORIZATION -> DOT FACTOR |,| PERIOD)
(FACTOR -> DOT BIGINTEGER ^ BIGINTEGER |,| $)
(FACTOR -> DOT BIGINTEGER |,| $)
(FACTOR -> DOT BIGINTEGER ^ BIGINTEGER |,| PERIOD)
(FACTOR -> DOT BIGINTEGER |,| PERIOD)
(BIGINTEGER -> DOT BIGINTEGER BACKSLASH INTEGER |,| ^)
(BIGINTEGER -> DOT INTEGER |,| ^)
(BIGINTEGER -> DOT BIGINTEGER BACKSLASH INTEGER |,| $)
(BIGINTEGER -> DOT INTEGER |,| $)
(BIGINTEGER -> DOT BIGINTEGER BACKSLASH INTEGER |,| PERIOD)
(BIGINTEGER -> DOT INTEGER |,| PERIOD)
(BIGINTEGER -> DOT BIGINTEGER BACKSLASH INTEGER |,| BACKSLASH)
(BIGINTEGER -> DOT INTEGER |,| BACKSLASH)
)
)
)
; ACTION TABLE
;
; (state
; (item)
; ...
(
( (0)
(
(INTEGER (S 2))
(DEFAULT (ERROR))
)
)
( (1)
(
($ (ACC NIL))
(DEFAULT (ERROR))
)
)
( (2)
(
(INTEGER (S 3))
(DEFAULT (ERROR))
)
)
( (3)
(
(INTEGER (S 4))
(DEFAULT (ERROR))
)
)
( (4)
(
(^ (R 7))
($ (R 7))
(PERIOD (R 7))
(BACKSLASH (R 7))
(DEFAULT (ERROR))
)
)
( (5)
(
($ (R 1))
(PERIOD (S 8))
(DEFAULT (ERROR))
)
)
( (6)
(
($ (R 3))
(PERIOD (R 3))
(DEFAULT (ERROR))
)
)
( (7)
(
(^ (S 9))
($ (R 5))
(PERIOD (R 5))
(BACKSLASH (S 10))
(DEFAULT (ERROR))
)
)
( (8)
(
(INTEGER (S 4))
(DEFAULT (ERROR))
)
)
( (9)
(
(INTEGER (S 4))
(DEFAULT (ERROR))
)
)
( (10)
(
(INTEGER (S 14))
(DEFAULT (ERROR))
)
)
( (11)
(
($ (R 2))
(PERIOD (R 2))
(DEFAULT (ERROR))
)
)
( (13)
(
($ (R 4))
(PERIOD (R 4))
(BACKSLASH (S 10))
(DEFAULT (ERROR))
)
)
( (14)
(
(^ (R 6))
($ (R 6))
(PERIOD (R 6))
(BACKSLASH (R 6))
(DEFAULT (ERROR))
)
)
)
; GOTO TABLE
;
; (state
; (item)
; ...
(
( (0)
(
(S 1)
(DEFAULT (ERROR))
)
)
( (3)
(
(FACTORIZATION 5)
(FACTOR 6)
(BIGINTEGER 7)
(DEFAULT (ERROR))
)
)
( (8)
(
(FACTOR 11)
(BIGINTEGER 7)
(DEFAULT (ERROR))
)
)
( (9)
(
(BIGINTEGER 13)
(DEFAULT (ERROR))
)
)
)
; ERROR MESSAGE TABLE
;
; If the action table has an error state, the other non-error
; actions show which symbol was failed to appear next on the input.
;
; The user can modify these minimal error messages.
(
((0) ("error - expecting one of the symbols INTEGER"))
((1) ("error - expecting one of the symbols $"))
((2) ("error - expecting one of the symbols INTEGER"))
((3) ("error - expecting one of the symbols INTEGER"))
((4) ("error - expecting one of the symbols BACKSLASH PERIOD $ ^"))
((5) ("error - expecting one of the symbols PERIOD $"))
((6) ("error - expecting one of the symbols PERIOD $"))
((7) ("error - expecting one of the symbols BACKSLASH PERIOD $ ^"))
((8) ("error - expecting one of the symbols INTEGER"))
((9) ("error - expecting one of the symbols INTEGER"))
((10) ("error - expecting one of the symbols INTEGER"))
((11) ("error - expecting one of the symbols PERIOD $"))
((13) ("error - expecting one of the symbols BACKSLASH PERIOD $"))
((14) ("error - expecting one of the symbols BACKSLASH PERIOD $ ^"))
)
Let's try out the parser which inputs sentences and parses them using the parse tables just generated. Here are a few test sentences,
; Not correct, e.g. 2
(integer)
; Minimum correct sentence, e.g. 2 33 234234
(integer integer integer)
; Successively more complex sentences. e.g. 2 10 989080890\
; 123213123
(integer integer integer backslash integer)
; 2 10 989080890 . 2132312
(integer integer integer period integer)
; 2 10 3 ^ 6
(integer integer integer ^ integer)
; 2 10 55 . 3333232432\
; 23434234
(integer integer integer period integer backslash integer)
; 2 10 55 . 3333232432 . 12313 . 21 ^ 22332\
; 23434234\
; 454 . 23 ^ 32
(integer integer integer period integer period integer ^ integer backslash integer backslash integer period integer ^ integer)
Start LISP interpreter's read-evaluate-print-loop and load the parser.
$ sbcl
This is SBCL 1.1.6.0-3c5581a, an implementation of ANSI Common Lisp.
More information about SBCL is available at <http://www.sbcl.org/>.
...
* (load "LR(1)AndLALR(1)Parser.lsp")
T
* (parser "parser.dat" "sentences.dat" "parsed-sentences.dat")
LR(1)AndLALR(1)ParserGenerator Version 5.6
An LR(1) and LALR(1) Parser Generator written in Common Lisp.
Copyright (C) 1989-2024 by Sean Erik O'Connor. All Rights Reserved.
...
NIL
* (quit)
Here are the parsed sentences,
Parsing the sentence: (INTEGER)
PARSE STACK INPUT STACK ACTION
(0) (INTEGER $) (SHIFT 2)
(0 INTEGER 2) ($) ERROR
error - expecting one of the symbols INTEGER
Sentence was not in the grammar.
Parsing the sentence: (INTEGER INTEGER INTEGER)
PARSE STACK INPUT STACK ACTION
(0) (INTEGER INTEGER INTEGER $) (SHIFT 2)
(0 INTEGER 2) (INTEGER INTEGER $) (SHIFT 3)
(0 INTEGER 2 INTEGER 3) (INTEGER $) (SHIFT 4)
(0 INTEGER 2 INTEGER 3 INTEGER 4) ($) (REDUCE 7 (BIGINTEGER -> INTEGER))
(0 INTEGER 2 INTEGER 3 BIGINTEGER 7) ($) (REDUCE 5 (FACTOR -> BIGINTEGER))
(0 INTEGER 2 INTEGER 3 FACTOR 6) ($) (REDUCE 3 (FACTORIZATION -> FACTOR))
(0 INTEGER 2 INTEGER 3 FACTORIZATION 5) ($) (REDUCE 1 (S -> INTEGER INTEGER FACTORIZATION))
(0 S 1) ($) (ACCEPT)
Sentence was grammatical.
Parsing the sentence: (INTEGER INTEGER INTEGER BACKSLASH INTEGER)
PARSE STACK INPUT STACK ACTION
(0) (INTEGER INTEGER INTEGER BACKSLASH INTEGER $) (SHIFT 2)
(0 INTEGER 2) (INTEGER INTEGER BACKSLASH INTEGER $) (SHIFT 3)
(0 INTEGER 2 INTEGER 3) (INTEGER BACKSLASH INTEGER $) (SHIFT 4)
(0 INTEGER 2 INTEGER 3 INTEGER 4) (BACKSLASH INTEGER $) (REDUCE 7 (BIGINTEGER -> INTEGER))
(0 INTEGER 2 INTEGER 3 BIGINTEGER 7)(BACKSLASH INTEGER $) (SHIFT 10)
(0 INTEGER 2 INTEGER 3 BIGINTEGER 7 BACKSLASH 10) (INTEGER $) (SHIFT 14)
(0 INTEGER 2 INTEGER 3 BIGINTEGER 7 BACKSLASH 10 INTEGER 14) ($) (REDUCE 6 (BIGINTEGER -> BIGINTEGER BACKSLASH INTEGER))
(0 INTEGER 2 INTEGER 3 BIGINTEGER 7) ($) (REDUCE 5 (FACTOR -> BIGINTEGER))
(0 INTEGER 2 INTEGER 3 FACTOR 6) ($) (REDUCE 3 (FACTORIZATION -> FACTOR))
(0 INTEGER 2 INTEGER 3 FACTORIZATION 5) ($) (REDUCE 1 (S -> INTEGER INTEGER FACTORIZATION))
(0 S 1) ($) (ACCEPT)
Sentence was grammatical.
Parsing the sentence: (INTEGER INTEGER INTEGER PERIOD INTEGER)
PARSE STACK INPUT STACK ACTION
(0) (INTEGER INTEGER INTEGER PERIOD INTEGER $) (SHIFT 2)
(0 INTEGER 2) (INTEGER INTEGER PERIOD INTEGER $) (SHIFT 3)
(0 INTEGER 2 INTEGER 3) (INTEGER PERIOD INTEGER $) (SHIFT 4)
(0 INTEGER 2 INTEGER 3 INTEGER 4) (PERIOD INTEGER $) (REDUCE 7 (BIGINTEGER -> INTEGER))
(0 INTEGER 2 INTEGER 3 BIGINTEGER 7) (PERIOD INTEGER $) (REDUCE 5 (FACTOR -> BIGINTEGER))
(0 INTEGER 2 INTEGER 3 FACTOR 6) (PERIOD INTEGER $) (REDUCE 3 (FACTORIZATION -> FACTOR))
(0 INTEGER 2 INTEGER 3 FACTORIZATION 5) (PERIOD INTEGER $) (SHIFT 8)
(0 INTEGER 2 INTEGER 3 FACTORIZATION 5 PERIOD 8) (INTEGER $) (SHIFT 4)
(0 INTEGER 2 INTEGER 3 FACTORIZATION 5 PERIOD 8 INTEGER 4) ($) (REDUCE 7 (BIGINTEGER -> INTEGER))
(0 INTEGER 2 INTEGER 3 FACTORIZATION 5 PERIOD 8 BIGINTEGER 7) ($) (REDUCE 5 (FACTOR -> BIGINTEGER))
(0 INTEGER 2 INTEGER 3 FACTORIZATION 5 PERIOD 8 FACTOR 11) ($) (REDUCE 2 (FACTORIZATION -> FACTORIZATION PERIOD FACTOR))
(0 INTEGER 2 INTEGER 3 FACTORIZATION 5) ($) (REDUCE 1 (S -> INTEGER INTEGER FACTORIZATION))
(0 S 1) ($) (ACCEPT)
Sentence was grammatical.
Parsing the sentence: (INTEGER INTEGER INTEGER ^ INTEGER)
PARSE STACK INPUT STACK ACTION
(0) (INTEGER INTEGER INTEGER ^ INTEGER $) (SHIFT 2)
(0 INTEGER 2) (INTEGER INTEGER ^ INTEGER $) (SHIFT 3)
(0 INTEGER 2 INTEGER 3) (INTEGER ^ INTEGER $) (SHIFT 4)
(0 INTEGER 2 INTEGER 3 INTEGER 4) (^ INTEGER $) (REDUCE 7 (BIGINTEGER -> INTEGER))
(0 INTEGER 2 INTEGER 3 BIGINTEGER 7) (^ INTEGER $) (SHIFT 9)
(0 INTEGER 2 INTEGER 3 BIGINTEGER 7 ^ 9) (INTEGER $) (SHIFT 4)
(0 INTEGER 2 INTEGER 3 BIGINTEGER 7 ^ 9 INTEGER 4) ($) (REDUCE 7 (BIGINTEGER -> INTEGER))
(0 INTEGER 2 INTEGER 3 BIGINTEGER 7 ^ 9 BIGINTEGER 13) ($) (REDUCE 4 (FACTOR -> BIGINTEGER ^ BIGINTEGER))
(0 INTEGER 2 INTEGER 3 FACTOR 6) ($) (REDUCE 3 (FACTORIZATION -> FACTOR))
(0 INTEGER 2 INTEGER 3 FACTORIZATION 5) ($) (REDUCE 1 (S -> INTEGER INTEGER FACTORIZATION))
(0 S 1) ($) (ACCEPT)
Sentence was grammatical.
Parsing the sentence: (INTEGER INTEGER INTEGER PERIOD INTEGER BACKSLASH INTEGER)
PARSE STACK INPUT STACK ACTION
(0) (INTEGER INTEGER INTEGER PERIOD INTEGER BACKSLASH INTEGER $) (SHIFT 2)
(0 INTEGER 2) (INTEGER INTEGER PERIOD INTEGER BACKSLASH INTEGER $) (SHIFT 3)
(0 INTEGER 2 INTEGER 3) (INTEGER PERIOD INTEGER BACKSLASH INTEGER $) (SHIFT 4)
(0 INTEGER 2 INTEGER 3 INTEGER 4) (PERIOD INTEGER BACKSLASH INTEGER $) (REDUCE 7 (BIGINTEGER -> INTEGER))
(0 INTEGER 2 INTEGER 3 BIGINTEGER 7)(PERIOD INTEGER BACKSLASH INTEGER $) (REDUCE 5 (FACTOR -> BIGINTEGER))
(0 INTEGER 2 INTEGER 3 FACTOR 6) (PERIOD INTEGER BACKSLASH INTEGER $) (REDUCE 3 (FACTORIZATION -> FACTOR))
(0 INTEGER 2 INTEGER 3 FACTORIZATION 5)(PERIOD INTEGER BACKSLASH INTEGER $) (SHIFT 8)
(0 INTEGER 2 INTEGER 3 FACTORIZATION 5 PERIOD 8)(INTEGER BACKSLASH INTEGER $) (SHIFT 4)
(0 INTEGER 2 INTEGER 3 FACTORIZATION 5 PERIOD 8 INTEGER 4)(BACKSLASH INTEGER $) (REDUCE 7 (BIGINTEGER -> INTEGER))
(0 INTEGER 2 INTEGER 3 FACTORIZATION 5 PERIOD 8 BIGINTEGER 7)(BACKSLASH INTEGER $) (SHIFT 10)
(0 INTEGER 2 INTEGER 3 FACTORIZATION 5 PERIOD 8 BIGINTEGER 7 BACKSLASH 10) (INTEGER $) (SHIFT 14)
(0 INTEGER 2 INTEGER 3 FACTORIZATION 5 PERIOD 8 BIGINTEGER 7 BACKSLASH 10
INTEGER 14) ($) (REDUCE 6 (BIGINTEGER -> BIGINTEGER BACKSLASH INTEGER))
(0 INTEGER 2 INTEGER 3 FACTORIZATION 5 PERIOD 8 BIGINTEGER 7) ($) (REDUCE 5 (FACTOR -> BIGINTEGER))
(0 INTEGER 2 INTEGER 3 FACTORIZATION 5 PERIOD 8 FACTOR 11) ($) (REDUCE 2 (FACTORIZATION -> FACTORIZATION PERIOD FACTOR))
(0 INTEGER 2 INTEGER 3 FACTORIZATION 5) ($) (REDUCE 1 (S -> INTEGER INTEGER FACTORIZATION))
(0 S 1) ($) (ACCEPT)
Sentence was grammatical.
Parsing the sentence: (INTEGER INTEGER INTEGER PERIOD INTEGER PERIOD INTEGER ^
INTEGER BACKSLASH INTEGER BACKSLASH INTEGER PERIOD
INTEGER ^ INTEGER)
PARSE STACK INPUT STACK ACTION
(0) (INTEGER INTEGER INTEGER PERIOD INTEGER PERIOD INTEGER ^ INTEGER BACKSLASH
INTEGER BACKSLASH INTEGER PERIOD INTEGER ^ INTEGER $) (SHIFT 2)
(0 INTEGER 2) (INTEGER INTEGER PERIOD INTEGER PERIOD INTEGER ^ INTEGER BACKSLASH INTEGER
BACKSLASH INTEGER PERIOD INTEGER ^ INTEGER $) (SHIFT 3)
(0 INTEGER 2 INTEGER 3) (INTEGER PERIOD INTEGER PERIOD INTEGER ^ INTEGER BACKSLASH INTEGER BACKSLASH
INTEGER PERIOD INTEGER ^ INTEGER $) (SHIFT 4)
(0 INTEGER 2 INTEGER 3 INTEGER 4) (PERIOD INTEGER PERIOD INTEGER ^ INTEGER BACKSLASH INTEGER BACKSLASH INTEGER
PERIOD INTEGER ^ INTEGER $) (REDUCE 7 (BIGINTEGER -> INTEGER))
(0 INTEGER 2 INTEGER 3 BIGINTEGER 7)(PERIOD INTEGER PERIOD INTEGER ^ INTEGER BACKSLASH INTEGER BACKSLASH INTEGER
PERIOD INTEGER ^ INTEGER $) (REDUCE 5 (FACTOR -> BIGINTEGER))
(0 INTEGER 2 INTEGER 3 FACTOR 6) (PERIOD INTEGER PERIOD INTEGER ^ INTEGER BACKSLASH INTEGER BACKSLASH INTEGER
PERIOD INTEGER ^ INTEGER $) (REDUCE 3 (FACTORIZATION -> FACTOR))
(0 INTEGER 2 INTEGER 3 FACTORIZATION 5)(PERIOD INTEGER PERIOD INTEGER ^ INTEGER BACKSLASH INTEGER BACKSLASH INTEGER
PERIOD INTEGER ^ INTEGER $) (SHIFT 8)
(0 INTEGER 2 INTEGER 3 FACTORIZATION 5 PERIOD 8)(INTEGER PERIOD INTEGER ^ INTEGER BACKSLASH INTEGER BACKSLASH INTEGER PERIOD
INTEGER ^ INTEGER $) (SHIFT 4)
(0 INTEGER 2 INTEGER 3 FACTORIZATION 5 PERIOD 8 INTEGER 4)(PERIOD INTEGER ^ INTEGER BACKSLASH INTEGER BACKSLASH INTEGER PERIOD INTEGER ^
INTEGER $) (REDUCE 7 (BIGINTEGER -> INTEGER))
(0 INTEGER 2 INTEGER 3 FACTORIZATION 5 PERIOD 8 BIGINTEGER 7)(PERIOD INTEGER ^ INTEGER BACKSLASH INTEGER BACKSLASH INTEGER PERIOD INTEGER ^
INTEGER $) (REDUCE 5 (FACTOR -> BIGINTEGER))
(0 INTEGER 2 INTEGER 3 FACTORIZATION 5 PERIOD 8 FACTOR 11)(PERIOD INTEGER ^ INTEGER BACKSLASH INTEGER BACKSLASH INTEGER PERIOD INTEGER ^
INTEGER $) (REDUCE 2 (FACTORIZATION -> FACTORIZATION PERIOD FACTOR))
(0 INTEGER 2 INTEGER 3 FACTORIZATION 5)(PERIOD INTEGER ^ INTEGER BACKSLASH INTEGER BACKSLASH INTEGER PERIOD INTEGER ^
INTEGER $) (SHIFT 8)
(0 INTEGER 2 INTEGER 3 FACTORIZATION 5 PERIOD 8)(INTEGER ^ INTEGER BACKSLASH INTEGER BACKSLASH INTEGER PERIOD INTEGER ^ INTEGER
$) (SHIFT 4)
(0 INTEGER 2 INTEGER 3 FACTORIZATION 5 PERIOD 8 INTEGER 4)(^ INTEGER BACKSLASH INTEGER BACKSLASH INTEGER PERIOD INTEGER ^ INTEGER $) (REDUCE 7 (BIGINTEGER -> INTEGER))
(0 INTEGER 2 INTEGER 3 FACTORIZATION 5 PERIOD 8 BIGINTEGER 7)(^ INTEGER BACKSLASH INTEGER BACKSLASH INTEGER PERIOD INTEGER ^ INTEGER $) (SHIFT 9)
(0 INTEGER 2 INTEGER 3 FACTORIZATION 5 PERIOD 8 BIGINTEGER 7 ^ 9)(INTEGER BACKSLASH INTEGER BACKSLASH INTEGER PERIOD INTEGER ^ INTEGER $) (SHIFT 4)
(0 INTEGER 2 INTEGER 3 FACTORIZATION 5 PERIOD 8 BIGINTEGER 7 ^ 9 INTEGER 4)(BACKSLASH INTEGER BACKSLASH INTEGER PERIOD INTEGER ^ INTEGER $) (REDUCE 7 (BIGINTEGER -> INTEGER))
(0 INTEGER 2 INTEGER 3 FACTORIZATION 5 PERIOD 8 BIGINTEGER 7 ^ 9 BIGINTEGER 13)(BACKSLASH INTEGER BACKSLASH INTEGER PERIOD INTEGER ^ INTEGER $) (SHIFT 10)
(0 INTEGER 2 INTEGER 3 FACTORIZATION 5 PERIOD 8 BIGINTEGER 7 ^ 9 BIGINTEGER 13
BACKSLASH 10)(INTEGER BACKSLASH INTEGER PERIOD INTEGER ^ INTEGER $) (SHIFT 14)
(0 INTEGER 2 INTEGER 3 FACTORIZATION 5 PERIOD 8 BIGINTEGER 7 ^ 9 BIGINTEGER 13
BACKSLASH 10 INTEGER 14)(BACKSLASH INTEGER PERIOD INTEGER ^ INTEGER $) (REDUCE 6 (BIGINTEGER -> BIGINTEGER BACKSLASH INTEGER))
(0 INTEGER 2 INTEGER 3 FACTORIZATION 5 PERIOD 8 BIGINTEGER 7 ^ 9 BIGINTEGER 13)(BACKSLASH INTEGER PERIOD INTEGER ^ INTEGER $) (SHIFT 10)
(0 INTEGER 2 INTEGER 3 FACTORIZATION 5 PERIOD 8 BIGINTEGER 7 ^ 9 BIGINTEGER 13
BACKSLASH 10)(INTEGER PERIOD INTEGER ^ INTEGER $) (SHIFT 14)
(0 INTEGER 2 INTEGER 3 FACTORIZATION 5 PERIOD 8 BIGINTEGER 7 ^ 9 BIGINTEGER 13
BACKSLASH 10 INTEGER 14)(PERIOD INTEGER ^ INTEGER $) (REDUCE 6 (BIGINTEGER -> BIGINTEGER BACKSLASH INTEGER))
(0 INTEGER 2 INTEGER 3 FACTORIZATION 5 PERIOD 8 BIGINTEGER 7 ^ 9 BIGINTEGER 13)(PERIOD INTEGER ^ INTEGER $) (REDUCE 4 (FACTOR -> BIGINTEGER ^ BIGINTEGER))
(0 INTEGER 2 INTEGER 3 FACTORIZATION 5 PERIOD 8 FACTOR 11)(PERIOD INTEGER ^ INTEGER $) (REDUCE 2 (FACTORIZATION -> FACTORIZATION PERIOD FACTOR))
(0 INTEGER 2 INTEGER 3 FACTORIZATION 5)(PERIOD INTEGER ^ INTEGER $) (SHIFT 8)
(0 INTEGER 2 INTEGER 3 FACTORIZATION 5 PERIOD 8)(INTEGER ^ INTEGER $) (SHIFT 4)
(0 INTEGER 2 INTEGER 3 FACTORIZATION 5 PERIOD 8 INTEGER 4) (^ INTEGER $) (REDUCE 7 (BIGINTEGER -> INTEGER))
(0 INTEGER 2 INTEGER 3 FACTORIZATION 5 PERIOD 8 BIGINTEGER 7) (^ INTEGER $) (SHIFT 9)
(0 INTEGER 2 INTEGER 3 FACTORIZATION 5 PERIOD 8 BIGINTEGER 7 ^ 9) (INTEGER $) (SHIFT 4)
(0 INTEGER 2 INTEGER 3 FACTORIZATION 5 PERIOD 8 BIGINTEGER 7 ^ 9 INTEGER 4) ($) (REDUCE 7 (BIGINTEGER -> INTEGER))
(0 INTEGER 2 INTEGER 3 FACTORIZATION 5 PERIOD 8 BIGINTEGER 7 ^ 9 BIGINTEGER 13) ($) (REDUCE 4 (FACTOR -> BIGINTEGER ^ BIGINTEGER))
(0 INTEGER 2 INTEGER 3 FACTORIZATION 5 PERIOD 8 FACTOR 11) ($) (REDUCE 2 (FACTORIZATION -> FACTORIZATION PERIOD FACTOR))
(0 INTEGER 2 INTEGER 3 FACTORIZATION 5) ($) (REDUCE 1 (S -> INTEGER INTEGER FACTORIZATION))
(0 S 1) ($) (ACCEPT)
Sentence was grammatical.
Looks good!
