home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
ftp.ee.pdx.edu
/
2014.02.ftp.ee.pdx.edu.tar
/
ftp.ee.pdx.edu
/
pub
/
users
/
Harry
/
compilers
/
yapp
/
readme
< prev
next >
Wrap
Text File
|
2003-05-23
|
3KB
|
94 lines
YAPP - Yet Another PCAT Parser
==============================
by Harry Porter (October, 1998)
This directory contains an SLR parser generator written in the PCAT language.
This program takes, as input, a context-free grammar (the "grammar") and a
sample input string (called the "example"). From the grammar, it builds
parsing LR parsing tables using the "SLR" algorithm. Then it attempts
to find a parsing of the sample input example string.
-----
There is also a tst directory containing several sample "grammar"s and
"example"s.
grammar1: A syntax for expressions using + * ( ) id
example1: A small expression
grammar2: A syntax for expressions using AND OR NOT ( ) true false
example2: A small boolean expression
grammar3: A small ambiguous (therefore, non-LR) grammar
example3: An example string from this language
grammarPCAT: A grammar for PCAT
examplePCAT1: A small PCAT program
examplePCAT2: A small PCAT program (The quicksort program)
-----
To run the YAPP program type something like one of these commands:
go grammar1 example1
go grammar2 example2
go grammar3 example3
go grammarPCAT examplePCAT1
go grammarPCAT examplePCAT2
You should see a trace of the table building process, followed by an
attempt to parse the given input.
In particular, you should see the following:
1. The grammar rules as they are read in.
2. A list of the terminals and the non-terminals in the grammar.
3. A repeat of the grammar, augmented with a dummy start rule.
4. The FIRST and FOLLOW sets.
5. A trace of the SLR table building process.
6. A list of all the sets of items (i.e., the canonical collection
of LR(0) items).
7. A formatted display of the table. (This will only look good
for very small grammars, since it will be truncated.)
8. A parse of the sample "prog" input string using the table,
with a trace of which actions were taken. This should end
by saying either "parse succeeded" or "parse failed".
In the case of grammar3, you will see error messages during table
construction as the shift-reduce and reduce-reduce conflicts are
detected.
In the case of grammarPCAT, the trace of the table building is fairly long
and the table is fairly large. The trace of the parse is also long, but
should succeed.
The following files are included in this directory:
tst
A directory containing the test grammars and examples, as described
above.
go
A script to run the YAPP program, discussed above.
pre.c
A program to pre-process the grammar and the input string. PCAT programs
cannot read character data; only integers and reals, so the input is
preprocessed to turn all tokens into integers before being sent to
the main PCAT program.
lexer.h, lexer.c
Routines used by pre.c to tokenize the input grammar and the input string.
Lexer.c may not be present since it is assigned as a programming
project in CS-301.
post.c
PCAT programs have limited capability to output newlines, so the
YAPP program writes a "$" instead of newline. This program translates
all "$"s into newlines.
yapp.pcat
The SLR parser generator and the LR parsing algorithm. 2109 lines of
PCAT code.
pcat
An executable version of the PCAT-to-SPARC compiler (C Version).
pc
A shell script to run the PCAT compiler and follow it with the assembly
stage, producing a ".o" file.
makefile
A Makefile to compile the programs: pre.c, yapp.pcat, and post.c.