Comment by graphviz | Hacker News Reader

Comment by graphviz | Hacker News Reader

The difficulty of implementing parsers (for the majority of programmers or engineers) is one of the tragedies of computer science. It is a very well developed theory and apparently it is too hard to deliver in a usable form without becoming one of those "to bake an apple pie you need to invent the universe" experiences. I just wanted a pie! Like the html-ish parser in Graphviz:

  bison -y -Wno-yacc -dv ../../lib/common/htmlparse.y -o htmlparse.c
  ../../lib/common/htmlparse.y: warning: 2 shift/reduce conflicts [-Wconflicts-sr]
  ../../lib/common/htmlparse.y: note: rerun with option '-Wcounterexamples' to generate conflict counterexamples

Noted.

This partially explains the success of languages like XML, JSON and YAML as alternatives to writing your own parser.

The trick for “lets hand write a parser, it is simple” is in coming up with grammar that is either LL(1) or slight superset of that that can still be parsed by recursive descent with hand rolled deconflicting rules (prime example of that is if-else in C). The issue with that is you cannot just take an arbitrary context-free grammar with attached semantics and mechanically transform it into LL(1) form, because while doing that you are moving production rules around and thus you lose any kind of semantics that were originally attached to them. This is the reason why the parser generators tend to be (LA)LR, you can produce such parser for wide (albeit in practice ill-defined) subset of context-free grammars purely mechanically without having to change the meaning of the attached semantic rules (typically represented as a bunch of copied code).

Reply on news.ycombinator.com