zbMATH — the first resource for mathematics

Semantic routines and \(LR(k)\) parsers. (English) Zbl 0424.68052
Summary: Most applications of parsing require that the parser call semantic action routines while processing the input. For \(LR(k)\) parsers it is well known that a semantic action routine can be called when the end of a production is recognized. Often, however, it is desirable to call routines at other times. This paper presents fast algorithms that determine, for an \(LR(k)\) (or \(SLR(k)\)) grammar, which positions are suitable for calling routines. The algorithms are practical for use with \(LR(1)\) (\(SLR(1)\)) parser building programs, because the worst case running time is dominated by the time required to build the \(LR(1)\) (\(SLR(1)\)) parser. Applications of the algorithms to attribute grammars and automatic indentation are discussed.

68N20 Theory of compilers and interpreters
Full Text: DOI