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

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.