4 ms·

Your comment doesn't apply for this particular case, because the submission goes into great detail that the parser in question was written with Ragel, a parser

by niftich 10y ago

Your comment doesn't apply for this particular case, because the submission goes into great detail that the parser in question was written with Ragel, a parser generator. The code written by them in Ragel contained a bug, which lay uncaught and dormant for years, and manifested only when calling/wrapping code was altered.

Blackthorn 10y ago
It still seems like a gross mismatch of power though. Correct me if I'm wrong but Ragel only can output parsers for regular languages, yes? You can't call their Ragel code an HTML parser because Ragel can't output a parser powerful enough to parse HTML.
- nostrademons 10y ago
  HTML isn't a CFG. The HTML spec is setup as a state machine ( = regular language) + a number of side data structures like the stack of open elements and list of active formatting elements. This maps very easily to Ragel, where your actions can easily have side-effects and reference internal state within the language.
  - Blackthorn 10y ago
    > HTML isn't a CFG. The HTML spec is setup as a state machine ( = regular language) + a number of side data structures like the stack of open elements and list of active formatting elements. That's...that's what a context-free grammar is. (FWIW, wild-type html might not be context-free but require a higher powered parser.)
    - nostrademons 10y ago
      Operations on the stack of open elements don't have to follow the same LIFO discipline that a set of recursive productions (i.e. a CFG) would generate. For example, parts of the HTML5 parsing algorithm (eg. the Adoption Agency Algorithm) involve conditionally popping elements off the stack of open elements while they appear in the list of open formatting elements (which is itself a FIFO queue), and then pushing the popped elements back onto the list of open formatting elements. Other parts (eg. tables) involve re-parenting elements into parents that are currently on the stack of open elements. (I've written a fairly well-used conforming HTML5 parser, so I do have some domain knowledge in this area...)
      - Blackthorn 10y ago
        Fair enough...I'll cop to not knowing much about HTML5, my knowledge stopped with HTML4. I went and referenced the parsing rules and they are quite the mess. There's no official grammar for HTML5 that I can find and even if there was, I don't think there's a solid parser generator out there that handles anything more powerful than context-free grammars.

by niftich 10y ago

Blackthorn 10y ago

It still seems like a gross mismatch of power though. Correct me if I'm wrong but Ragel only can output parsers for regular languages, yes? You can't call their Ragel code an HTML parser because Ragel can't output a parser powerful enough to parse HTML.

nostrademons 10y ago
HTML isn't a CFG. The HTML spec is setup as a state machine ( = regular language) + a number of side data structures like the stack of open elements and list of active formatting elements. This maps very easily to Ragel, where your actions can easily have side-effects and reference internal state within the language.
- Blackthorn 10y ago
  > HTML isn't a CFG. The HTML spec is setup as a state machine ( = regular language) + a number of side data structures like the stack of open elements and list of active formatting elements. That's...that's what a context-free grammar is. (FWIW, wild-type html might not be context-free but require a higher powered parser.)
  - nostrademons 10y ago
    Operations on the stack of open elements don't have to follow the same LIFO discipline that a set of recursive productions (i.e. a CFG) would generate. For example, parts of the HTML5 parsing algorithm (eg. the Adoption Agency Algorithm) involve conditionally popping elements off the stack of open elements while they appear in the list of open formatting elements (which is itself a FIFO queue), and then pushing the popped elements back onto the list of open formatting elements. Other parts (eg. tables) involve re-parenting elements into parents that are currently on the stack of open elements. (I've written a fairly well-used conforming HTML5 parser, so I do have some domain knowledge in this area...)
    - Blackthorn 10y ago
      Fair enough...I'll cop to not knowing much about HTML5, my knowledge stopped with HTML4. I went and referenced the parsing rules and they are quite the mess. There's no official grammar for HTML5 that I can find and even if there was, I don't think there's a solid parser generator out there that handles anything more powerful than context-free grammars.