The simple and powerful yfx operator precedence parser
Dynamic operator declarations were introduced in the first Prolog system in the early 1970s. Today several other logical and functional languages adopt the Prolog style of dynamic operators. Despite this widespread use, there are no guidelines to assist the development of dynamic operator parsers. This paper presents an in-depth study of the built-in classical dynamic operator parser in Prolog systems. It is a powerful operator precedence parser covering pre/in/postfix operators; it is table-driven, allowing operators to be redefined at run-time; it is encoded in a simple, small and fast code; and, finally, it is widely used as a standard parser by the logic programming community. In a stepwise refinement approach (from specification to implementation and evaluation), this paper presents a detailed analysis of this parser. As an additional contribution, it is also shown how to encode the parser as a plug-in component in procedural languages. (C) 2007 John Wiley & Sons, Ltd.
operator precedence dynamic operator prolog parser attribute grammar