LR parsing for strings with placeholders

• Investigation of parsing methods for strings containing placeholders can be formulated as the preservation of grammar classes. • Strings containing placeholders can be parsed by the standard LR(k) ( k ≥ 1) parser if the grammar for the language without placeholders is LR(k) and each nonterminal derives at least one nonempty string. • The property mentioned above does not holds for LR(0). This paper studies a parsing method for strings containing placeholders, each of which may be later replaced by a string derived from the corresponding nonterminal symbol. Such a method potentially applies to parallel/distributed parsing, parsing for templates, modular syntax definitions, and so on. This paper investigates whether the introduction of the placeholder preserves the class of the grammar and proves the following two facts. First, the class of LR( k )grammars is preserved if k ≥ 1 and every nonterminal derives at least one nonempty string; hence, we can apply the standard LR parsing algorithm for parsing strings with placeholders. Second, the class of LR(0) is not. These results extend the preceding study for the LL(1) grammars.