Theoretical analysis reveals conditions preserving probability distributions in context-free parsing, highlighting fundamental limitations in generalized LR parsing.
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.
No takes yet. Share an insight, caveat, or question.
Nederhof et al. (2006) studied this question.
Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context: