Converts a PDA into a lower-level PDA-RISC which is easier to flow analyze
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Type Name Latest commit message Commit time
Failed to load latest commit information.
risc-enhanced
tests
.gitignore
README
compile-pda.rkt
compile-pdarisc.rkt
define-ustruct.rkt
examples.rkt
graph-algo.rkt
infer-pda-types.rkt
macro-glue.rkt
node-graph.rkt
parse-pda.rkt
parse-pdarisc.rkt
pda-data.rkt
pda-parse-post-processing.rkt
pda-syntax-classes.rkt
pda-syntax-literals.rkt
pdarisc-data.rkt
pdarisc-node-graph.rkt
stack-types.rkt
strip-syntax.rkt
symbol-append.rkt
traverse-pdarisc.rkt
uid.rkt
unparse-pda.rkt
unparse-pdarisc.rkt

README

PDA Compiler
====================

macro-glue.rkt provides the pda macro which has the following form:

  (pda token-convert get-token drop-token eos-stream?
       (clauses ...))

token-convert : X -> TokenSymbol
get-token : InputStream -> X
drop-token : InputStream -> InputStream
eos-stream? : InputStream -> Boolean

We can take the output from the DeRemer Penello algorithm and feed it to the pda
macro after minor modifications. First, the DRP algorithm produces unreachable
states and never-used rules. We must remove these because the stack type
inference algorithm will fail if it finds unreachable states. Then, we must
remove the NO-SHIFT and ERROR forms because these are not found in the PDA
grammar used by the pda macro. We must break the lambdas from the semantic
actions into a series of bindings and a body as specified by the rule
syntax. Furthermore, we must add a START form specifying the initial state and
an EOS form specifying the EOS token. Finally, we must convert scheme48/scsh
idioms, such as (if #f #f), to proper Racket code.

The DRP algorithm often produces unreachable states that cause errors in the
stack type inferring algorithm. You'll get hash-ref errors. Remove the
corresponding states. Analogously, you may come across irreducible rules which
will cause errors in the compile-pda step. Remove them as well.

The procedure parameters used in DRP are slightly different than the ones
expected by the pda macro. Instead of token-case, a piece of syntax which
creates a case form, pda asks for token-convert which converts a token from the
stream into a token declared in the TOKENS form. The pda get-token argument
expects only one argument, the stream; the DRP's get-token argument expected
both a stream and a lookahead. Finally, the pda macro neglects an error handler
and adds an empty-stream? procedure, which checks if the stream is empty.

(NO-SHIFT *EOF*) => (EOF *EOF*)