Navin Budhiraja


pdf bib
Parsing Generalized Phrase Structure Grammar with Dynamic Expansion
Navin Budhiraja | Subrata Mitra | Harish Karnick | Rajeev Sangal
Proceedings of the First International Workshop on Parsing Technologies

A parser is described here based on the Cocke-Young-Kassami algorithm which uses immediate dominance and linear precedence rules together with various feature inheritance conventions. The meta rules in the grammar are not applied beforehand but only when needed. This ensures that the rule set is kept to a minimum. At the same time, determining what rule to expand by applying which meta-rule is done in an efficient manner using the meta-rule reference table. Since this table is generated during “compilation” stage, its generation does not add to parsing time.