# Computer Science Colloquium

Im Rahmen des Informatik-Kolloquiums, das von den Instituten des Fachbereichs Informatik, der Österreichischen Gesellschaft für Informatik (ÖGI), der Arbeitsgemeinschaft für Datenverarbeitung (ADV) sowie der Österreichischen Computergesellschaft (OCG) abgehalten wird, spricht## Dr. Mikhail Barash

### Center of Computer Science, University of Turku (Finland)

über das Thema:## On a New Model to Specify Programming Languages

Zeit: 2015-11-13 13:00:00.0, 120 MinutenOrt: S3-218 im Science Park 3

#### Zusammenfassung

Context-free grammars have been a model for defining syntax of various kinds of languages since the early days of Computer Science and they found their foremost application in specifying programming languages. However, their expressive power turned out to be insufficient to express many useful constructs, such as cross-reference, which reduces their applicability.The present work attempts to implement N. Chomsky's idea (1959) of a phrase-structure rule applicable in a context and introduces an extension of context-free grammars equipped with operators for referring to left and right contexts of the substring being defined. In this model, a rule, for example, "A -> a & <B & >C" defines a symbol "a", as long as it is preceded by a string defined by "B" and followed by a string defined by "C". The conjunction operator in this example is taken from conjunctive grammars (A. Okhotin, Conjunctive grammars, J. Autom., Lang. Comb., 2001), which are an extension of ordinary context-free grammars that maintains most of their practical properties, including many parsing algorithms.

The present work gives two equivalent definitions of the new model of grammars with contexts: by logical deduction and by language equations, and establishes some basic properties of the model, including a cubic-time general parsing algorithm; this time can be improved to linear for LL and LR subclasses of grammars. A variety of examples of grammars with contexts is constructed, with the most extensive example completely specifying the syntax of a simple typed programming language.