I parser sono programmi che aiutano a elaborare il testo. I compilatori e gli interpreti utilizzano i parser per analizzare i programmi prima di elaborarli ulteriormente e i parser per formati come JSON e YAML elaborano il testo nelle strutture dati native del linguaggio di programmazione.
In questo articolo, vedremo come costruire "parser di discesa ricorsivi". I parser di discesa ricorsivi sono un modo semplice ma potente per creare parser:per ogni "entità" nel testo che vuoi elaborare, definisci una funzione.
In primo luogo, esamineremo alcune delle teorie alla base dell'analisi. Quindi, usando Python, creeremo una calcolatrice e un parser JSON che supporti commenti, virgole finali e stringhe senza virgolette. Infine, discuteremo di come creare parser per altri tipi di linguaggi che si comportano in modo diverso rispetto agli esempi summenzionati.
Se hai già familiarità con la teoria, puoi saltare direttamente alle parti in cui costruiamo il parser.
Contenuti
- 1 Come funziona l'analisi?
- 2 Scrivere regole di produzione
- 3 Considerazioni sulla creazione di parser
- 3.1 Gestire la precedenza nelle grammatiche
- 3.2 Evitare la ricorsione a sinistra
- 3.3 Evitare il backtracking
- 4 Costruire una base per il parser di discese ricorsive in Python
- 4.1 La classe di eccezione
- 4.2 La classe Parser di base
- 4.3 Elaborazione degli intervalli di caratteri
- 4.4 Estrarre caratteri dal testo
- 4.5 Estrazione di parole chiave e simboli
- 4.6 Un aiuto per abbinare più produzioni
- 4.7 Guardando al futuro:le funzioni di supporto
- 5 Primo esempio di parser:una calcolatrice
- 5.1 Regole di produzione per la grammatica della calcolatrice
- 5.2 Implementazione del parser
- 5.3 Riconoscimento dei numeri
- 5.4 Un'interfaccia per il nostro parser
- 6 Secondo esempio di parser:un parser JSON "esteso"
- 6.1 Regole di produzione per la grammatica JSON
- 6.2 Implementazione del parser e gestione dei commenti
- 6.3 Analisi di elenchi e mappe
- 6.4 Riconoscimento null e booleano
- 6.5 Riconoscimento di stringhe e numeri senza virgolette
- 6.6 Riconoscimento di stringhe tra virgolette
- 6.7 Un'interfaccia per il nostro parser JSON
- 7 Creazione di altri tipi di parser
- 7.1 Linguaggi sensibili agli spazi bianchi
- 7.2 Rientro basato su spazi bianchi
Come funziona l'analisi?
Per elaborare un pezzo di testo, un programma esegue tre compiti. In un processo chiamato "lexing" o "tokenizzazione", il programma esamina i caratteri nel testo ed estrae gruppi logici chiamati "token". Ad esempio, in un'espressione come "3 + 5 – 10", un programma per elaborare espressioni aritmetiche potrebbe estrarre i seguenti token:
[{ "Type": "Number" , "Text": "3" },
{ "Type": "Operator", "Text": "+" },
{ "Type": "Number" , "Text": "5" },
{ "Type": "Operator", "Text": "-" },
{ "Type": "Number" , "Text": "10" }] Il programma utilizza quindi le regole per identificare sequenze significative di token, e questo viene chiamato "analisi". Le regole utilizzate per fare in modo che ciò accada sono chiamate "grammatiche", più o meno allo stesso modo in cui le parole di una lingua naturale come l'inglese sono messe insieme in sequenze significative usando la grammatica inglese. Le singole regole di una grammatica sono dette “produzioni”.
Immagina di costruire un programma per elaborare espressioni matematiche e ci interessa solo l'addizione e la sottrazione. Un'espressione deve avere un numero (come "3"), seguito da un numero qualsiasi di operatori e numeri (come "+ 5" ). La regola di analisi può essere visualizzata in questo modo:
Indica che il gruppo può ripetere un numero qualsiasi di volte (incluso zero).
Infine, il programma esegue una serie di azioni per una regola grammaticale. Ad esempio, dopo l'analisi, il nostro programma matematico dovrebbe calcolare il valore dell'espressione.
Sebbene li abbiamo descritti come passaggi separati, un programma può eseguirli tutti contemporaneamente. Eseguire tutti i passaggi contemporaneamente comporta alcuni vantaggi e questo è l'approccio che adotteremo in questo articolo.
Scrittura delle regole di produzione
Nel resto di questo articolo, utilizzeremo le regole di produzione per visualizzare le grammatiche. Pertanto, abbiamo spiegato come scriviamo le regole di produzione in questo articolo. Se in precedenza hai letto un libro di testo sull'analisi, la notazione che abbiamo usato qui è leggermente diversa.
In precedenza, abbiamo visto un esempio di una produzione semplice. Quando la regola grammaticale contiene il nome di un token e il token è abbastanza semplice, è comune scrivere il testo del token nella grammatica. Se consideriamo l'esempio precedente, restituisce un + o un - , quindi potremmo riscrivere la regola in questo modo:
Abbiamo anche visto come possiamo usare per indicare che qualcosa si ripete un numero qualsiasi di volte. Allo stesso modo, a indica che qualcosa si ripete, ma dovrebbe verificarsi almeno una volta. A indica qualcosa che è facoltativo.
Ad esempio, supponiamo di costruire un parser per elaborare un elenco di condizioni, come "x> 10 e y> 30". Supponiamo che il and è opzionale, quindi potremmo riscrivere questa condizione come "x> 10 y> 30". Potresti progettare una grammatica per quanto sopra in questo modo:
Quando ci sono più alternative, l'ordine delle alternative è importante. Per una regola come , dovremmo provare a far corrispondere prima un "+" e poi un "-". Anche se in questo banale esempio potrebbe sembrare che l'ordine non abbia importanza, vedremo più avanti esempi in cui l'ordine diventa importante.
Infine, una regola di produzione si concentra solo su token e altri simboli grammaticali:ignora gli spazi bianchi e i commenti.
Considerazioni sulla creazione di parser
In precedenza, abbiamo visto alcune semplici grammatiche. Tuttavia, quando si tenta di analizzare qualcosa di più complesso, possono verificarsi numerosi problemi. Ne discuteremo qui.
Gestire la precedenza nelle grammatiche
In precedenza, abbiamo visto una grammatica in grado di gestire un'espressione matematica composta da addizioni e sottrazioni. Sfortunatamente, non puoi estendere la stessa grammatica per le moltiplicazioni (e le divisioni), poiché queste operazioni hanno una precedenza maggiore rispetto alle addizioni (e alle sottrazioni).
Per gestire questo scenario, dobbiamo progettare la nostra grammatica in modo che il parser rinvii qualsiasi addizione, ma esegua le moltiplicazioni non appena viene incontrata. Per ottenere ciò, dividiamo la grammatica in due regole separate, come mostrato di seguito:
Prendiamo un'espressione (come "3 + 2 * 5") per assicurarci che funzioni davvero. Assumiamo che una volta che il nostro parser ha finito di abbinare una regola grammaticale, calcola automaticamente l'espressione. Useremo anche il testo sottolineato per indicare cosa sta cercando il parser. Inoltre, abbiamo anche omesso le virgolette per chiarezza.
Quando 2 * 5 viene analizzato, il parser restituisce immediatamente il risultato di 10. Questo risultato viene ricevuto al passaggio e l'aggiunta viene eseguita alla fine, ottenendo 13 come risultato.
In sintesi, dovresti organizzare le tue regole in modo che gli operatori con la precedenza più bassa siano in alto, mentre quelli con la precedenza più alta siano in fondo.
Evitare la ricorsione a sinistra
In precedenza, abbiamo menzionato che un parser discendente ricorsivo è costituito da funzioni che elaborano "entità" nel testo. Ora che conosciamo i token e le regole di produzione, ridefiniamo questo aspetto un po' più formalmente:ogni funzione nel parser estrae un token o implementa la logica di una regola di produzione.
Prendiamo una semplice grammatica, tale da vedere cosa significa veramente. Se hai scritto lo pseudocodice per questa grammatica, sarebbe simile a questo:
def expression():
first_number = number()
read('+')
second_number = number()
# process these two numbers, e.g. adding them
Quindi, considera una grammatica che analizzi un elenco di numeri separati da virgole. In genere lo scrivi come:
Ora, immagina che per qualche motivo tu voglia evitare il carattere jolly e riscriverlo in questo modo:
Questa grammatica è teoricamente corretta:preleva un singolo numero dal testo o si espande in un elenco con un numero alla fine. Il secondo elenco, a sua volta, può espandersi in un altro numero o in un elenco, finché il parser non termina il testo.
Tuttavia, c'è un problema con questo approccio:entreresti in una ricorsione infinita! Se provi a chiamare il list() funzione una volta, finisci per chiamarlo di nuovo e così via. Potresti pensare che riscrivere la grammatica potrebbe aiutare. Tuttavia, se provassi a scrivere una funzione, leggeresti un singolo numero e usciresti dall'analisi. Il numero che hai letto potrebbe far parte di un elenco come "2, 4, 6" e non sarai in grado di leggere gli altri numeri.
Quando si ha a che fare con l'analisi, questo è chiamato ricorsione a sinistra. Il caso che abbiamo visto sopra riguarda la "ricorsione sinistra diretta", ma c'è anche la "ricorsione sinistra indiretta", dove A chiama B, B chiama A e così via. In entrambi i casi, dovresti riscrivere la grammatica in un altro modo per evitare questo problema.
Evitare di tornare indietro
Supponiamo che tu stia cercando di costruire un parser che analizzi un'operazione di due numeri, come "2 + 4", e scriva una grammatica in questo modo:
Questa grammatica è corretta e si comporterà anche nel modo in cui ti aspetti e produrrà risultati corretti. Tuttavia, questa grammatica non è ciò che vorresti usare.
Per vedere perché questo è il caso, considera la stringa di input "5 – 2". Per prima cosa andremo con la regola di addizione e analizzeremo un numero. Quindi, ci aspetteremmo un "+" ma quando leggiamo la stringa, otterremo un "-" il che significa che dobbiamo tornare indietro e applicare la regola di sottrazione. In tal modo, abbiamo perso tempo e cicli della CPU nell'analisi di un numero, solo per scartarlo e analizzarlo di nuovo come parte della regola di sottrazione.
Inoltre, quando si creano parser che funzionano direttamente con flussi di dati, come un socket di rete, spesso non è possibile riavvolgere il flusso. In questo articolo tratteremo solo parser che hanno tutto il testo in memoria. Tuttavia, è una buona pratica evitare di tornare indietro e, per farlo, dovresti escludere le parti comuni da sinistra. Ecco come la nostra regola si occuperebbe del factoring:
La fase di factoring è completa ed eviterà il backtracking. Tuttavia, per motivi estetici, lo scriveremo semplicemente come:
Costruire una base per il parser di discese ricorsive in Python
Ora che abbiamo discusso le varie considerazioni per l'analisi, creeremo la calcolatrice e il parser JSON. Tuttavia, prima di farlo, scriveremo una classe "Parser" di base che abbia alcuni metodi per funzioni comuni, come il riconoscimento dei caratteri e la gestione degli errori.
Questa sezione potrebbe sembrare un po' troppo lunga, ma ne vale la pena. Una volta completata questa sezione, avrai tutti gli strumenti per creare parser complessi con pochissimo codice richiesto per riconoscere i token e implementare le regole di produzione.
La classe di eccezione
Poiché questo è di gran lunga il compito più semplice, quindi affronteremo questo prima. Definiremo la nostra classe di eccezione denominata ParseError così:
class ParseError(Exception):
def __init__(self, pos, msg, *args):
self.pos = pos
self.msg = msg
self.args = args
def __str__(self):
return '%s at position %s' % (self.msg % self.args, self.pos)
La classe accetta la posizione del testo in cui si è verificato l'errore, un messaggio di errore (come stringa di formato) e gli argomenti della stringa di formato. Vediamo come potresti utilizzare questo tipo di eccezione:
e = ParseError(13, 'Expected "{" but found "%s"', "[") Quando provi a stampare l'eccezione, riceverai un messaggio formattato come questo:
Expected "{" but found "[" at position 13
Nota che non abbiamo utilizzato un % simbolo all'interno della stringa di formato e dei suoi argomenti (come '"Expected "{" but found "%s"' % "[" ). Questo è gestito in __str__ metodo della classe, dove abbiamo formattato self.msg con elementi in self.pos .
Ora, potresti chiederti perché vogliamo formattarlo nel __str__ metodo, invece di scriverlo con un % ? Si scopre che usando il % operatore per formattare una stringa richiede un bel po' di tempo. Durante l'analisi di una stringa, verranno sollevate molte eccezioni poiché il parser tenta di applicare varie regole. Pertanto, abbiamo posticipato la formattazione della stringa a quando è veramente necessaria.
La classe Parser di base
Ora che abbiamo una classe di errore in atto, il passaggio successivo è scrivere la classe del parser. Lo definiremo come segue:
class Parser:
def __init__(self):
self.cache = {}
def parse(self, text):
self.text = text
self.pos = -1
self.len = len(text) - 1
rv = self.start()
self.assert_end()
return rv
Qui noterai un cache membro nel __init__ metodo:torneremo sul motivo per cui è necessario quando discutiamo di riconoscere i caratteri.
Il parse è abbastanza semplice:in primo luogo, memorizza la stringa. Poiché non abbiamo ancora scansionato nessuna parte della stringa, imposteremo la posizione su -1. Inoltre, memorizzeremo l'indice massimo della stringa in self.len . (L'indice massimo è sempre uno in meno rispetto alla lunghezza della stringa.)
Successivamente, inizieremo ad analizzare la stringa e verificheremo se abbiamo raggiunto la fine della stringa. Questo per garantire che il nostro parser sia stato in grado di elaborare l'intero testo senza che sia rimasto nulla alla fine. Dopo questo, restituiamo il risultato.
Il assert_end il metodo è semplice:verificheremo se la posizione corrente è inferiore all'indice massimo. Tieni presente che questi metodi sono all'interno della classe, anche se abbiamo omesso il rientro per semplicità.
def assert_end(self):
if self.pos < self.len:
raise ParseError(
self.pos + 1,
'Expected end of string but got %s',
self.text[self.pos + 1]
)
Durante il nostro parser, esamineremo il carattere che è uno in più rispetto all'indice corrente (self.pos ). Per capire perché questo è il caso, considera che iniziamo con self.pos = -1 , quindi esamineremo l'indice 0. Dopo aver riconosciuto correttamente un carattere, self.pos va a 0 e guardiamo il carattere all'indice 1 e così via. Questo è il motivo per cui l'errore utilizza self.pos + 1 .
Con la maggior parte delle lingue, gli spazi bianchi tra i token possono essere eliminati in modo sicuro. Pertanto, sembra logico includere un metodo che controlli se il carattere successivo è uno spazio vuoto e, in tal caso, lo "scarta" avanzando alla posizione successiva.
def eat_whitespace(self):
while self.pos < self.len and self.text[self.pos + 1] in " fvrtn":
self.pos += 1
Elaborazione degli intervalli di caratteri
Ora scriveremo una funzione che ci aiuti a riconoscere i caratteri nel testo. Prima di farlo, però, considereremo la nostra funzione dal punto di vista dell'utente:gli daremo una serie di caratteri da abbinare al testo. Ad esempio, se desideri riconoscere un alfabeto o un trattino basso, potresti scrivere qualcosa come:
self.char('A-Za-z_')
Daremo il char metodo contenente un elenco di caratteri o intervalli (come A-Z nell'esempio sopra). Gli intervalli sono indicati da due caratteri separati da un - . Il primo carattere ha un valore numericamente inferiore a quello a destra.
Ora, se il carattere a self.text[self.pos + 1] corrisponde a qualcosa nell'argomento di self.char , lo restituiremo. In caso contrario, solleveremo un'eccezione.
Internamente, elaboreremo la stringa in qualcosa di più facile da gestire:un elenco con caratteri o intervalli separati come ['A-Z', 'a-z', '_'] . Quindi, scriveremo una funzione per dividere gli intervalli:
def split_char_ranges(self, chars):
try:
return self.cache[chars]
except KeyError:
pass
rv = []
index = 0
length = len(chars)
while index < length:
if index + 2 < length and chars[index + 1] == '-':
if chars[index] >= chars[index + 2]:
raise ValueError('Bad character range')
rv.append(chars[index:index + 3])
index += 3
else:
rv.append(chars[index])
index += 1
self.cache[chars] = rv
return rv
Qui, esaminiamo il chars stringa, cercando un - seguito da un altro personaggio. Se questa condizione corrisponde e il primo carattere è più piccolo dell'ultimo, aggiungiamo l'intero intervallo (come A-Z ) alla lista rv . Altrimenti, aggiungiamo il carattere in chars[index] a rv .
Quindi, aggiungiamo l'elenco in rv nella cache. Se vediamo questa stringa una seconda volta, la restituiremo dalla cache utilizzando il try ... except KeyError: ... blocco in alto.
Certo, avremmo potuto semplicemente fornire un elenco come ['A-Z', 'a-z', '_'] al char metodo. Tuttavia, a nostro avviso, facendo in questo modo si effettuano chiamate a char() sembri un po' più pulito.
Estrarre caratteri dal testo
Ora che abbiamo un metodo che fornisce un elenco contenente intervalli e caratteri, possiamo scrivere la nostra funzione per estrarre un carattere dal testo. Ecco il codice per il char metodo:
def char(self, chars=None):
if self.pos >= self.len:
raise ParseError(
self.pos + 1,
'Expected %s but got end of string',
'character' if chars is None else '[%s]' % chars
)
next_char = self.text[self.pos + 1]
if chars == None:
self.pos += 1
return next_char
for char_range in self.split_char_ranges(chars):
if len(char_range) == 1:
if next_char == char_range:
self.pos += 1
return next_char
elif char_range[0] <= next_char <= char_range[2]:
self.pos += 1
return next_char
raise ParseError(
self.pos + 1,
'Expected %s but got %s',
'character' if chars is None else '[%s]' % chars,
next_char
)
Concentriamoci prima sull'argomento chars=None . Ciò ti consente di chiamare self.char() senza dargli una serie di caratteri. Questo è utile quando vuoi semplicemente estrarre un carattere senza limitarlo a un set specifico. Altrimenti, puoi chiamarlo con un intervallo di caratteri, come abbiamo visto nella sezione precedente.
Questa funzione è abbastanza semplice:in primo luogo, controlliamo se abbiamo esaurito il testo. Quindi, scegliamo il carattere successivo e controlliamo se chars è None , nel qual caso possiamo incrementare la posizione e restituire immediatamente il carattere.
Tuttavia, se è presente un insieme di caratteri in chars , lo dividiamo in un elenco di singoli caratteri e intervalli, come ['A-Z', 'a-z', '_'] . In questo elenco, una stringa di lunghezza 1 è un carattere e qualsiasi altra cosa è un intervallo. Verifica se il carattere successivo corrisponde al carattere o all'intervallo e, in caso affermativo, lo restituiamo. Se non siamo riusciti a confrontarlo con qualcosa, esce dal ciclo che genera ParseError , affermando che non siamo riusciti a ottenere il carattere previsto.
Il 'character' if chars is None else '[%s]' % chars è solo un modo per fornire un'eccezione più leggibile. Se chars è None , il messaggio dell'eccezione leggerebbe Expected character but got ... , ma se char era impostato su qualcosa come A-Za-z_ , otterremmo Expected [A-Za-z_] but got ... .
Più avanti vedremo come utilizzare questa funzione per riconoscere i token.
Estrazione di parole chiave e simboli
Oltre all'estrazione di singoli caratteri, il riconoscimento delle parole chiave è un compito comune durante la creazione di un parser. Stiamo usando "parole chiave" per fare riferimento vagamente a qualsiasi stringa contigua che è la "propria entità" e potrebbe avere spazi bianchi prima e dopo di essa. Ad esempio, in JSON { potrebbe essere una parola chiave e in un linguaggio di programmazione if , else potrebbe essere una parola chiave e così via.
Questo è il codice per riconoscere le parole chiave:
def keyword(self, *keywords):
self.eat_whitespace()
if self.pos >= self.len:
raise ParseError(
self.pos + 1,
'Expected %s but got end of string',
','.join(keywords)
)
for keyword in keywords:
low = self.pos + 1
high = low + len(keyword)
if self.text[low:high] == keyword:
self.pos += len(keyword)
self.eat_whitespace()
return keyword
raise ParseError(
self.pos + 1,
'Expected %s but got %s',
','.join(keywords),
self.text[self.pos + 1],
)
Questo metodo accetta parole chiave, come self.keyword('if', 'and', 'or') . Il metodo rimuove gli spazi bianchi e quindi controlla se abbiamo esaurito il testo da analizzare. Quindi scorre ogni parola chiave, controllando se la parola chiave esiste nel testo. Se trova qualcosa, elimineremo lo spazio bianco dopo la parola chiave, quindi restituiremo la parola chiave.
Tuttavia, se non trova qualcosa, esce dal ciclo che genera ParseError , affermando che non è stato possibile trovare le parole chiave.
Un aiuto per abbinare più produzioni
Nelle sezioni precedenti, hai notato che utilizziamo le eccezioni per segnalare gli errori. Sappiamo anche che per scrivere un parser discendente ricorsivo, si scrivono funzioni che riconoscono un token o una regola di produzione. Ora, immagina di voler analizzare un testo semplice, in cui ti aspetti un numero o una parola. La regola di produzione potrebbe essere simile a:
Assumiamo anche che il testo contenga una parola. Quando il parser prova a cercare una cifra (magari usando char() ), non lo troverà e questo provoca la generazione di un'eccezione. Inoltre, devi eliminare gli spazi bianchi prima e dopo aver abbinato una regola di produzione. Quindi, il codice per item() potrebbe assomigliare a questo:
def item(self): self.eat_whitespace() try: rv = self.number() except ParseError: rv = self.word() self.eat_whitespace() return rv
Sembra già molto per implementare una semplice regola! Immagina come sarebbe implementare una regola complessa:dovresti usare try...except blocchi dappertutto.
Quindi, scriveremo un match() funzione che rimuoverà lo spazio bianco e proverà a far corrispondere più regole. La funzione è la seguente:
def match(self, *rules):
self.eat_whitespace()
last_error_pos = -1
last_exception = None
last_error_rules = []
for rule in rules:
initial_pos = self.pos
try:
rv = getattr(self, rule)()
self.eat_whitespace()
return rv
except ParseError as e:
self.pos = initial_pos
if e.pos > last_error_pos:
last_exception = e
last_error_pos = e.pos
last_error_rules.clear()
last_error_rules.append(rule)
elif e.pos == last_error_pos:
last_error_rules.append(rule)
if len(last_error_rules) == 1:
raise last_exception
else:
raise ParseError(
last_error_pos,
'Expected %s but got %s',
','.join(last_error_rules),
self.text[last_error_pos]
)
Prima di discutere di come funziona, vediamo quanto è semplice riscrivere il nostro esempio precedente usando match() :
def item(self):
return self.match('number', 'word')
Allora, come funziona? match() accetta un nome di metodo da eseguire (come number o word nell'esempio sopra). Innanzitutto, si sbarazza dello spazio bianco all'inizio. Quindi, esegue l'iterazione su tutti i nomi dei metodi e recupera ogni metodo utilizzando il suo nome tramite getattr() . Quindi prova a invocare il metodo e, se tutto va bene, rimuoverà anche gli spazi bianchi dopo il testo. Infine, restituisce il valore che ha ricevuto chiamando il metodo
Tuttavia, se si verifica un errore, reimposta self.pos al valore che era presente prima di provare a far corrispondere una regola. Quindi, prova a selezionare un buon messaggio di errore utilizzando le seguenti regole:
- Quando si confrontano più regole, molte di esse potrebbero generare un errore. L'errore che è stato generato dopo aver analizzato la maggior parte del testo è probabilmente il messaggio di errore che vogliamo.
Per vedere perché questo è il caso, considera la stringa "abc1". Tentativo di chiamare number() fallirebbe alla posizione 0, mentre word() fallirebbe nella posizione 2. Osservando la stringa, è molto probabile che l'utente abbia voluto inserire una parola, ma ha commesso un errore di battitura.
- Se due o più regole errate finiscono in "pareggio", preferiamo informare l'utente di tutte le regole che hanno fallito.
Il last_error_pos e last_exception tiene traccia rispettivamente della posizione e dell'eccezione dell'ultimo errore. Inoltre, manteniamo un elenco last_error_rules in modo che, in caso di parità, possiamo comunicare all'utente tutte le regole che abbiamo cercato di abbinare.
Nel except ParseError blocco, confrontiamo la posizione dell'ultimo errore e l'errore corrente. Se l'errore corrente è uguale, lo consideriamo un pareggio e lo aggiungiamo all'elenco. In caso contrario, aggiorniamo la posizione dell'errore, l'eccezione e l'elenco delle regole errate.
Alla fine, controlliamo quante regole hanno fallito. Se ce n'è solo uno, last_exception avrebbe il miglior messaggio di errore. In caso contrario, è un pareggio e lo faremo sapere all'utente con un messaggio come Expected number,word but found ... .
Sguardo al futuro:funzioni di supporto
A questo punto, abbiamo tutte le cose necessarie nel nostro parser e tutti gli errori generano eccezioni. Tuttavia, a volte vogliamo abbinare un carattere, una parola chiave o una regola solo se è presente, senza l'inconveniente di gestire le eccezioni.
Presenteremo tre piccoli aiutanti per fare proprio questo. Nel caso di un'eccezione durante la ricerca di materiale, questi restituiranno None :
def maybe_char(self, chars=None):
try:
return self.char(chars)
except ParseError:
return None
def maybe_match(self, *rules):
try:
return self.match(*rules)
except ParseError:
return None
def maybe_keyword(self, *keywords):
try:
return self.keyword(*keywords)
except ParseError:
return None
L'uso di queste funzioni è facile. Ecco come potresti usarli:
operator = self.maybe_keyword('+', '-'):
if operator == '+':
# add two numbers
elif operator == '-':
# subtract two numbers
else: # operator is None
# do something else
Primo esempio di parser:una calcolatrice
Ora che abbiamo costruito le basi per scrivere un parser, costruiremo il nostro primo parser. Sarà in grado di analizzare espressioni matematiche con addizioni, sottrazioni, moltiplicazioni, divisioni e anche gestire espressioni tra parentesi come "(2 + 3) * 5".
Inizieremo visualizzando la grammatica sotto forma di regole di produzione.
Regole di produzione per la grammatica della calcolatrice
In precedenza abbiamo visto una grammatica per gestire tutto tranne le espressioni tra parentesi:
Ora, pensiamo a come le espressioni tra parentesi si adattano a questa grammatica. Quando valutiamo "(2 + 3) * 5", dovremmo calcolare "(2 + 3)" e ridurlo a un numero. Ciò significa che nella grammatica precedente, il termine "Numero" può riferirsi a un'espressione tra parentesi oa qualcosa che è in realtà un numero, come "5".
Quindi, modificheremo le nostre regole per soddisfare entrambi. Nella regola per "Termine", sostituiremo "Numero" con un termine più appropriato come "Fattore". "Fattore" può quindi fare riferimento a un'espressione tra parentesi o a un "Numero". La grammatica modificata si presenta così:
Detto questo, implementiamo le regole di produzione!
Implementazione del parser
Implementeremo il nostro parser Calcolatrice estendendo la classe Parser di base. Iniziamo a definire la classe in questo modo:
class CalcParser(Parser):
def start(self):
return self.expression()
In precedenza, quando si implementava la classe del parser di base, avevamo un start() metodo per avviare l'analisi. Chiameremo semplicemente il expression() metodo qui, che definiremo come di seguito:
def expression(self):
rv = self.match('term')
while True:
op = self.maybe_keyword('+', '-')
if op is None:
break
term = self.match('term')
if op == '+':
rv += term
else:
rv -= term
return rv
La regola grammaticale per . Quindi, iniziamo leggendo un termine dal testo. Quindi impostiamo un ciclo infinito e cerchiamo un "+" o "-". Se non lo troviamo, significa che abbiamo finito di leggere l'elenco dei termini aggiuntivi come indicato da , quindi possiamo uscire dal giro.
Altrimenti, leggiamo un altro termine dal testo. Quindi, a seconda dell'operatore, lo aggiungiamo o lo sottraiamo dal valore iniziale. Continuiamo con questo processo finché non riusciamo a ottenere un "+" o "-" e restituire il valore alla fine.
Implementeremo term() allo stesso modo:
def term(self):
rv = self.match('factor')
while True:
op = self.maybe_keyword('*', '/')
if op is None:
break
term = self.match('factor')
if op == '*':
rv *= term
else:
rv /= term
return rv Successivamente, implementeremo "Fattore". Proveremo a leggere prima una parentesi a sinistra, il che significa che c'è un'espressione tra parentesi. Se troviamo una parentesi, leggiamo un'espressione e la parentesi chiusa e restituiamo il valore dell'espressione. In caso contrario, leggiamo e restituiamo semplicemente un numero.
def factor(self):
if self.maybe_keyword('('):
rv = self.match('expression')
self.keyword(')')
return rv
return self.match('number')
Nella prossima sezione faremo in modo che il nostro parser riconosca un numero.
Riconoscere i numeri
Per riconoscere un numero, dobbiamo guardare i singoli caratteri nel nostro testo. I numeri sono costituiti da una o più cifre, eventualmente seguite da una parte decimale. La parte decimale ha un punto (.) e seguito da almeno una cifra. Inoltre, i numeri possono avere un segno come "+" o "-" prima di loro, come "-124,33".
Implementeremo il number() metodo in questo modo:
def number(self):
chars = []
sign = self.maybe_keyword('+', '-')
if sign is not None:
chars.append(sign)
chars.append(self.char('0-9'))
while True:
char = self.maybe_char('0-9')
if char is None:
break
chars.append(char)
if self.maybe_char('.'):
chars.append('.')
chars.append(self.char('0-9'))
while True:
char = self.maybe_char('0-9')
if char is None:
break
chars.append(char)
rv = float(''.join(chars))
return rv
Sebbene la funzione sia lunga, è abbastanza semplice. Abbiamo un chars lista in cui mettiamo i caratteri del numero. Innanzitutto, esaminiamo tutti i simboli "+" o "-" che potrebbero essere presenti prima del numero. Se è presente, lo aggiungiamo all'elenco. Quindi, cerchiamo la prima cifra obbligatoria del numero e continuiamo a cercare altre cifre utilizzando il maybe_char() metodo. Una volta ottenuto None tramite maybe_char , sappiamo che abbiamo superato l'insieme di cifre e terminiamo il ciclo.
Allo stesso modo, cerchiamo la parte decimale e le sue cifre. Infine, convertiamo tutti i caratteri in una stringa, che a sua volta convertiamo in un numero in virgola mobile.
Un'interfaccia per il nostro parser
Abbiamo finito di costruire il nostro parser. Come passaggio finale, aggiungeremo un po' di codice nell'ambito globale che ci consentirà di inserire espressioni e vedere i risultati:
if __name__ == '__main__':
parser = CalcParser()
while True:
try:
print(parser.parse(input('> ')))
except KeyboardInterrupt:
print()
except (EOFError, SystemExit):
print()
break
except (ParseError, ZeroDivisionError) as e:
print('Error: %s' % e)
Se hai seguito finora, congratulazioni! Hai creato il tuo primo parser di discesa ricorsivo!
Se stai seguendo un IDE locale, a questo punto puoi eseguire il tuo codice. In alternativa, puoi utilizzare il playground qui sotto per eseguire il parser. Puoi inserire le espressioni attraverso la scheda "Input" di seguito:
Puoi anche trovare il codice completo qui.
Secondo esempio di parser:un parser JSON "esteso"
JSON è un formato di interscambio di dati che supporta strutture di dati di base come numeri, stringhe ed elenchi. È un formato molto utilizzato, anche se la sua semplicità significa che manca di cose come commenti e rigoroso sulle cose che accetta. Ad esempio, non puoi avere una virgola finale in un elenco o avere un "+" esplicito davanti a un numero per indicarne il segno.
Poiché Python ha già un modulo JSON, mireremo a un po' più in alto e creeremo un parser JSON che supporti commenti, virgole finali e stringhe senza virgolette.
L'implementazione di questo parser ti insegnerà come gestire i commenti. Illustrerà anche come creare un linguaggio facile da usare possa rendere complicata l'analisi e come affrontare tali situazioni.
Prima di implementare la nostra grammatica, diamo un'idea del nostro formato JSON esteso:
{
# Comments begin with a '#' and continue till the end of line.
# You can skip quotes on strings if they don't have hashes,
# brackets or commas.
Size: 1.5x,
# Trailing commas are allowed on lists and maps.
Things to buy: {
Eggs : 6,
Bread: 4,
Meat : 2,
},
# And of course, plain JSON stuff is supported too!
"Names": ["John", "Mary"],
"Is the sky blue?": true
} Regole di produzione per la grammatica JSON
Il nostro JSON esteso si attiene agli stessi tipi di dati supportati da JSON. JSON ha quattro tipi di dati primitivi:null, booleani, numeri e stringhe e due tipi di dati complessi:elenchi (o array) e mappe (chiamate anche hash o dizionari). Gli elenchi e gli hash sono simili a quelli di Python.
Poiché i dati JSON sarebbero costituiti da uno di questi tipi, potresti scrivere le regole di produzione in questo modo:
Quindi, puoi suddividere questi due tipi in tipi di JSON:
Questa grammatica va bene per l'analisi del JSON regolare, ma necessita di un po' di ritocco per il nostro caso. Dal momento che supporteremo le stringhe senza virgolette, il che significa "1,5" (senza virgolette) è un numero, ma "1,5x" (di nuovo, senza virgolette), è una stringa. La nostra grammatica attuale leggerebbe "1.5" da "1.5x" e quindi causerebbe un errore perché "x" non era previsto dopo un numero.
Ciò significa che prima dovremo ottenere il set completo di caratteri non quotati. Successivamente, analizzeremo i caratteri e determineremo se si tratta di un numero o di una stringa. Quindi, combineremo numeri e stringhe non quotate in un'unica categoria, "Non quotate". Le stringhe tra virgolette vanno bene, quindi le separeremo in un'altra categoria, "QuotedString". La nostra regola di produzione modificata per "PrimitiveType" ora è simile a questa:
Inoltre, l'ordine delle regole è importante. Dato che abbiamo chiavi senza virgolette, dobbiamo prima provare ad analizzare il testo come null o booleano. Altrimenti, potremmo finire per riconoscere "null" o "true" come una stringa senza virgolette.
Implementazione del parser e gestione dei commenti
Per implementare il parser JSON, inizieremo estendendo la classe del parser di base in questo modo:
class JSONParser(Parser): # ...
Affronteremo innanzitutto il problema della gestione dei commenti. Se ci pensi, i commenti sono davvero simili agli spazi bianchi:si verificano negli stessi punti in cui possono verificarsi spazi bianchi e possono essere scartati proprio come gli spazi bianchi. Quindi, reintempleremo eat_whitespace() per gestire i commenti, in questo modo:
def eat_whitespace(self):
is_processing_comment = False
while self.pos < self.len:
char = self.text[self.pos + 1]
if is_processing_comment:
if char == 'n':
is_processing_comment = False
else:
if char == '#':
is_processing_comment = True
elif char not in ' fvrtn':
break
self.pos += 1
Qui, dobbiamo tenere traccia se stiamo elaborando spazi bianchi o un commento. Eseguiamo il ciclo del testo carattere per carattere, controllando se abbiamo spazi bianchi o un # . Quando c'è un # , aggiorniamo is_processing_comment a True e nelle successive iterazioni del while loop, possiamo tranquillamente scartare tutti i caratteri fino a raggiungere la fine della riga. Tuttavia, quando si elaborano caratteri di spazi bianchi, è necessario interrompere quando viene visualizzato un carattere diverso da spazi bianchi.
Successivamente, implementeremo le regole di produzione e il start() metodo. Il testo di input conterrà un tipo JSON, quindi chiameremo semplicemente any_type() nel start() metodo:
def start(self):
return self.match('any_type')
def any_type(self):
return self.match('complex_type', 'primitive_type')
def primitive_type(self):
return self.match('null', 'boolean', 'quoted_string', 'unquoted')
def complex_type(self):
return self.match('list', 'map')
Analisi di elenchi e mappe
In precedenza, abbiamo visto come analizzare elenchi separati da virgole. Gli elenchi di JSON sono solo un elenco separato da virgole con parentesi quadre aggiunte su di essi e l'elenco potrebbe avere zero o più elementi. Vediamo come implementeresti l'analisi di un elenco:
def list(self):
rv = []
self.keyword('[')
while True:
item = self.maybe_match('any_type')
if item is None:
break
rv.append(item)
if not self.maybe_keyword(','):
break
self.keyword(']')
return rv
Iniziamo leggendo la parentesi quadra iniziale seguita da un elemento dell'elenco utilizzando self.maybe_match('any_type') . Se non siamo riusciti a ottenere un articolo, ciò indica che probabilmente abbiamo finito di esaminare tutti gli articoli, quindi usciamo dal ciclo. In caso contrario, aggiungiamo l'elemento all'elenco. Proviamo quindi a leggere una virgola dall'elenco e l'assenza di una virgola indica anche che l'elenco è terminato.
Allo stesso modo, le mappe sono solo elenchi separati da virgole di "coppie" con parentesi graffe, dove una coppia è una chiave stringa seguita da due punti(:) e un valore. A differenza di dict di Python s che può avere qualsiasi tipo "hashable" come chiave (che include int se tuple s), JSON supporta solo chiavi stringa.
Ecco come implementeresti le regole per mappe e coppie:
def map(self):
rv = {}
self.keyword('{')
while True:
item = self.maybe_match('pair')
if item is None:
break
rv[item[0]] = item[1]
if not self.maybe_keyword(','):
break
self.keyword('}')
return rv
def pair(self):
key = self.match('quoted_string', 'unquoted')
if type(key) is not str:
raise ParseError(
self.pos + 1,
'Expected string but got number',
self.text[self.pos + 1]
)
self.keyword(':')
value = self.match('any_type')
return key, value
In pair() , proviamo a leggere un "QuotedString" o "Unquoted" per la chiave. Come accennato in precedenza, "Unquoted" può restituire un numero o una stringa, quindi controlliamo esplicitamente se la chiave che abbiamo letto è una stringa. pair() quindi restituisce una tupla con una chiave e un valore e map() chiama pair() e li aggiunge a un dict Python.
Riconoscimento nullo e booleano
Ora che le parti principali del nostro parser sono state implementate, iniziamo riconoscendo semplici token come null e booleani:
def null(self):
self.keyword('null')
return None
def boolean(self):
boolean = self.keyword('true', 'false')
return boolean[0] == 't'
None di Python è l'analogo più vicino al null di JSON . In the case of booleans, the first characters is sufficient to tell whether it’s true or false , and we return the result of the comparison.
Recognizing unquoted strings and numbers
Before moving on to recognize unquoted strings, let us first define the set of acceptable characters. We’ll leave out anything that’s considered special in such as braces, quotes, colons, hashes (since they are used in comments) and backslashes (because they’re used for escape sequences). We’ll also include spaces and tabs in the acceptable set of characters so that you can write strings like “Things to buy” without using quotes.
So, what are the characters that we want to accept? We can use Python to figure this out:
>>> import string
>>> ''.join(sorted(set(string.printable) - set('{}[]:#"'fvrn')))
't !$%&()*+,-./0123456789;<=>[email protected]^_`abcdefghijklmnopqrstuvwxyz|~'
The next question is, how do you figure out if the text you read is a number or a string? The answer is — we cheat! Since Python’s int() and float() can take a string and return a number, we’ll use them and if those result in a ValueError , we’ll return a string. As for when to use int() or float() , we’ll use a simple rule. If the text contains “E”, “e” or “.”, (for example, “12.3” or “2e10”), we’ll call float(); otherwise, we’ll use int() .
Here’s the code:
def unquoted(self):
acceptable_chars = '0-9A-Za-z t!$%&()*+./;<=>?^_`|~-'
number_type = int
chars = [self.char(acceptable_chars)]
while True:
char = self.maybe_char(acceptable_chars)
if char is None:
break
if char in 'Ee.':
number_type = float
chars.append(char)
rv = ''.join(chars).rstrip(' t')
try:
return number_type(rv)
except ValueError:
return rv
Since matching rules are handled by match() , this takes care of stripping any initial whitespace before unquoted() can run. In this way, we can be sure that unquoted() won’t return a string consisting of only whitespaces. Any whitespace at the end is stripped off before we parse it as a number or return the string itself.
Recognizing quoted strings
Quoted strings are fairly simple to implement. Most programming languages (including Python) have single and double quotes that behave in the same way, and we’ll implement both of them.
We’ll support the following escape sequences — b (backspace), f (line feed), n (newline), r (carriage return), t (tab) and u(four hexadecimal digits) where those digits are used to represent an Unicode “code point”. For anything else that has a backslash followed by a character, we’ll ignore the backslash. This handles cases like using the backslash to escape itself ( ) or escaping quotes (" ).
Here’s the code for it:
def quoted_string(self):
quote = self.char('"'')
chars = []
escape_sequences = {
'b': 'b',
'f': 'f',
'n': 'n',
'r': 'r',
't': 't'
}
while True:
char = self.char()
if char == quote:
break
elif char == '':
escape = self.char()
if escape == 'u':
code_point = []
for i in range(4):
code_point.append(self.char('0-9a-fA-F'))
chars.append(chr(int(''.join(code_point), 16)))
else:
chars.append(escape_sequences.get(char, char))
else:
chars.append(char)
return ''.join(chars)
We first read a quote and then read additional characters in a loop. If this character is the same type of quote as the first character we read, we can stop reading further and return a string by joining the elements of chars .
Otherwise, we check if it’s an escape sequence and handle it in the aforementioned way, and add it to chars . Finally, if it matches neither of them, we treat it as a regular character and add it to our list of characters.
An interface for our JSON parser
To make sure we can interact with our parser, we’ll add a few lines of code that accepts input and parses it as JSON. Again, this code will be in global scope:
if __name__ == '__main__':
import sys
from pprint import pprint
parser = JSONParser()
try:
pprint(parser.parse(sys.stdin.read()))
except ParseError as e:
print('Error: '+ str(e))
To ensure we can read multiple lines, we have used sys.stdin.read() . If you’re going to run this locally, you can enter text and use Ctrl+D to stop the program from asking for more input. Otherwise, you can use this runnable snippet:
You can find the complete code here.
Building other kinds of parsers
Now that we’ve gone through building two parsers, you might have a fairly good idea of how to roll your own for the task at hand. While every language is unique (and therefore, their parsers), there are some common situations that we haven’t covered. For the sake of brevity, we won’t cover any code in these sections.
Whitespace sensitive languages
Before we begin, let us clarify that we’re not referring to languages that use whitespace-based indentation — we’ll cover them in the next section. Here, we’ll discuss languages where the meaning of things change based on the whitespace you put between elements.
An example of such a language would be where “a=10” is different than “a =10”. With bash and some other shells, “a=10” sets an environment variable, whereas “a =10” runs the program “a” with “=” and “10” as command-line arguments. You can even combine the two! Consider this:
a=10 b=20 c = 30
This sets the environment variables “a” and “b” only for the program “c”. The only way to parse such a language is to handle the whitespaces manually, and you’d have to remove all the eat_whitespace() calls in keyword() and match() . This is how you might write the production rules:
Whitespace based indentation
Languages like C and Javascript use curly braces to indicate the body of loops and if-statements. However, Python uses indentation for the same purpose, which makes parsing tricky.
One of the methods to handle this is to introduce a term such as “INDENT” to keep track of indented statements. To see how this would work, consider the following production rule:
After matching a condition, our parser would look for INDENT. Since this is the first time it’s trying to match INDENT, it takes whatever whitespace (except for newlines) that appears along with a non-whitespace character (since that would be part of a statement).
In subsequent iterations, it looks for the same whitespace in the text. If it encounters a different whitespace, it can raise an error. However, if there’s no whitespace at all, it indicates that the “while” loop is finished.
For nested indentations, you’d need to maintain a list of all indentations that you’re currently handling. When the parser handles a new indented block, it should add the new indentation string on the list. You can tell if you’re done parsing the block, by checking that you were able to retrieve less whitespace than you did previously. At this point, you should pop off the last indentation off the list.