Implementations ofParsing Algorithms forLinear Multiple Context-Free Grammars Thesis for M.A. in Computational Linguisti s

This thesis is an a ount of implementations of parsing algorithms for Linear Multiple Context-Free Grammars (LMCFG). The algorithms have originally been proposed for Parallel Multiple Context-Free Grammars (PMCFG), a super lass to LMCFG, by Peter Ljunglöf. LMCFG is a Mildly Context-Sensitive Grammar formalism. The implementations are part of the work being arried out for the TALK proje t at the departements of Linguisti s at Göteborg University and Computing S ien e at Chalmers University of Te hnology and Göteborg Univerity. The Language Te hnology Group at Chalmers is urrently ondu ting resear h round the grammar formalism Grammati al Framework (GF). The important sub lass ontext-free GF is equivalent to PMCFG. This implies that a subset of the ontext-free GF grammars an be parsed as equivalent LMCFG grammars. Four dierent algorithms for parsing LMCFG are implemented, using dedu tive agenda-driven hart-parsing. The rst algorithm is a straightforward bottom-up strategy om-bining items with smaller over of the input string to items with larger over. The se ond algorithm uses a ontext-free approximation and then re overs the resulting hart. The third algorithm is an a tive algorithm with Earley and Kilbury predi tion. And the last algorithm is in remental. The algorithms have not been thoroughly tested as part of the work presented here. However, preliminary testing indi ate that they seem faster than the existing parser for GF. Sammanfattning Den här uppsatsen är en redogörelse för implementeringar av parsningsalgoritmer för Linear Multiple Context-Free Grammars (LMCFG). Algoritmerna har från början föreslagits av Peter Ljunglöf för Parallel Multiple Context-Free Grammars (PMCFG), en superklass till LMCFG. LMCFG är en milt kontextkänslig grammatikformalism