CPL - Chalmers Publication Library
| Utbildning | Forskning | Styrkeområden | Om Chalmers | In English In English Ej inloggad.

Expressivity and Complexity of the Grammatical Framework

Peter Ljunglöf (Institutionen för datavetenskap, Språkteknologi)
Göteborg : Chalmers University of Technology, 2004. ISBN: 91-628-6331-2.- 172 pages s.

This thesis investigates the expressive power and parsing complexity of the Grammatical Framework (GF), a formalism originally designed for displaying formal propositions and proofs in natural language. This is done by relating GF with two more well-known grammar formalisms; Generalized Context-Free Grammar (GCFG), best seen as a framework for describing various grammar formalisms; and Parallel Multiple Context-Free Grammar (PMCFG), an instance of GCFG. Since GF is a fairly new theory, some questions about expressivity and parsing complexity have until now not been answered; and these questions are the main focus of this thesis. The main result is that the important subclass context-free GF is equivalent to PMCFG, which has polynomial parsing complexity, and whose expressive power is fairly well known. Furthermore, we give a number of tabular parsing algorithms for PMCFG with polynomial complexity, by extending existing algorithms for context-free grammars. We suggest three possible extensions of GF/PMCFG, and discuss how the expressive power and parsing complexity are influenced. Finally, we discuss the parsing problem for unrestricted GF grammars, which is undecidable in general. We nevertheless describe a procedure for parsing grammars containing higher-order functions and dependent types.

Nyckelord: Grammatical Framework, generalized context-free grammar, multiple context-free grammar, context-free rewriting systems, type theory, expressive power, abstract syntax, linearization, parsing

Dissertation at the University of Gothenburg

Denna post skapades 2006-09-28. Senast ändrad 2011-11-15.
CPL Pubid: 10794


Läs direkt!

Länk till annan sajt (kan kräva inloggning)

Institutioner (Chalmers)

Institutionen för datavetenskap, Språkteknologi (2002-2004)


Språkteknologi (språkvetenskaplig databehandling)

Chalmers infrastruktur


Datum: 2004-12-07
Tid: 10.00
Lokal: HA2
Opponent: Dr Bernard Lang, INRIA Rocquencourt, France

Ingår i serie

Technical report D - School of Computer Science and Engineering, Chalmers University of Technology 31 D