Skip to content
cgrand edited this page Sep 13, 2010 · 3 revisions

Interface

  • at core, event-driven (SAX-like), 3 types of events:
    • text
    • open tag/rule
    • close tag/rule
  • events are reduced into a DOM tree (default)
  • states, states, states (opaque)
    • creating a parser yields an initial state S_0
    • ’step and ’eof “advance” the state
      (→ S_0 (step “chunk1”) ; S_1
      (step “chunk2”) ; S_2
      (step “chunk3”) ; S_3
      eof) ; S_4
  • ’results extracts the DOM from the current (final?) state
  • (obviously) restartable:
    (→ S_1
    (step “chunk2b”) ; S_2b
    (step “chunk3”) ; S_3b
    eof) ; S_4b
  • resumable: ’reset before each ’step
    (def RS_1 (→ S_0 reset (step “chunk1”)))
    (def RS_2 (→ RS_1 reset (step “chunk2”)))
    (def RS_3 (→ RS_2 reset (step “chunk3”) eof))
    (reduce stitch S_0 [RS_1 RS_2 RS_3]) ; returns S_4. Note that stitch is associative
    • since stitch is associative you can store your “resumable states” in a tree and cache (stitch left-child right-child)
      • when a chunk is altered, you need to recompute its resumable state. If its resumable state is stitchable (see stitchable?) you can safely alter the corresponding leaf in the tree. Thus the new altered DOM is computed in O(log n) stith calls
      • tip: use lines as chunks

Implementation details

  • interpreted, use “continuations”
    • one op is [f & args]
      • no closures because closures are opaque and have no equality
      • the set of possible values for “f” must be finite
    • interpreting an op (interpret-op) yields a seq of [events n cont] where:
      • events: seq of events (text, open, close etc.)
      • n: count of consumed characters, nil when all chars consumed and need more input for the continuation
      • cont: next ops to execute
Clone this wiki locally