Campus Event Calendar

Event Entry

New for: D3

What and Who

Syntactic analysis of ambiguous natural language constructions with Tomita shift-resolve parser

Alexander Kobzar
Kharkiv National University of Radioelectronics
PhD Application Talk
AG 1, AG 3, AG 4, AG 5, SWS, RG1, MMCI  
Public Audience

Date, Time and Location

Tuesday, 16 February 2010
120 Minutes
E1 4


Most context-free (CF) grammar parsing algorithms developed up to

now are inapplicable to natural language (NL) parsing due to its narrow
coverage of CF-grammars describing NL syntax or unpractical time
complexity. In this presentation we consider the design of such an algorithm
directed by Russian language as well as a scheme of formalization of
Russian constructions. The algorithm is based on a combination of shiftresolve
parsing and Tomita parser, and its design is divided into two phases:

1. Design of a deterministic algorithm. NL constructions and its formal
representations by recursive and epsilon-grammars that make most parsing
algorithms unable to process them are considered. An improvement of shiftresolve
parsing algorithm is carried out with respect to the ambiguity.

2. Design of a nondeterministic algorithm. Properties of shift-resolve parsing
which are different to LR-parsing and formal conditions of applying of
Tomita parser to shift-resolve parsing are considered. Designed parser is
capable to carry out parsing with better accuracy and time complexity
compared to LR-parsing implementation. Next, we consider formalization of
Russian word combinations and simple sentences by attribute CF-grammar.
Designed scheme and grammar make it possible to formalize these
constructions completely. Next, we consider a developed NL parser that
implement designed algorithm and make it possible to design NL grammars.
Finally, we consider some open problems, namely grammar classes that are
remain unhandled for the algorithm.


IMPRS-CS Office Team
0681 93 25 225
--email hidden
passcode not visible
logged in users only

Tags, Category, Keywords and additional notes

Stephanie Jörg, 02/12/2010 10:39 -- Created document.