Premium
A compiler for parsing schemata
Author(s) -
GómezRodríguez C.,
Vilares J.,
Alonso M. A.
Publication year - 2008
Publication title -
software: practice and experience
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.437
H-Index - 70
eISSN - 1097-024X
pISSN - 0038-0644
DOI - 10.1002/spe.904
Subject(s) - computer science , programming language , parsing , compiler , rotation formalisms in three dimensions , implementation , top down parsing language , parser combinator , rule based machine translation , abstract syntax tree , s attributed grammar , parsing expression grammar , grammar , parse tree , l attributed grammar , top down parsing , context free grammar , natural language processing , bottom up parsing , geometry , mathematics , linguistics , philosophy
Abstract We present a compiler that can be used to automatically obtain efficient Java implementations of parsing algorithms from formal specifications expressed as parsing schemata. The system performs an analysis of the inference rules in the input schemata in order to determine the best data structures and indexes to use, and to ensure that the generated implementations are efficient. The system described is general enough to be able to handle all kinds of schemata for different grammar formalisms, such as context‐free grammars and tree‐adjoining grammars, and it provides an extensibility mechanism allowing the user to define custom notational elements. This compiler has proven very useful for analyzing, prototyping and comparing natural‐language parsers in real domains, as can be seen in the empirical examples provided at the end of the paper. Copyright © 2008 John Wiley & Sons, Ltd.