  LR(1) parsing was a focus of extensive research in the past 50 years. Though
most fundamental mysteries have been resolved, a few remain hidden in the dark
corners. The one we bumped into is the minimization of the LR(1) state
machines, which we prove is NP-hard. It is the node-coloring problem that is
reduced to the minimization puzzle. The reduction makes use of two technique:
indirect reduction and incremental construction. Indirect reduction means the
graph to be colored is not reduced to an LR(1) state machine directly. Instead,
it is reduced to a context-free grammar from which an LR(1) state machine is
derived. Furthermore, by considering the nodes in the graph to be colored one
at a time, the context-free grammar is incrementally extended from a template
context-free grammar that is for a two-node graph. The extension is done by
adding new grammar symbols and rules. A minimized LR(1) machine can be used to
recover a minimum coloring of the original graph.
