And backtracking is so useful when doing parsing in general. For an NLP class I did we made a shift-reduce parser with dotted items for an assignment, and my liberally commented Prolog source weighs in a 33 lines of code. My friend's Lisp code which only found one parse (but did make parse trees, to be fair), was several hundred lines if memory serves.
The corollary to Greenspun's tenth rule in action, I guess. =)
Comments
And backtracking is so useful when doing parsing in general. For an NLP class I did we made a shift-reduce parser with dotted items for an assignment, and my liberally commented Prolog source weighs in a 33 lines of code. My friend's Lisp code which only found one parse (but did make parse trees, to be fair), was several hundred lines if memory serves.
The corollary to Greenspun's tenth rule in action, I guess. =)
Yep. I taught a Prolog NLP course and among the parsers covered was a shift-reduce parser, which would fit on one slide without much trouble.
Same thing for chart parsing in Prolog. When you get backtracking and unification for free, implementing a parser is simple ;).