Premium
Lazy recursive descent parsing for modular language implementation
Author(s) -
Koskimies Kai
Publication year - 1990
Publication title -
software: practice and experience
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.437
H-Index - 70
eISSN - 1097-024X
pISSN - 0038-0644
DOI - 10.1002/spe.4380200802
Subject(s) - parsing , computer science , parser combinator , programming language , top down parsing , bottom up parsing , modular design , modular programming , top down parsing language , artificial intelligence , descent (aeronautics) , parsing expression grammar , reuse , natural language processing , context free grammar , l attributed grammar , ecology , engineering , biology , aerospace engineering
A variant of the well‐known recursive descent parsing technique is developed, based on the assumption that each non‐terminal of the language is implemented through a separate module. The modularization principle requires that the recursive descent parser of one non‐terminal must be written knowing only the production rules of that non‐terminal, and not the other parts of the language. This leads to a parsing technique which is ‘lazy’ in the sense that part of the parser is constructed during parsing, according to the needs of a particular input text. It turns out that this technique can be implemented as efficiently as conventional recursive descent parsing, which is one of the fastest known parsing methods. The main benefit of the technique is that it allows a language to be implemented in small pieces which are easy to modify, replace, and reuse.