Two iteration theorems for the LL(k) languages

DOI10.1016/0304-3975(80)90029-8zbMath0452.68084OpenAlexW1968765705MaRDI QIDQ1148695

John C. Beatty

Publication date: 1980

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(80)90029-8

zbMATH Keywords

derivation treesdangling-ELSELL(k) grammarLR(k) languages

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Theory of compilers and interpreters (68N20)

Related Items

A pumping lemma for real-time deterministic context-free languages, The interchange or pump (di)lemmas for context-free languages, A pumping lemma for deterministic context-free languages, Iteration theorems for families of strict deterministic languages, Two iteration theorems for the LL(k) languages, Rediscovering pushdown machines, On the relationship between the LL(k) and LR(k) grammars, On satisfying the LL-iteration theorem, Ll-regular grammars, On LC(0) grammars and languages, A metatheorem for undecidable properties of formal languages and its application to LRR and LLR grammars and languages

Uses Software

• ALGOL 60

Cites Work

• Unnamed Item
• Unnamed Item
• Revised report on the algorithmic language ALGOL 60
• Iteration theorems for families of strict deterministic languages
• Two iteration theorems for the LL(k) languages
• Two iteration theorems for some families of languages
• A strong pumping lemma for context-free languages
• On LR(k) grammars and languages
• Characteristic parsing: A framework for producing compact deterministic parsers. II
• A left part theorem for grammatical trees
• Pascal. User manual and report
• A necessary and sufficient condition for a power language to be LL(k)
• On the Parsing of Deterministic Languages
• Deterministic parsing of ambiguous grammars
• Intercalation theorems for stack languages
• Syntax-Directed Transduction
• A helpful result for proving inherent ambiguity
• Properties of deterministic top-down grammars