stereobooster/derp

Parsing with derivatives

Moved to https://parsing.stereobooster.com/

Parsing with derivatives

Innovation

• Parsing with derivatives can easily support Conjunctive grammar, which can parse not context-free grammar, for example $\set{a^nb^nc^n \mid n \geq 0}$. This is not something innovative per se, but I haven't seen it mentioned anywhere in reviewed publications.
• Parsing with derivatives can support Conjunctive grammar with right context, if we add recursion to REwLA
• I showed how to express PEG in terms of REwLA with recursion. Which allows to define derivative formula for PEG.
  • This allows to create variation of PEG with unordered choice. Related work:
    • Parsing Expression Grammars with Unordered Choices
  • By the nature of parsing with derivatives it doesn't have issues with left recursion. Related works:
    • Left recursion in Parsing Expression Grammars
    • Packrat Parsers Can Support Left Recursion
    • Direct Left-Recursive Parsing Expression Grammars
    • More about left recursion in PEG
  • It can open door to understand expressive power of PEG (it is not contained within context-free, but also can express some context-sensitive languages)