Projects

SSGI (Small Step Grammar Interpreter)

SSGI is a parser implemented as a small step interpreter. It borrows heavily from the design of the well-known CESK machine.

• Demo

Definition

The state space Σ of the machine is defined as

ς ∈ Σ =

Grammar × Buffer × Point × Control × Token* × Continuation

A grammar is a function which maps non-terminal symbols N to metalinguistic expressions M.

Grammar =

N → M

m ∈ M ::=

  (!= m)
| (* m)
| (+ m)
| (== m)
| (? m)
| (_ m)
| (| m ...)
| (m ...)
| t where t ∈ S*
| n where n ∈ N

A buffer b is the string being read by the parser.

Buffer =

b ∈ S*

A point p is a natural number ℕ and represents a position in the buffer.

A control is the current metalinguistic expression being evaluated.

c ∈ Control ::=

  okay
| fail
| m

where {fail, okay} ∉ M.

A token τ is a triple of a non-terminal symbol n, a start point p₁, and an end point p₂.

τ ∈ Token where τ = (n × p₁ × p₂).

A continuation κ is the parser program stack.

κ ∈ Continuation ::=

  (choice (c ...) p (τ ...) (τ ...) κ)
| (confirm p (τ ...) κ)
| (drop (τ ...) κ)
| (negate p (τ ...) κ)
| (resume (τ ...) κ)
| (sequence (c ...) κ)
| (token n p κ)

Transition

The transition function ς ⇀ ς′ is defined as.