Where academic tradition
meets the exciting future

You are here: TUCS > PUBLICATIONS > Publication Search > Programming Language Specifica...

Programming Language Specification by a Grammar with Contexts

Mikhail Barash, Programming Language Specification by a Grammar with Contexts. In: Suna Bensch, Frank Drewes, Rudolf Freund, Friedrich Otto (Eds.), Fifth Workshop on Non-Classical Models of Automata and Applications - NCMA 2013, Umeå, Sweden, August 13 - August 14, 2013, Proceedings, books@ocg.at 294, 51–67, Österreichische Computer Gesellschaft, 2013.

Abstract:

In a recent paper (M. Barash, A. Okhotin, "Defining contexts in context-free grammars", LATA 2012) a mathematical definition of contexts within grammar rules has been proposed. The model, called grammars with contexts, extends context-free grammars with operators for referring to the context in which a substring being defined occurs. The expressive power of such grammars is far beyond context-free languages, while a general parsing algorithm for such grammars has cubic time complexity, as in standard context-free case. The present paper investigates an application of the model and makes an attempt to specify a tiny typified programming language solely by means of a grammar. Such inherently non-context-free "context conditions" as declaration of every variable before use and checking the types of formal and actual arguments in function calls are specified by contexts, native to the proposed model.

BibTeX entry:

@INPROCEEDINGS{inpBarash_Mikhail13b,
  title = {Programming Language Specification by a Grammar with Contexts},
  booktitle = {Fifth Workshop on Non-Classical Models of Automata and Applications - NCMA 2013, Umeå, Sweden, August 13 - August 14, 2013, Proceedings},
  author = {Barash, Mikhail},
  volume = {294},
  series = {books@ocg.at},
  editor = {Bensch, Suna and Drewes, Frank and Freund, Rudolf and Otto, Friedrich},
  publisher = {Österreichische Computer Gesellschaft},
  pages = {51–67},
  year = {2013},
  keywords = {conjunctive grammars, grammars with contexts, programming language specification, applications},
}

Belongs to TUCS Research Unit(s): FUNDIM, Fundamentals of Computing and Discrete Mathematics

Edit publication