Deterministic and Bottom-Up Parsing in Prolog

Book One

Volume

Proceedings of the AAAI Conference on Artificial Intelligence, 3

Natural Language

It is well known that top-down backtracking context free parsers are easy to write in Prolog, and that these parsers can be extended to give them the power of ATN’s. This report shows that a number of other familiar parser designs can be very naturally implemented in Prolog. The top-down parsers can easily be constrained to do deterministic parsing of LL(k) languages. Bottom-up backtrack parsers can also be elegantly implemented and similarly constrained to do deterministic LR(k) parsing. Very natural extensions of these LR(k) parser designs suffice for deterministic parsing of natural languages of the sort carried out by the Marcus(1980) parser.