llk

LLk refers to a family of context-free grammars that can be parsed by a top-down, predictive parser using up to k tokens of lookahead. The letters LL stand for left-to-right scanning of the input and a leftmost derivation of the sentence, while the subscript k indicates how many input tokens are consulted to decide which production to apply. LLk grammars are the target of predictive parsing strategies, where decisions are made without backtracking.

A typical LLk parser maintains a stack of grammar symbols and reads input from left to right. When a nonterminal on the stack must be expanded, the parser examines the next up to k input tokens to select an appropriate production. This decision process is usually realized through a parsing table that encodes which productions to use for combinations of nonterminals and lookahead strings. If no valid production exists for the current lookahead, the grammar is not LLk and parsing fails.

LLk grammars are not universal for all context-free languages. Many languages are not LLk for any finite k and require more powerful parsing approaches, such as LR parsing. In practice, language designers often aim for LL(1) grammars, where a single lookahead token suffices to make decisions, because they are easier to implement with fast, predictable parsers. Increasing k expands the class of languages that are LLk, but at the cost of larger parse tables and more complex lookahead handling. LLk concepts influence compiler design, formal language theory, and the development of parsing tools, providing a framework for understanding when a top-down, predictive parser can be effectively applied.