Parsing

 

Parsing is the process of assigning structure to sentences. The structure is obtained from the grammatical description of the language. Both in computer science and in computational linguistics, context-free grammars and associated parsing algorithms are among the most useful tools. The notations in this section are close to [Sikkel,Nijhold,1997].

Parsing can be viewed as a deductive process, see [Pereira,Warren,1983]. That is, the algorithm operates by means of least fixed-point iteration: a table is gradually filled with elements derived from other elements, until no new ones can be found. A certain collection of deduction steps indicate how table elements are to be derived from others.

Section one introduces parsing as deduction for context-free grammars. The Earley, CYK, and Bottom-up parsing schemata are presented. In section two, these parsing schemata are generalized for RMS. In section three parsing schemata of restricted RMS are analyzed. In the last section, upper time bounds for these new algorithms are given, as well as the proof of correctness.

• Parsing of Context-Free Languages
  • Introductory Example
  • Parsing System and Parsing Schema
  • Correctness of Parsing Schemata
• Parsing of Recursive Matrix Systems
  • CYK Parsing Schemata
  • Bottom-up Parsing Schemata
  • Earley Parsing Schemata
  • Parsing Schemata in Vector Notation
• Parsing of Restricted Grammars
  • Parsing of Regular and Linear Grammars
  • Parsing of Restricted RMS
• Time Complexity