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.
Probabilistic Parsing Strategies
SATTA, GIORGIO
2006
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.File in questo prodotto:
File | Dimensione | Formato | |
---|---|---|---|
p406-nederhof.pdf
non disponibili
Tipologia:
Published (publisher's version)
Licenza:
Accesso privato - non pubblico
Dimensione
350.84 kB
Formato
Adobe PDF
|
350.84 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
1218955.1219024.pdf
accesso aperto
Tipologia:
Preprint (submitted version)
Licenza:
Accesso libero
Dimensione
115.49 kB
Formato
Adobe PDF
|
115.49 kB | Adobe PDF | Visualizza/Apri |
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.