This thesis presents an extension of packrat parsing for grammars
which require the notion of state while parsing.  Packrat parsing is a
parsing algorithm that has the power and flexibility of top-down
parsing with unlimited lookahead and backtracking, and nevertheless
guarantees linear parsing time.  However, it cannot be applied
directly to grammars with state because the algorithm is based
essentially on memoization of intermediate results.  Yet, the notion
of state is often useful for briefly describing a grammar.  In fact,
parsing of some practical languages such as C _requires_ state (the
set of type names in scope, for example).  To resolve this dilemma, we
propose two approaches for handling state in packrat parsing.  One is
to memoize pairs of a result and state; the other is to invalidate
memoized results when the state is changed.  We evaluate these
approaches with the grammar and programs of C as a test case.