3 ms·

That's gotta just be a flaw in the implementation, if the title of the issue ("Exponential parsing") is accurate. Any PEG can be parsed in linear time and spac

• BruceIV 12y ago
  TL;DR Packrat trades guaranteed linear memory usage for worst-case polynomial time; the worst-case almost never comes up in non-contrived input, so it's a reasonable implementation decision to go with the less memory-hungry naive implementation. Depends on the algorithm; the naive recursive algorithm takes worst-case exponential time, while the packrat algorithm guarantees linear time. However, for most sensible[1] inputs, the recursive algorithm runs in linear time and constant space, while packrat takes about the same time, but with linear space usage. [1] Where "sensible" is defined to be "amount of backtracking is bounded by a fixed small constant, as is grammar nesting depth" - conditions that hold for most human-generated files matching useful grammars (I've been working on a new PEG parsing algorithm; it doesn't work so well, but the results I've been getting in testing about the existing algorithms are quite interesting.)
• maxerickson 12y ago
  I don't know much of these things. I was thinking more that maybe some aspect of markdown was not easily expressed using a PEG (it's the same implementer behind both the parser in Pandoc and this project) .
  • phpnode 12y ago
    Keeping track of indent levels is not easy with PEGs but can be dealt with by pre processing
    • kaoD 12y ago
      I might've missed something. Where do indent levels come into play? AFAICT Markdown has no concept of indentation.
      • BruceIV 12y ago
        IIRC, lists and code blocks depend on indentation to decide where they begin/end, and I think what level they're at.
        • kaoD 12y ago
          I think code blocks don't track indentation. A code block is just a bunch of lines beginning with 4 spaces (or blank lines) and the rest (when >4 spaces) are treated as leading spaces. I think you're right about lists though.