Semantic predicates in parser generators

Parser-based pattern matching proves to be attractive to compiler implementors because of its use in compiler-compilers. Semantic predicates can be added to parsers to augment the decision making power provided by syntactic analysis. This paper presents a practical technique to incorporate them within the framework of existing parser generators. A nearly vanilla parser can be used in this manner provided that epsilon productions are added to the grammar. Reduction by epsilon productions triggers the predicates, which as a side effect modify the lookahead symbol(s), thus influencing the progress of the parser at the last possible minute.