Probabilistic parsing strategies

Research output: Contribution to journalArticlepeer-review

10 Citations (Scopus)

Abstract

We present new results on the relation between purely symbolic context-free parsing strategies and their probabilistic counterparts. Such parsing strategies are seen as constructions of push-down devices from grammars. We show that preservation of probability distribution is possible under two conditions, viz. the correct-prefix property and the property of strong predictiveness. These results generalize existing results in the literature that were obtained by considering parsing strategies in isolation. From our general results, we also derive negative results on so-called generalized LR parsing.

Original languageEnglish
Pages (from-to)406-436
Number of pages31
JournalJournal of the ACM
Volume53
Issue number3
DOIs
Publication statusPublished - May 2006

Keywords

  • algorithms
  • theory
  • parsing algorithms
  • probabilistic parsing
  • transduction
  • context-free grammars
  • push-down automata
  • CONTEXT-FREE GRAMMARS
  • LANGUAGES
  • AUTOMATA
  • FORM

Fingerprint

Dive into the research topics of 'Probabilistic parsing strategies'. Together they form a unique fingerprint.

Cite this