Abstract
Although existing LR(1) or U(1) parser generators suffice for many language recognition problems, writing a straightforward grammar to translate a complicated language, such as C++ or even C, remains a non-trivial task. We have often found that adding translation actions to the grammar is harder than writing the grammar itself. Part of the problem is that many languages are context-sensitive. Simple, natural descriptions of these languages escape current language tool technology because they were not designed to handle semantic information. In this paper, we introduce predicated LR (k) and LL (k) parsers as a solution. Predicates provide a general, practical means to utilize semantic tests in parsers. Used in conjunction with k >1 lookahead sets, a predicated parser simplifies the task of writing real translators. Our approach differs from previous work in that (i) we allow multiple predicates to be placed arbitrarily within a production, (ii) we describe the construction of predicated LR (k) parsing tables, (iii) we automatically hoist predicates in an LL(k) parser from one production to aid in the recognition of another, and (iv) we have implemented predicate handling in a public-domain parser generator that offers k-token lookahead - The Purdue Compiler Construction Tool Set (PCCTS)
Keywords
parser generators, predicate testing, LL (k), LR (k)
Date of this Version
July 1993