Sökning: id:"swepub:oai:gup.ub.gu.se/10794" >
Expressivity and Co...
Expressivity and Complexity of the Grammatical Framework
-
- Ljunglöf, Peter, 1971 (författare)
- Gothenburg University,Göteborgs universitet,Institutionen för data- och informationsteknik (GU),Department of Computer Science and Engineering (GU),Chalmers tekniska högskola,Chalmers University of Technology
-
(creator_code:org_t)
- ISBN 9162863312
- Göteborg : Chalmers University of Technology, 2004
- Engelska.
- Relaterad länk:
-
https://gup.ub.gu.se... (primary) (free)
-
visa fler...
-
https://gup.ub.gu.se...
-
https://research.cha...
-
visa färre...
Abstract
Ämnesord
Stäng
- 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.
Ämnesord
- NATURVETENSKAP -- Data- och informationsvetenskap -- Språkteknologi (hsv//swe)
- NATURAL SCIENCES -- Computer and Information Sciences -- Language Technology (hsv//eng)
Nyckelord
- Grammatical Framework
- generalized context-free grammar
- multiple context-free grammar
- context-free rewriting systems
- type theory
- expressive power
- abstract syntax
- linearization
- parsing
- context-free rewriting systems
Publikations- och innehållstyp
- vet (ämneskategori)
- dok (ämneskategori)
Hitta via bibliotek
Till lärosätets databas