Skip to content
Parsing

Changelog

  • Implemented linked list and zipper for it
  • Implemented vizaulization using react-archer
  • Implemented narry tree and (Huet’s) zipper for it
  • Implemented vizualization using Graphviz
  • Implemented vizualization for “cycled” tree (cycle detection)
  • Implemented parsing with zippers
  • Extended “parsing with zippers” with:
    • Kleene star (Rep) - tree for it is similar to Seq
      • Didn’t implemented Kleene plus (+) and optional (?), because I was lazy instead use Alt
    • lexical nodes (Lex) - when parsed derivation tree is replaced by single node with matched value
    • ignored nodes (Ign) - when parsed derivation tree is replaced by empty string node
  • Added DSL for grammar
    • Including letrec-like function to handle creation of cycles. OCaml provide this function ability out of the box, for JS I had to do some hacks
  • Extended “parsing with zippers” with tree compaction
    • All nodes except terminals and labeleled non-terminal are removed from parse tree
  • Implemented “grammar grammar” e.g. grammar to parse BNF-like grammar
  • Implemented playground for “parsing with zippers”
    • User can provide grammar and string and use controls to experiment, observe how parsing happens
  • Realized that my Narry-tree and Huet zipper implementation is cumbersome
    • I wanted to make it “by the book” e.g. to show that zipper indeed can be implemented as McBride derivtive and that this exact zipper can be used for parsing (with zipper). It indeed works, but it is very hard to maintain this codebase
    • So I chnaged implementation to LCRS tree and zipper which treats LCRS tree as Narry tree (not as binary tree). It is not by the book, but it is easier for me to handle
  • Added vizualization of Mem for “parsing with zippers”.
    • Not very helpfull to be fair
  • Added different UI improvements, like
    • Ability to select node to show “legend” e.g. details about node: label, value, top, left, right, etc..
    • Ability to highlight nodes when other controls are hovered - to easily identify which node is related to this control
    • Ability to jump to specific derivation cycle. This makes debuging so much easier I whould have done this earlier
    • Animation between cycles
    • Pink arrows where zipper will move next
  • Display compaction (not the same as tree compaction)
    • It removes all duplicate nodes and changes edges to point to de-duped nodes.
      • Node is duplicate if it has the same originalId, start and end and same children (after de-duplication)
    • This is very similar to Shared Packed Parse Forest, except this representation doesn’t have ambiguation-nodes
      • It hints how to implement transformation of the result to SPPF
    • If it is possible to compact final result, it means that memoization doesn’t fully work. It memoizes some nodes, but not all of them
      • Which means that either I messed up implementation
      • Or that it works the same in the original paper
    • The compaction algorithm is a total mess
  • Added lookahed operators
    • Similar operators exist in PEG and Regular Expressions: & - positive, ! - negative
    • Current algorithm is a mess. Idea is:
      • to mark each zipper with id
      • if there is lookahead operator it produces two independent zippers - one for lookahed and one for main derivation. Connection between them is stored through ids
      • Derivation of zippers continues independently, but if lookahead matched or unmatched, it will preserve or remove main zippers
    • Lookahed with cycle doesn’t work so far

Next

  • Add tests and fix bugs
  • I still a bit fuzzy on how exactly Mem works. I get general idea, but when I tried to implement PwZ without memoization table I got confused. So probably it makes sense to continue improving vizaulization for Mem
    • As soon as I will understand it better I can implement PwZ without memoization table
  • I wonder if it is possible to modify PwZ to produce SPPF instead of list of trees
    • Potentially connected to multiple focus zippers
  • Better error message should take in account Ign and Lex