Implementazione “*?” (Pigro “*”) modello regexp nel parser GLR combinatori

Question

Ho implementato parser GLR combinatorie. Tra loro ci sono:

• parser char(·) che consuma specificati carattere o intervallo di caratteri.
• Combinator many(·) che ripete specificato parser da zero a infinite volte.

Esempio:. "char('a').many()" corrisponderà una stringa con un numero qualsiasi di "a"-s

Ma many(·) combinatore è avido, così, per esempio, char('{') >> char('{') >> char('a'..'z').many() >> char('}') >> char('}') (dove ">>" è il concatenamento sequenziale di parser) consumerà con successo l'intera stringa "{{foo}}some{{bar}}".

Voglio realizzare la versione pigra di many(·) che, utilizzato nell'esempio precedente, si consumano solo "{{foo}}". Come posso fare?

Modifica

Può essere ho confuso ya tutti. Nel mio programma di un parser è una funzione (o "funtore" in termini di C ++), che accetta un "passo" e ritorna foresta di "passi". Un "passo" può essere di tipo OK (questo significa che parser ha consumato parte di ingresso con successo) e il tipo FAIL (che significa che il parser ha riscontrato l'errore). Ci sono più tipi di passaggi, ma sono ausiliario.

Parser = f(Step) -> Collection of TreeNodes of Steps.

Così, quando ho ingresso parse, I:

• semplice Componi funzioni predefinite Parser per ottenere la funzione di parser complessa che rappresenta la grammatica necessaria.

• forma iniziale Passo dall'ingresso.

• Dare il primo passo per la funzione Parser complesso.

• Filtro TreeNodes con scala, lasciando solo quelle OK (o con minima FAIL-S Se ci fossero errori di ingresso).

• Raccogliere informazioni da Piazza di cui sono stati lasciati.

Answer 1

Si consideri il regolare <.*?> espressione e la <a>bc<d>ef ingresso. Questo dovrebbe trovare <a>, e non altre partite, giusto?

Consideriamo ora il <.*?>e espressione regolare con lo stesso ingresso. Questo dovrebbe trovare <a>bc<d>e, giusto?

Questo pone un dilemma. Per l'amor dell'utente, vogliamo che il comportamento del >> Combinator da intendersi in termini di due operandi. Eppure non v'è alcun modo di produrre il comportamento del secondo parser in termini di ciò che il primo si trova.

Una risposta è per ogni parser per produrre un sequenza di tutte le analizza, in ordine di preferenza, piuttosto che l'insieme non ordinato di tutti i parser. corrispondenza Greedy sarebbe tornato partite allineati lungo al più breve; non avido, più breve per raggiungere più lunga.

Answer 2

Ho implementato e sono state usando parser GLR per 15 anni come front-end di lingua per un sistema di programma di trasformazione.

Non so cosa sia un "GLR parser combinatoria" è, e io sono familiarità con la vostra notazione quindi non sono del tutto sicuro di come interpretarlo. Suppongo che questo sia un qualche tipo di notazione di funzione al curry? Sto immaginando le tue regole Combinator sono equivalenti ad un definining Grammer in termini di caratteri terminali, in cui corrisponde alle regole grammaticali "char ( 'a') molti.":

 char = "a" ;
 char = char "a" ;

parser GLR, infatti, producono tutti i possibili analizza. L'intuizione chiave per GLR analisi è la sua elaborazione pseudo-parallelo di tutti i possibili analizza. Se i "combinatori" possono proporre molteplici analizza (che è, di produrre regole grammaticali sorta di equivalente a quanto sopra), e si dispone in effetti li collegati ad un parser GLR, saranno tutti ottenere provato, e solo quelle sequenze di produzioni che tegola il testo sopravviverà (che significa tutto parsess valida, ad esempio, analizza ambigui) sopravviverà.

Se si è davvero implementato un parser GLR, questa raccolta di tutte le possibili analizza avrebbe dovuto essere estremamente chiaro a voi. Il fatto che non si tratta allude ciò che avete implementato non è un parser GLR.

recupero di errore con un parser GLR è possibile, proprio come con qualsiasi altra tecnologia di analisi. Quello che facciamo è mantenere l'insieme delle analizza in tempo reale prima del punto dell'errore; quando viene rilevato un errore, proviamo (in pseudo-parallelo, il GLR parsing macchine rende questo facile se esso piegato correttamente) tutte le seguenti: a) l'eliminazione del offendere gettone, b) inserire tutti i gettoni che sono essenzialmente SEGUITO (x) dove x è parse dal vivo. In sostanza, eliminare il token, o inserire quello atteso da un parse dal vivo. Abbiamo poi girare il parser GLR sciolto di nuovo. Solo i analizza validi (ad esempio, le riparazioni) sopravviverà. Se il token corrente non può essere elaborato, il parser elaborazione del flusso con il token cancellato sopravvive. Nel peggiore dei casi, i GLR parser di recupero errore finisce per gettare via tutti i gettoni di EOF. Un grave inconveniente di questo è tempo di esecuzione del parser GLR cresce abbastanza radicalmente durante l'analisi di errori; se ci sono molti in un unico luogo, il tempo di recupero di errore può passare attraverso il tetto.

Answer 3

Non sarà un parser GLR produrre tutti i possibili analizza dell'ingresso? Poi risolvere l'ambiguità è una questione di scegliere il parse che si preferisce. Per fare questo, suppongo che gli elementi della necessità foresta parse di essere etichettati in base al tipo di combinatore loro, ansiosi o pigri prodotta. (Non è possibile risolvere l'ambiguità in modo incrementale prima di aver visto tutti gli input, in generale.)

(La risposta in base alla mia pallido ricordo e vago possibile fraintendimento di GLR parsing. Speriamo che qualcuno esperto verrà da.)

Answer 4

funzionalità non avido non è altro che un meccanismo di disambiguazione. Se avete veramente un parser generalizzato (che non richiede disambiguazione per produrre i suoi risultati), quindi "non-greedy" è privo di significato; gli stessi risultati saranno restituiti se un operatore è "non-greedy".

comportamento disambiguation non avido potrebbe essere applicato al set completo di risultati forniti da un parser generalizzata. Lavorando da sinistra a destra, filtro sottogruppi ambigue corrispondenti ad un operatore non avido di utilizzare la corrispondenza più breve che ancora portato ad una parse successo della ingresso rimanente.