Reference. Indexed grammars—an extension of context-free grammars

Alfred V. Aho · · parsing · DOI
A new type of grammar for generating formal languages, called an indexed grammar, is presented. An indexed grammar is an extension of a context-free grammar, and the class of languages generated by indexed grammars has closure properties and decidability results similar to those for context-free languages. The class of languages generated by indexed grammars properly includes all context-free languages and is a proper subset of the class of context-sensitive languages. Several subclasses of indexed grammars generate interesting classes of languages.

Cite

Cite as @AhoIndexed (helia, typst) · \cite{AhoIndexed} (LaTeX)
BibTeX
bibtex · 18 lines
@article{AhoIndexed,
 title = {Indexed Grammars—An Extension of Context-Free Grammars},
 author = {Aho, Alfred V.},
 year = {1968},
 doi = {10.1145/321479.321488},
 url = {https://doi.org/10.1145/321479.321488},
 journal = {J. ACM},
 volume = {15},
 number = {4},
 pages = {647–671},
 publisher = {Association for Computing Machinery},
 address = {New York, NY, USA},
 numpages = {25},
 month = {oct},
 abstract = {A new type of grammar for generating formal languages, called an indexed grammar, is presented. An indexed grammar is an extension of a context-free grammar, and the class of languages generated by indexed grammars has closure properties and decidability results similar to those for context-free languages. The class of languages generated by indexed grammars properly includes all context-free languages and is a proper subset of the class of context-sensitive languages. Several subclasses of indexed grammars generate interesting classes of languages.},
 issn = {0004-5411},
 issue_date = {Oct. 1968}
}
hayagriva YAML (typst)
yaml · 19 lines
AhoIndexed:
  type: article
  title: Indexed Grammars—An Extension of Context-Free Grammars
  author: Aho, Alfred V.
  date: 1968-10
  page-range: 647-671
  url: https://doi.org/10.1145/321479.321488
  serial-number:
    doi: 10.1145/321479.321488
    issn: 0004-5411
  abstract: A new type of grammar for generating formal languages, called an indexed grammar, is presented. An indexed grammar is an extension of a context-free grammar, and the class of languages generated by indexed grammars has closure properties and decidability results similar to those for context-free languages. The class of languages generated by indexed grammars properly includes all context-free languages and is a proper subset of the class of context-sensitive languages. Several subclasses of indexed grammars generate interesting classes of languages.
  parent:
    type: periodical
    title: J. ACM
    publisher:
      name: Association for Computing Machinery
      location: New York, NY, USA
    issue: 4
    volume: 15
Cites 14 works (1 here)
With notes (1)

Formal properties of grammars chom1963

Web
AhoIndexed reference entries/refs/AhoIndexed/AhoIndexed.hel