A4 Refereed article in a conference publication
Programming language specification by a grammar with contexts
Authors: Mikhail Barash
Editors: Suna Bensch, Frank Drewes, Rudolf Freund, Friedrich Otto
Publication year: 2013
Journal: books@ocg.at
Book title : Fifth Workshop on Non-Classical Models of Automata and Applications (NCMA 2013)
Series title: books@ocg.at
First page : 51
Last page: 67
ISBN: 978-3-85403-294-6
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.
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.
UTU Research Portal