CS524: Using SLRGEN to Construct
Shift/Reduce Parse Tables
13Feb08

We have a code available that will allow you to produce your own examples of the SLR parsing machine which we considered last week. As part of building this machine, the First and Follow sets are computed and displayed.

You can either copy the executable to your own account, or run it from mine ~stewart/cs524/slrgen < example > example.out

Here's an example that we have already looked at - the block structure grammar, G0,

program ::= BEGIN stmts END eof .
stmts   ::= stmt ; stmts .
stmts   ::=  .
stmt    ::= SimpleS .
stmt    ::= BEGIN stmts END .
Note: the period (.) at the end of each grammar rule is important to SLRGEN to signal the end of a grammar production. This example was worked in lecture last week from the ACTION and GOTO tables provided in our text and I would ask that you construct your own copy of the grammar today in lab and run it through slrgen.

Last week, in class, you were pointed to the G3 grammar for arithmetic expressions. You received email at the beginning of the semester on the need to make a grammar unambigous, and the G3 grammar was derived and sent earlier. The G3 grammar which we will work through today constructing the CFSM

s ::= e  .
e ::= e + t .
e ::= t .
t ::= t * p .
t ::= p .
p ::= id .
p ::= ( e ) .

SLRGEN - An SLR(1) Table Generator Written by Dr. Barney MacCabe, UNM

Slrgen is an SLR(1) parse table generator specifically tailored for use with compilers written in Pascal. Slrgen reads a sequence of grammar rules from standard input and generates the files ``ptables'' and ``gramconst.h'' as well as a human readable version of the files on standard output. ``Ptables'' contains the (ASCII, but encoded) machine readable version of the parsing tables, while ``gramconst.h'' contains constant definitions suitable for inclusion in a Pascal program with a #include Berkeley Pascal compiler directive.

Input to slrgen consists of a sequence of grammar rules. Each grammar rule must consist of an identifier, followed by the symbol ``::='', followed by a sequence of zero or more identifiers. Any rule may have an action indicator, which must appear last. When present, an action indicator consists of the symbol ``#'' followed immediately by an identifier. Each rule must be terminated by the symbol ``.''.

All lexical objects must be separated by spaces. Any identifier which never appears on the left hand side of the ``::='' symbol and is not used in an action indicator is assumed to be a terminal symbol in the grammar. The first nonterminal (identifier on the left hand side of the ``::='' symbol) is assumed to be the start symbol for the grammar. Action indicators are used to indicate that semantic processing is associated with the rule.

*** probably all that's useful to cs 524 / Spring 2008***

The same action indicator may be used as the semantic action associated with several productions. Of course, the semantic action taken will be the same. Rules without action indicators are assumed to have no associated semantic processing. Ptables is a text file consisting of the identifiers used in the grammar, followed by parsing state descriptions, followed by production descriptions. Each identifier appears on a single line (one identifier per line). The terminal identifiers appear first, followed by the nonterminal identifiers followed by the action identifiers. These identifiers are not necessary for parsing, but can be helpful in tracing the activities of a compiler. A parsing state description spans many lines in the ptables file. Each line corresponds to a single entry in a (logical) two-dimensional SLR parsing table, consisting of a state number, followed by a symbol number (an integer version of the human readable terminal and nonterminal symbols - the equivalence is given in the file gramconst.h), followed by a parser action value.

Parser action values are encoded shift/reduce/goto actions. If the parser action is negative, it means reduce. The appropriate production is indicated by the absolute value of the action. If the parser action value is positive, it means shift and goto the state indicated by the value of the action. Only those parser table entries which are non-blank and non-error entries are included in ptables. The entries are sorted in order of increasing state number. Each pro- duction description is given on a single line in the ptables file. These descriptions consist of the left hand side symbol, followed by the size of the right hand side, followed by the semantic action number associated with the production. Gramconst.h contains a series of Pascal constant definitions derived from the grammar. This file contains constant definitions for each of the terminal symbols, followed by definitions for the nonterminal symbols, followed by definitions for the semantic actions symbols, followed by size and range definitions.

Back To Class Calendar