parser GLR con recupero di errore: troppo alternative quando ci sono errori di ingresso

Question

Preambolo

Ho scritto GLR-parser con recupero degli errori. Quando si incontra un errore si divide in seguenti alternative:

1. Inserire l'elemento previsto in ingresso (può essere l'utente appena perso) e procedere come al solito.
2. Sostituire l'elemento errato con quello atteso (può essere l'utente appena fatto un mistype) e procedere come al solito.
3. Vai elemento erronea e se la prossima elemento è anche errato poi andare a # 2.

Ma se l'ingresso ha un sacco di errori (per esempio, l'utente ha per errore dato file JPEG al parser) una serie di alternative cresce esponenzialmente.

Esempio

Tale parser corrispondente alla seguente grammatica:

Program -> Identifier WS Identifier WS '=' WS Identifier
Identifier -> ('a'..'z' | 'A'..'Z' | '0'..'9')*
WS -> ' '*

applicata al seguente testo:

x = "abc\"def"; y = "ghi\"jkl";

fallisce con "out of memory", a moderatamente moderno computer desktop.

Domanda

Come ridurre il numero di alternative in caso di errori in ingresso?

Answer 1

In questo GLR (parsing quindi) la correzione degli errori a livello di carattere è possibile, ma aggrava il problema.

La procedura di recupero degli errori GLR usiamo opera su gettoni, quindi non è così male.

Ma quando l'ingresso ha un numero enorme di errori, è piuttosto difficile da recuperare. Più sofisticati sistemi di recupero di errore praticamente utilizzano il parser per identificare valide stringhe della lingua in ingresso, e quindi tenta di rattoppare le sottostringhe insieme per ottenere il risultato. Questo è abbastanza ambizioso.

Ho costruito parser GLR con recupero degli errori. Io non ero così ambizioso. In generale il parser soprattutto solo interrompe quando il numero di parser vivi ottiene sopra "un gran numero" (ad esempio, 10.000) o il numero di errori di sintassi riscontrati superano una soglia (ad esempio, 10 o 20). Si potrebbe prendere in considerazione l'interruzione del parser, se non ha avanzato il flusso di input nell'ultimo secondo, che è un segno indiretto che ha troppi parser dal vivo.