Abstract
Original language  Undefined 

Awarding Institution 

Supervisors/Advisors 

Date of Award  17 Dec 1993 
Place of Publication  Enschede 
Publisher  
Print ISBNs  9090066888 
State  Published  17 Dec 1993 
Fingerprint
Keywords
 METIS118389
 EWI10844
 IR64273
Cite this
}
Parsing Schemata. / Sikkel, Nicolaas.
Enschede : Universiteit Twente, 1993. 412 p.Research output: Scientific › PhD Thesis  Research UT, graduation UT
TY  THES
T1  Parsing Schemata
AU  Sikkel,Nicolaas
PY  1993/12/17
Y1  1993/12/17
N2  Parsing schemata provide a general framework for specication, analysis and comparison of (sequential and/or parallel) parsing algorithms. A grammar specifies implicitly what the valid parses of a sentence are; a parsing algorithm specifies explicitly how to compute these. Parsing schemata form a welldefined level of abstraction in between grammars and parsing algorithms. A parsing schema specifies the types of intermediate results that can be computed by a parser, and the rules that allow to expand a given set of such results with new results. A parsing schema does not specify the data structures, control structures, and (in case of parallel processing) communication structures that are to be used by a parser. Part I, Exposition, gives a general introduction to the ideas that are worked out in the following parts. Part II, Foundation, unfolds a mathematical theory of parsing schemata. Different kinds of relations between parsing schemata are formally introduced and illustrated with examples drawn from the parsing literature. Part III, Application, discusses a series of applications of parsing schemata.  Feature percolation in unification grammar parsing can be described in an elegant, legible notation.  Because of the absence of algorithmic detail, parsing schemata can be used to get a formal grip on highly complicated algorithms. We give substance to this claim by means of a thorough analysis of LeftCorner and HeadCorner chart parsing.  As an example of structural similarity of parsers, despite differences in form and appearance, we show that the underlying parsing schemata of Earley's algorithm and Tomita's algorithm are virtually identical. Using this structural correspondence we can obtain a novel parallel parser by crossfertilizing a parallel Earley parser with Tomita's graphstructured stack.  Parsing schemata can be implemented straightforwardly by boolean circuits. This means that, in principle, parsing schemata can be coded directly into hardware. Part IV, Perspective, discusses the prospects for natural language parsing applications and draws some conclusions. An important observation is that the theoretical and practical part of the book reinforce each other. The proposed framework is abstract enough to allow a thorough mathematical treatment and practical enough to allow rewriting a variety of real parsing algorithms (i.e. seriously proposed in the literature, not toy examples) in a clear and coherent way.
AB  Parsing schemata provide a general framework for specication, analysis and comparison of (sequential and/or parallel) parsing algorithms. A grammar specifies implicitly what the valid parses of a sentence are; a parsing algorithm specifies explicitly how to compute these. Parsing schemata form a welldefined level of abstraction in between grammars and parsing algorithms. A parsing schema specifies the types of intermediate results that can be computed by a parser, and the rules that allow to expand a given set of such results with new results. A parsing schema does not specify the data structures, control structures, and (in case of parallel processing) communication structures that are to be used by a parser. Part I, Exposition, gives a general introduction to the ideas that are worked out in the following parts. Part II, Foundation, unfolds a mathematical theory of parsing schemata. Different kinds of relations between parsing schemata are formally introduced and illustrated with examples drawn from the parsing literature. Part III, Application, discusses a series of applications of parsing schemata.  Feature percolation in unification grammar parsing can be described in an elegant, legible notation.  Because of the absence of algorithmic detail, parsing schemata can be used to get a formal grip on highly complicated algorithms. We give substance to this claim by means of a thorough analysis of LeftCorner and HeadCorner chart parsing.  As an example of structural similarity of parsers, despite differences in form and appearance, we show that the underlying parsing schemata of Earley's algorithm and Tomita's algorithm are virtually identical. Using this structural correspondence we can obtain a novel parallel parser by crossfertilizing a parallel Earley parser with Tomita's graphstructured stack.  Parsing schemata can be implemented straightforwardly by boolean circuits. This means that, in principle, parsing schemata can be coded directly into hardware. Part IV, Perspective, discusses the prospects for natural language parsing applications and draws some conclusions. An important observation is that the theoretical and practical part of the book reinforce each other. The proposed framework is abstract enough to allow a thorough mathematical treatment and practical enough to allow rewriting a variety of real parsing algorithms (i.e. seriously proposed in the literature, not toy examples) in a clear and coherent way.
KW  METIS118389
KW  EWI10844
KW  IR64273
M3  PhD Thesis  Research UT, graduation UT
SN  9090066888
PB  Universiteit Twente
ER 