Where academic tradition
meets the exciting future

You are here: TUCS > PUBLICATIONS > Publication Search > Defining Contexts in Context-F...

Defining Contexts in Context-Free Grammars

Mikhail Barash, Defining Contexts in Context-Free Grammars. TUCS Dissertations 204. University of Turku, 2015.

Abstract:

This thesis introduces an extension of Chomsky’s context-free grammars equipped with operators for referring to left and right contexts of strings.The new model is called grammar with contexts.

The semantics of these grammars are given in two equivalent ways — by language equations and by logical deduction, where a grammar is understood as a logic for the recursive definition of syntax. The motivation for grammars with contexts comes from an extensive example that completely defines the syntax and static semantics of a simple typed programming language.

Grammars with contexts maintain most important practical properties of context-free grammars, including a variant of the Chomsky normal form. For grammars with one-sided contexts (that is, either left or right), there is a cubic-time tabular parsing algorithm, applicable to an arbitrary grammar. The time complexity of this algorithm can be improved to quadratic,provided that the grammar is unambiguous, that is, it only allows one parsefor every string it defines. A tabular parsing algorithm for grammars withtwo-sided contexts has fourth power time complexity. For these grammarsthere is a recognition algorithm that uses a linear amount of space.

For certain subclasses of grammars with contexts there are low-degree polynomial parsing algorithms. One of them is an extension of the classical recursive descent for context-free grammars; the version for grammars with contexts still works in linear time like its prototype. Another algorithm, with time complexity varying from linear to cubic depending on the particular grammar, adapts deterministic LR parsing to the new model.

If all context operators in a grammar define regular languages, then such a grammar can be transformed to an equivalent grammar without context operators at all. This allows one to represent the syntax of languages in a more succinct way by utilizing context specifications. Linear grammars with contexts turned out to be non-trivial already over a one-letter alphabet. This fact leads to some undecidability results for this family of grammars

***

Kontekstien antaminen kontekstittomille kieliopeille

Tässä väitöskirjassa esitellään Chomskyn kontekstittomien kielioppien laajennus, jossa on vasemmille ja oikeille konteksteille viittaavia operaattoreita.Uutta kielioppiperhettä kutsutaan konteksteilla varustetuiksi kieliopeiksi.Näiden kielioppien semantiikka määritellään kahdella ekvivalentillatavalla — kieliyhtälöin sekä loogisin päättelyin, jossa kielioppi katsotaansyntaksin rekursiivisen määritelmän logiikaksi. Konteksteilla varustettujen kielioppien motivaationa on laaja esimerkki, jossa yksinkertaisen ohjelmointikielen syntaksi ja staattinen semantiikka määritellään täysin.

Konteksteilla varustetut kieliopit omaavat monia kontekstittomienkielioppien käytännön ominaisuuksia, kuten Chomskyn normaalimuodonvariaation. Yksipuolisilla konteksteilla varustetut kieliopit (toisin sanoenkontekstit ovat joko vasemmanpuoleisia tai oikeanpuoleisia) voidaan jäsentää taulukkointiin perustuvalla jäsennysalgoritmilla, jonka aikakompleksisuus on kuutiollinen, ja joka on sovellettavissa mielivaltaisten kielioppien analyysiin. Tämän algoritmin aikakompleksisuus paranee neliölliseksi, mikäli kielioppi on yksiselitteinen, toisin sanoen, jos jokainen kieliopin määrittelemä merkkijono on jäsennettävissä vain yhdellä tavalla. Kaksipuolisilla konteksteilla varustettujen kielioppien jäsennysalgoritmilla on neljännen potenssin aikakompleksisuus. Kaikki nämä kielioppiperheet voidaan tunnistaa käyttäen lineaarista määrää tiloja.

Konteksteilla varustettujen kielioppien tietyt alaperheet voidaan jäsentää algoritmeilla, jotka toimivat alhaista astetta olevassa polynomiajassa. Yksi näistä algoritmeista on klassisen rekursiivisen laskeutumisen laajennus, joka toimii lineaarisessa ajassa, kuten alkuperäinen algoritmikin. Toinen algoritmi, jonka aikakompleksisuus vaihtelee lineaarisesta kuutiolliseen kieliopista riippuen, mukauttaa deterministisen LR-jäsennysalgoritmin uudelle kielioppiperheelle.

Mikäli jokainen konteksteilla varustetun kieliopin kontekstioperaattori määrittelee säännöllisen kielen, voidaan kyseinen kielioppi muuttaa ekvivalentiksi kontekstittomaksi kieliopiksi. Tämän avulla voidaan määritellä kielten syntaksi ytimekkäämmin hyödyntämällä kontekstioperaattorien ilmaisuvoimaa.

BibTeX entry:

@PHDTHESIS{phdBarash_Mikhail15a,
  title = {Defining Contexts in Context-Free Grammars},
  author = {Barash, Mikhail},
  number = {204},
  series = {TUCS Dissertations},
  school = {University of Turku},
  year = {2015},
  ISBN = {978-952-12-3260-2},
  ISSN = {1239-1883},
}

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

Edit publication