Sixth International Conference on Spoken Language Processing (ICSLP 2000)

Beijing, China
October 16-20, 2000

Optimizing BNF Grammars through Source Transformations

Bob Carpenter, Sol Lerner, Roberto Pieraccini

SpeechWorks International, Inc., USA

In this paper we explore the efficiency of various ways of expressing the form and meaning of natural language utterances as context-free grammars. We concentrate on the top-down parsing strategy employed in SpeechWorks 6.5, a strategy common to many systems. As with other search-based parsers, the key to efficiency is to limit the uncertainty of the parser at any given stage by reducing non-determinism in the grammar. Here we study the effects of different expressions of the same grammar in terms of efficiency. We also describe a methodology for transforming a source grammar into a more efficient expression of the same forms and meanings.

Full Paper

Bibliographic reference.  Carpenter, Bob / Lerner, Sol / Pieraccini, Roberto (2000): "Optimizing BNF grammars through source transformations", In ICSLP-2000, vol.1, 194-197.