Programming language specification by a grammar with contexts



: Mikhail Barash

: Suna Bensch, Frank Drewes, Rudolf Freund, Friedrich Otto

: 2013

: books@ocg.at

: Fifth Workshop on Non-Classical Models of Automata and Applications (NCMA 2013)

: books@ocg.at

: 51

: 67

: 978-3-85403-294-6


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.



Last updated on 2024-26-11 at 12:16