Analyzátory jsou programy, které pomáhají zpracovávat text. Kompilátory a interpreti používají analyzátory k analýze programů před jejich dalším zpracováním a analyzátory pro formáty jako JSON a YAML zpracovávají text do nativních datových struktur programovacího jazyka.
V tomto článku se podíváme na to, jak vytvořit „rekurzivní analyzátory sestupu“. Rekurzivní sestupné analyzátory představují jednoduchý, ale výkonný způsob vytváření analyzátorů – pro každou „entitu“ v textu, který chcete zpracovat, definujete funkci.
Nejprve se podíváme na některé teorie, které jsou základem analýzy. Potom pomocí Pythonu vytvoříme kalkulačku a analyzátor JSON, který podporuje komentáře, koncové čárky a řetězce bez uvozovek. Nakonec probereme, jak můžete vytvořit analyzátory pro jiné druhy jazyků, které se chovají jinak než výše uvedené příklady.
Pokud jste již obeznámeni s teorií, můžete přímo přeskočit na části, ve kterých sestavujeme analyzátor.
Obsah
- 1 Jak funguje analýza?
- 2 Psaní produkčních pravidel
- 3 úvahy při vytváření analyzátorů
- 3.1 Manipulace s prioritou v gramatikách
- 3.2 Vyhnutí se rekurzi doleva
- 3.3 Vyhýbání se zpětnému sledování
- 4 Vytváření základny pro rekurzivní sestupný analyzátor v Pythonu
- 4.1 Třída výjimky
- 4.2 Základní třída Parser
- 4.3 Zpracování rozsahů znaků
- 4.4 Extrahování znaků z textu
- 4.5 Extrahování klíčových slov a symbolů
- 4.6 Pomocník pro párování více produkcí
- 4.7 Pohled dopředu na to, co bude dál – pomocné funkce
- 5 První příklad analyzátoru:kalkulačka
- 5.1 Produkční pravidla pro gramatiku kalkulačky
- 5.2 Implementace analyzátoru
- 5.3 Rozpoznávání čísel
- 5.4 Rozhraní pro náš analyzátor
- 6 Druhý příklad analyzátoru:„rozšířený“ analyzátor JSON
- 6.1 Produkční pravidla pro gramatiku JSON
- 6.2 Implementace analyzátoru a řešení komentářů
- 6.3 Analýza seznamů a map
- 6.4 Rozpoznávání null a boolean
- 6.5 Rozpoznávání řetězců a čísel v uvozovkách
- 6.6 Rozpoznávání řetězců v uvozovkách
- 6.7 Rozhraní pro náš analyzátor JSON
- 7 Vytváření dalších druhů analyzátorů
- 7.1 Jazyky citlivé na mezery
- 7.2 Odsazení založené na mezerách
Jak funguje analýza?
Aby mohl program zpracovat kus textu, provádí tři úkoly. V procesu zvaném „lexing“ nebo „tokenizace“ program prochází znaky v textu a extrahuje logické skupiny nazývané „tokeny“. Například ve výrazu jako „3 + 5 – 10“ může program pro zpracování aritmetických výrazů extrahovat následující tokeny:
[{ "Type": "Number" , "Text": "3" },
{ "Type": "Operator", "Text": "+" },
{ "Type": "Number" , "Text": "5" },
{ "Type": "Operator", "Text": "-" },
{ "Type": "Number" , "Text": "10" }] Program pak používá pravidla k identifikaci smysluplných sekvencí tokenů a to se nazývá „parsing“. Pravidla, která se k tomu používají, se nazývají „gramatiky“ – podobně jako slova přirozeného jazyka, jako je angličtina, se spojují do smysluplných sekvencí pomocí anglické gramatiky. Jednotlivá pravidla gramatiky se nazývají „výroby“.
Představte si, že vytváříme program pro zpracování matematických výrazů a zajímá nás pouze sčítání a odčítání. Výraz musí obsahovat číslo (např. „3“), za nímž následuje libovolný počet operátorů a čísel (např. „+ 5“). Pravidlo analýzy lze zobrazit takto:
Označuje, že skupina se může opakovat libovolný počet opakování (včetně nuly).
Nakonec program provede sadu akcí pro gramatické pravidlo. Například po analýze by náš matematický program potřeboval vypočítat hodnotu výrazu.
Ačkoli jsme to popsali jako samostatné kroky, program může provést všechny najednou. Provedení všech kroků najednou přináší několik výhod a toto je přístup, kterým se v tomto článku podíváme.
Psaní produkčních pravidel
Ve zbytku tohoto článku budeme používat produkční pravidla k vizualizaci gramatik. Proto jsme v tomto článku vysvětlili, jak píšeme produkční pravidla. Pokud jste si dříve prošli učebnici analýzy, zápis, který jsme zde použili, je trochu jiný.
Již dříve jsme viděli příklad jednoduché výroby. Když gramatické pravidlo obsahuje název tokenu a token je poměrně jednoduchý, je běžné zapsat text tokenu do gramatiky. Pokud vezmeme v úvahu předchozí příklad, dává + nebo - , takže bychom mohli pravidlo přepsat takto:
Viděli jsme také, jak můžeme použít k označení toho, že se něco opakuje mnohokrát. Podobně a označuje, že se něco opakuje, ale mělo by k tomu dojít alespoň jednou. A označuje něco, co je volitelné.
Předpokládejme například, že vytváříme analyzátor pro zpracování seznamu podmínek, jako je „x> 10 a y> 30“. Předpokládejme, že and je volitelná, takže bychom tuto podmínku mohli přepsat jako „x> 10 y> 30“. Můžete navrhnout gramatiku pro výše uvedené takto:
Pokud existuje více alternativ, záleží na pořadí alternativ. U pravidla, jako je , bychom se měli nejprve pokusit najít shodu se „+“ a poté se „-“. Ačkoli by se v tomto triviálním příkladu mohlo zdát, že na pořadí nezáleží, uvidíme později příklady, kdy se pořadí stává důležitým.
A konečně, produkční pravidlo se zaměřuje pouze na tokeny a další gramatické symboly – ignoruje mezery a komentáře.
Úvahy při vytváření analyzátorů
Dříve jsme viděli několik jednoduchých gramatik. Při pokusu o analýzu něčeho složitějšího však může nastat řada problémů. Budeme o nich diskutovat zde.
Zacházení s prioritou v gramatikách
Dříve jsme viděli gramatiku, která zvládne matematický výraz sestávající ze sčítání a odčítání. Bohužel nemůžete rozšířit stejnou gramatiku pro násobení (a dělení), protože tyto operace mají vyšší prioritu než sčítání (a odčítání).
Abychom tento scénář zvládli, musíme naši gramatiku navrhnout tak, aby analyzátor odložil jakékoli sčítání, ale provedl násobení, jakmile na něj narazíme. Abychom toho dosáhli, rozdělili jsme gramatiku na dvě samostatná pravidla, jak je uvedeno níže:
Vezměme si výraz (například „3 + 2 * 5“), abychom se ujistili, že to opravdu funguje. Budeme předpokládat, že jakmile náš analyzátor dokončí shodu s gramatickým pravidlem, automaticky vypočítá výraz. K označení toho, co analyzátor hledá, použijeme také podtržený text. Kromě toho jsme pro přehlednost vynechali uvozovky.
Když 2 * 5 je analyzován, analyzátor okamžitě vrátí výsledek 10. Tento výsledek je přijat v kroku a přidání je provedeno na konci, výsledkem je 13.
Stručně řečeno, měli byste svá pravidla uspořádat tak, aby operátory s nejnižší prioritou byly nahoře, zatímco ty s nejvyšší prioritou byly dole.
Vyhnutí se levé rekurzi
Již dříve jsme zmínili, že rekurzivní sestupný analyzátor se skládá z funkcí, které zpracovávají „entity“ v textu. Nyní, když víme o tokenech a produkčních pravidlech, pojďme je předefinovat trochu formálněji:každá funkce v analyzátoru extrahuje token nebo implementuje logiku produkčního pravidla.
Vezměme si jednoduchou gramatiku, abychom viděli, co to skutečně znamená. Pokud byste napsali pseudokód pro tuto gramatiku, vypadal by asi takto:
def expression():
first_number = number()
read('+')
second_number = number()
# process these two numbers, e.g. adding them
Dále zvažte gramatiku, která analyzuje seznam čísel oddělených čárkami. Obecně byste to napsali jako:
Nyní si představte, že jste se z nějakého důvodu chtěli vyhnout zástupnému znaku a přepsat jej takto:
Tato gramatika je teoreticky správná — buď vybere jedno číslo z textu, nebo se rozšíří na seznam s číslem na konci. Druhý seznam se může rozšířit na další číslo nebo seznam, dokud analyzátor nedokončí text.
S tímto přístupem je však problém – vstoupili byste do nekonečné rekurze! Pokud se pokusíte zavolat na číslo list() jednou, nakonec ji zavoláte znovu a tak dále. Možná si myslíte, že přepsání gramatiky by mohlo pomoci. Pokud byste se však pokusili napsat funkci, přečetli byste jediné číslo a ukončili analýzu. Číslo, které čtete, může být součástí seznamu jako „2, 4, 6“ a ostatní čísla nebudete moci přečíst.
Při analýze se tomu říká levá rekurze. Případ, který jsme viděli výše, zahrnuje „přímou rekurzi doleva“, ale existuje také „nepřímá rekurze doleva“, kde A volá B, B volá A a tak dále. V obou případech byste měli přepsat gramatiku jiným způsobem, abyste se tomuto problému vyhnuli.
Vyhnout se zpětnému sledování
Předpokládejme, že se pokoušíte vytvořit analyzátor, který analyzuje operaci dvou čísel, například „2 + 4“, a píšete gramatiku tímto způsobem:
Tato gramatika je správná a také se bude chovat tak, jak očekáváte, a poskytne správné výsledky. Tato gramatika však není to, co byste chtěli používat.
Chcete-li zjistit, proč tomu tak je, zvažte vstupní řetězec „5 – 2“. Nejprve projdeme pravidlem sčítání a analyzujeme číslo. Pak bychom očekávali „+“, ale při čtení řetězce dostaneme „-“, což znamená, že musíme ustoupit a použít pravidlo odčítání. Tím jsme ztráceli čas a cykly CPU analýzou čísla, jen abychom je zahodili a znovu analyzovali jako součást pravidla odčítání.
Navíc při sestavování analyzátorů, které přímo pracují s datovými toky, jako je síťový soket, často není možné převinout stream. V tomto článku se budeme zabývat pouze analyzátory, které mají veškerý text v paměti. Přesto je dobrým zvykem vyhnout se couvání a za tímto účelem byste měli zohlednit společné části zleva. Takto by naše pravidlo vypadalo po faktoringu:
Krok faktoringu je dokončen a zabrání zpětnému sledování. Z estetických důvodů to však napíšeme jako:
Vytvoření základny pro rekurzivní sestupný analyzátor v Pythonu
Nyní, když jsme probrali různé úvahy pro analýzu, sestavíme kalkulačku a analyzátor JSON. Než to však uděláme, napíšeme základní třídu „Parser“, která má některé metody pro běžné funkce, jako je rozpoznávání znaků a zpracování chyb.
Tato část se může zdát příliš dlouhá, ale stojí za to trpělivost. Jakmile dokončíte tuto část, budete mít všechny nástroje k sestavení komplexních analyzátorů s velmi malým množstvím kódu potřebného k rozpoznání tokenů a implementaci produkčních pravidel.
Třída výjimky
Vzhledem k tomu, že je to zdaleka nejjednodušší úkol, vyřešíme to jako první. Definujeme vlastní třídu výjimky s názvem ParseError takhle:
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)
Třída přijímá pozici textu, kde došlo k chybě, chybovou zprávu (jako formátovací řetězec) a argumenty formátovacího řetězce. Podívejme se, jak můžete použít tento typ výjimky:
e = ParseError(13, 'Expected "{" but found "%s"', "[") Když se pokusíte vytisknout výjimku, zobrazí se zpráva ve formátu:
Expected "{" but found "[" at position 13
Všimněte si, že jsme nepoužili % symbol ve formátovacím řetězci a jeho argumenty (například '"Expected "{" but found "%s"' % "[" ). Toto je řešeno v __str__ metoda třídy, kde jsme naformátovali self.msg s prvky v self.pos .
Nyní se můžete zeptat, proč jej chceme formátovat v __str__ namísto psaní pomocí % ? Ukázalo se, že pomocí % formátování řetězce zabere poměrně dost času. Při analýze řetězce se objeví mnoho výjimek, protože se analyzátor pokouší aplikovat různá pravidla. Proto jsme formátování řetězce odložili na dobu, kdy je skutečně potřeba.
Základní třída analyzátoru
Nyní, když máme zavedenou třídu chyb, je dalším krokem zápis třídy analyzátoru. Definujeme to následovně:
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
Zde si všimnete cache členem v __init__ metoda — k tomu, proč je to potřeba, se vrátíme, až budeme diskutovat o rozpoznávání znaků.
parse metoda je poměrně jednoduchá — nejprve uloží řetězec. Protože jsme ještě nenaskenovali žádnou část řetězce, nastavíme pozici na -1. Také uložíme maximální index řetězce v self.len . (Maximální index je vždy o jeden menší než délka řetězce.)
Dále začneme analyzovat řetězec a zkontrolujeme, zda jsme dosáhli konce řetězce. To má zajistit, že náš analyzátor byl schopen zpracovat celý text, aniž by na konci něco zůstalo. Poté vrátíme výsledek.
assert_end metoda je jednoduchá:zkontrolujeme, zda je aktuální pozice nižší než maximální index. Mějte na paměti, že tyto metody jsou uvnitř třídy, i když jsme pro zjednodušení vynechali odsazení.
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]
)
V celém našem analyzátoru se budeme dívat na znak, který je o jeden větší než aktuální index (self.pos ). Chcete-li zjistit, proč tomu tak je, zvažte, že začínáme s self.pos = -1 , takže bychom se dívali na index 0. Jakmile úspěšně rozpoznáme znak, self.pos přejde na 0 a podíváme se na znak na indexu 1 a tak dále. To je důvod, proč chyba používá self.pos + 1 .
U většiny jazyků lze mezery mezi tokeny bezpečně zahodit. Proto se zdá logické zahrnout metodu, která zkontroluje, zda je další znak prázdný znak, a pokud ano, „zahodí“ jej postupem na další pozici.
def eat_whitespace(self):
while self.pos < self.len and self.text[self.pos + 1] in " fvrtn":
self.pos += 1
Zpracování rozsahů znaků
Nyní napíšeme funkci, která nám pomůže rozpoznat znaky v textu. Než to však uděláme, zvážíme naši funkci z pohledu uživatele – dáme jí sadu znaků, které budou odpovídat textu. Pokud byste například chtěli rozpoznat abecedu nebo podtržítko, můžete napsat něco jako:
self.char('A-Za-z_')
Dáme char metoda obsahující seznam znaků nebo rozsahů (například A-Z ve výše uvedeném příkladu). Rozsahy jsou označeny dvěma znaky oddělenými - . První znak má číselně menší hodnotu než ten vpravo.
Nyní, pokud je znak na self.text[self.pos + 1] odpovídá něčemu v argumentu self.char , vrátíme. V opačném případě vyhlásíme výjimku.
Interně řetězec zpracujeme na něco, s čím se lépe manipuluje – na seznam se samostatnými znaky nebo rozsahy, jako je ['A-Z', 'a-z', '_'] . Napíšeme tedy funkci pro rozdělení rozsahů:
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
Zde procházíme chars řetězec, který hledá - následuje další postava. Pokud tato podmínka odpovídá a první znak je menší než poslední, přidáme celý rozsah (např. A-Z ) do seznamu rv . V opačném případě přidáme znak na chars[index] na rv .
Poté přidáme seznam v rv to do mezipaměti. Pokud tento řetězec uvidíme podruhé, vrátíme jej z mezipaměti pomocí try ... except KeyError: ... blok nahoře.
Je pravda, že jsme mohli poskytnout seznam jako ['A-Z', 'a-z', '_'] na char metoda. Nicméně, podle našeho názoru, když to uděláte tímto způsobem, volá se char() vypadat trochu čistěji.
Extrahování znaků z textu
Nyní, když máme metodu, která poskytuje seznam obsahující rozsahy a znaky, můžeme napsat naši funkci pro extrahování znaku z textu. Zde je kód pro char metoda:
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
)
Nejprve se zaměřme na argument chars=None . To vám umožní volat self.char() aniž bychom mu dali sadu znaků. To je užitečné, když chcete jednoduše extrahovat znak, aniž byste jej omezovali na konkrétní sadu. V opačném případě jej můžete volat s řadou znaků, jak jsme viděli v předchozí části.
Tato funkce je poměrně přímočará – nejprve zkontrolujeme, zda nám nedošel text. Poté vybereme další znak a zkontrolujeme, zda jsou znaky None , v takovém případě můžeme zvýšit pozici a okamžitě vrátit znak.
Pokud však v chars existuje sada znaků , rozdělíme jej na seznam jednotlivých znaků a rozsahů, například ['A-Z', 'a-z', '_'] . V tomto seznamu je řetězec délky 1 znak a cokoliv jiného je rozsah. Zkontroluje, zda se další znak shoduje se znakem nebo rozsahem, a pokud ano, vrátíme jej. Pokud se nám nepodaří jej porovnávat s ničím, opustí smyčku, která vyvolá ParseError , s tím, že se nám nepodařilo získat očekávanou postavu.
'character' if chars is None else '[%s]' % chars je jen způsob, jak poskytnout čitelnější výjimku. Pokud chars je None , bude zpráva výjimky znít Expected character but got ... , ale pokud char byl nastaven na něco jako A-Za-z_ , dostali bychom Expected [A-Za-z_] but got ... .
Později uvidíme, jak tuto funkci použít k rozpoznání tokenů.
Extrahování klíčových slov a symbolů
Kromě extrahování jednotlivých znaků je při sestavování parseru běžným úkolem rozpoznávání klíčových slov. „Klíčová slova“ používáme k volnému odkazování na jakýkoli souvislý řetězec, který je „vlastní entitou“ a může mít před a za sebou mezery. Například v JSON { může být klíčové slovo a v programovacím jazyce if , else může být klíčové slovo a tak dále.
Toto je kód pro rozpoznávání klíčových slov:
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],
)
Tato metoda používá klíčová slova, například self.keyword('if', 'and', 'or') . Metoda odstraní mezery a poté zkontroluje, zda nám nedošel text k analýze. Poté prochází každé klíčové slovo a kontroluje, zda klíčové slovo v textu existuje. Pokud něco najde, odstraníme mezery za klíčovým slovem a vrátíme klíčové slovo.
Pokud však něco nenajde, opustí smyčku, která vyvolá ParseError s tím, že klíčová slova nebyla nalezena.
Pomocník pro párování více produkcí
V předchozích částech jste si všimli, že k hlášení chyb používáme výjimky. Víme také, že pro psaní rekurzivního sestupného analyzátoru píšete funkce, které rozpoznávají token nebo produkční pravidlo. Nyní si představte, že byste chtěli analyzovat jednoduchý text, kde očekáváte číslo nebo slovo. Produkční pravidlo může vypadat takto:
Budeme také předpokládat, že text obsahuje slovo. Když se analyzátor pokusí vyhledat číslici (možná pomocí char() ), nenajde to, a to způsobí, že vyvolá výjimku. Kromě toho musíte odstranit mezery před a po splnění produkčního pravidla. Takže kód pro item() může vypadat takto:
def item(self): self.eat_whitespace() try: rv = self.number() except ParseError: rv = self.word() self.eat_whitespace() return rv
To už vypadá na implementaci jednoduchého pravidla hodně! Představte si, jaké by to bylo implementovat složité pravidlo – museli byste použít try...except bloky všude.
Napíšeme tedy match() funkce, která odstraní mezery a pokusí se vyhovět více pravidlům. Funkce je následující:
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]
)
Než probereme, jak to funguje, podívejme se, jak jednoduché je přepsat náš předchozí příklad pomocí match() :
def item(self):
return self.match('number', 'word')
Jak to tedy funguje? match() přebírá název metody ke spuštění (například number nebo word ve výše uvedeném příkladu). Nejprve se zbaví mezer na začátku. Poté iteruje všechny názvy metod a načte každou metodu pomocí jejího názvu přes getattr() . Poté se pokusí vyvolat metodu, a pokud vše půjde dobře, odstraní i mezery za textem. Nakonec vrátí hodnotu, kterou obdržel voláním metody
Pokud však dojde k chybě, resetuje self.pos na hodnotu, která tam byla před pokusem o shodu pravidla. Potom se pokusí vybrat správnou chybovou zprávu pomocí následujících pravidel:
- Při porovnávání více pravidel může mnoho z nich způsobit chybu. Chyba, která byla vygenerována po analýze většiny textu, je pravděpodobně chybová zpráva, kterou chceme.
Chcete-li zjistit, proč tomu tak je, zvažte řetězec „abc1“. Pokus o volání number() by selhal na pozici 0, zatímco word() selže na pozici 2. Při pohledu na řetězec je docela pravděpodobné, že uživatel chtěl zadat slovo, ale udělal překlep.
- Pokud dvě nebo více chybných pravidel skončí nerozhodně, raději informujeme uživatele o všech pravidlech, která selhala.
last_error_pos a last_exception sleduje polohu poslední chyby a výjimku. Kromě toho udržujeme seznam last_error_rules abychom v případě nerozhodného výsledku mohli uživatele informovat o všech pravidlech, která jsme se snažili najít.
V except ParseError bloku, porovnáme pozici poslední chyby a aktuální chybu. Pokud je aktuální chyba stejná, považujeme to za nerozhodné a připojíme k seznamu. V opačném případě aktualizujeme chybovou pozici, výjimku a seznam chybných pravidel.
Nakonec zkontrolujeme, kolik pravidel selhalo. Pokud existuje pouze jeden, last_exception bude mít nejlepší chybovou zprávu. V opačném případě je to nerozhodné a my o tom uživatele informujeme zprávou jako Expected number,word but found ... .
Pohled dopředu na to, co bude dál – pomocné funkce
V tomto okamžiku máme všechny potřebné věci v našem analyzátoru a všechna selhání vyvolávají výjimky. Někdy však chceme přiřadit znak, klíčové slovo nebo pravidlo pouze tehdy, pokud existují, aniž bychom museli obtěžovat zpracováním výjimek.
K tomu vám představíme tři malé pomocníky. V případě výjimky při hledání věcí vrátí 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
Použití těchto funkcí je snadné. Můžete je použít takto:
operator = self.maybe_keyword('+', '-'):
if operator == '+':
# add two numbers
elif operator == '-':
# subtract two numbers
else: # operator is None
# do something else
Příklad prvního analyzátoru:kalkulačka
Nyní, když jsme vytvořili základy pro psaní analyzátoru, vytvoříme náš první analyzátor. Bude schopen analyzovat matematické výrazy pomocí sčítání, odčítání, násobení, dělení a také zpracovávat výrazy v závorkách jako „(2 + 3) * 5“.
Začneme vizualizací gramatiky ve formě produkčních pravidel.
Produkční pravidla pro gramatiku kalkulačky
Již dříve jsme viděli gramatiku, která zvládne vše kromě výrazů v závorkách:
Nyní se zamysleme nad tím, jak do této gramatiky zapadají výrazy v závorkách. Při vyhodnocení „(2 + 3) * 5“ bychom museli vypočítat „(2 + 3)“ a zmenšit ho na číslo. Což znamená, že ve výše uvedené gramatice může výraz „číslo“ odkazovat buď na výraz v závorkách, nebo na něco, co je ve skutečnosti číslo, například „5“.
Upravíme tedy naše pravidla tak, aby vyhovovala oběma. V pravidle pro „Termín“ nahradíme „Číslo“ vhodnějším výrazem, jako je „Faktor“. „Faktor“ pak může odkazovat buď na výraz v závorkách, nebo na „Číslo“. Upravená gramatika vypadá takto:
Když to bude pryč, pojďme implementovat produkční pravidla!
Implementace analyzátoru
Implementujeme náš analyzátor Calculator rozšířením základní třídy analyzátoru. Začneme definovat třídu takto:
class CalcParser(Parser):
def start(self):
return self.expression()
Dříve, když jsme implementovali základní třídu analyzátoru, měli jsme start() způsob zahájení analýzy. Budeme jednoduše volat expression() metodu zde, kterou definujeme následovně:
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
Gramatické pravidlo pro . Začneme tedy čtením termínu z textu. Poté nastavíme nekonečnou smyčku a hledáme „+“ nebo „-“. Pokud nenajdeme ani jeden, znamená to, že jsme dokončili čtení seznamu dalších výrazů podle , takže se můžeme vymanit ze smyčky.
Jinak z textu vyčteme jiný termín. Potom, v závislosti na operátoru, buď přičteme, nebo odečteme od počáteční hodnoty. Pokračujeme v tomto procesu, dokud se nám nepodaří získat „+“ nebo „-“ a vrátíme hodnotu na konci.
Implementujeme term() stejným způsobem:
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 Dále implementujeme „Factor“. Nejprve se pokusíme přečíst levou závorku, což znamená, že existuje výraz v závorce. Pokud závorku najdeme, přečteme výraz a koncovou závorku a vrátíme hodnotu výrazu. Jinak jednoduše přečteme a vrátíme číslo.
def factor(self):
if self.maybe_keyword('('):
rv = self.match('expression')
self.keyword(')')
return rv
return self.match('number')
V další části přimějeme náš analyzátor rozpoznat číslo.
Rozpoznávání čísel
Abychom číslo rozeznali, musíme se podívat na jednotlivé znaky v našem textu. Čísla se skládají z jedné nebo více číslic, případně následovaných desetinnou částí. Desetinná část má tečku (.) a za ní následuje alespoň jedna číslice. Kromě toho mohou mít čísla před sebou znaménko jako „+“ nebo „-“, například „-124,33“.
Implementujeme number() metoda takto:
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
Přestože je funkce dlouhá, je poměrně jednoduchá. Máme chars seznam, do kterého vkládáme znaky čísla. Nejprve se podíváme na všechny symboly „+“ nebo „-“, které mohou být před číslem. Pokud je přítomen, přidáme jej do seznamu. Poté hledáme první povinnou číslici čísla a pokračujeme hledáním dalších číslic pomocí maybe_char() metoda. Jakmile dostaneme None až maybe_char , víme, že jsme za množinou číslic, a ukončíme cyklus.
Podobně hledáme desetinnou část a její číslice. Nakonec všechny znaky převedeme na řetězec, který zase převedeme na číslo s plovoucí desetinnou čárkou.
Rozhraní pro náš analyzátor
Dokončili jsme vytváření našeho analyzátoru. Jako poslední krok přidáme trochu kódu v globálním rozsahu, který nám umožní zadávat výrazy a zobrazovat výsledky:
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)
Pokud jste to sledovali až sem, gratulujeme! Vytvořili jste svůj první rekurzivní sestupový analyzátor!
Pokud sledujete v místním IDE, můžete v tomto okamžiku spustit svůj kód. Alternativně můžete ke spuštění analyzátoru použít hřiště níže. Výrazy můžete zadávat přes záložku „Input“ níže:
Úplný kód naleznete také zde.
Příklad druhého analyzátoru:„rozšířený“ analyzátor JSON
JSON je formát pro výměnu dat, který podporuje základní datové struktury, jako jsou čísla, řetězce a seznamy. Je to velmi široce používaný formát, i když jeho jednoduchost znamená, že postrádá věci, jako jsou komentáře, a přísný o věcech, které přijímá. Nemůžete například mít v seznamu koncovou čárku nebo mít před číslem explicitní „+“, které označuje jeho znaménko.
Vzhledem k tomu, že Python již modul JSON má, zamíříme o něco výš a vytvoříme analyzátor JSON, který podporuje komentáře, koncové čárky a řetězce bez uvozovek.
Implementace tohoto parseru vás naučí, jak zacházet s komentáři. Bude také ilustrovat, jak může vytvoření snadno použitelného jazyka zkomplikovat analýzu a jak se s takovými situacemi můžete vypořádat.
Než implementujeme naši gramatiku, podívejme se na náš rozšířený formát JSON:
{
# 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
} Produkční pravidla pro gramatiku JSON
Náš rozšířený JSON se drží stejných datových typů, které podporuje JSON. JSON má čtyři primitivní datové typy – null, booleans, čísla a řetězce a dva komplexní datové typy – seznamy (nebo pole) a mapy (také nazývané hash nebo slovníky). Seznamy a hash vypadají podobně jako v Pythonu.
Protože data JSON by se skládala z jednoho z těchto typů, můžete napsat produkční pravidla takto:
Poté můžete tyto dva typy rozdělit na typy JSON:
Tato gramatika je v pořádku pro analýzu běžného JSON, ale v našem případě potřebuje trochu doladit. Protože budeme podporovat řetězce bez uvozovek, což znamená, že „1,5“ (bez uvozovek) je číslo, ale „1,5x“ (opět bez uvozovek) je řetězec. Naše současná gramatika by přečetla „1,5“ z „1,5x“ a pak by způsobila chybu, protože „x“ nebylo po čísle očekáváno.
To znamená, že nejprve bychom museli získat celou sadu necitovaných znaků. Dále analyzujeme znaky a určíme, zda se jedná o číslo nebo řetězec. Čísla a řetězce bez uvozovek tedy sloučíme do jedné kategorie „Neuvozovky“. Řetězce v uvozovkách jsou v pořádku, takže je rozdělíme do jiné kategorie, „QuotedString“. Naše upravené produkční pravidlo pro „PrimitiveType“ nyní vypadá takto:
Kromě toho je důležité pořadí pravidel. Protože máme klíče v uvozovkách, musíme nejprve zkusit analyzovat text jako null nebo boolean. Jinak bychom mohli skončit rozpoznáním „null“ nebo „true“ jako neuvedený řetězec.
Implementace analyzátoru a řešení komentářů
Abychom implementovali analyzátor JSON, začneme rozšířením základní třídy analyzátoru takto:
class JSONParser(Parser): # ...
Nejprve se vypořádáme s problémem nakládání s připomínkami. Pokud se nad tím zamyslíte, komentáře jsou opravdu podobné mezerám – vyskytují se na stejných místech, kde se mohou vyskytovat mezery, a lze je zahodit stejně jako mezery. Takže znovu implementujeme eat_whitespace() vypořádat se s komentáři, jako takto:
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
Zde musíme sledovat, zda zpracováváme mezery nebo komentáře. Procházíme textem znak po znaku a kontrolujeme, zda máme mezery nebo # . Když je tam # , aktualizujeme is_processing_comment na True a v dalších iteracích while smyčky, můžeme klidně zahodit všechny znaky, dokud se nedostaneme na konec řádku. Při zpracovávání bílých znaků však musíme přestat, jakmile se objeví znak, který není prázdný.
Dále implementujeme produkční pravidla a start() metoda. Vstupní text bude mít typ JSON obsažený v něm, takže budeme jednoduše volat any_type() v start() metoda:
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')
Analýza seznamů a map
Dříve jsme viděli, jak analyzovat seznamy oddělené čárkami. Seznamy JSON jsou pouze seznamy oddělené čárkami s hranatými závorkami a seznam může obsahovat nula nebo více prvků. Podívejme se, jak byste implementovali analýzu seznamu:
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
Začneme odečtením počáteční hranaté závorky následované položkou ze seznamu pomocí self.maybe_match('any_type') . Pokud se nám nepodařilo získat položku, znamená to, že jsme pravděpodobně dokončili procházení všech položek, takže se vymaníme ze smyčky. V opačném případě přidáme položku do seznamu. Poté se pokusíme přečíst čárku ze seznamu a absence čárky také znamená, že jsme se seznamem skončili.
Podobně jsou mapy pouze čárkami oddělené seznamy „párů“ se složenými závorkami, kde dvojice je klíč řetězce následovaný dvojtečkou (:) a hodnotou. Na rozdíl od Pythonu dict s, které mohou mít jakýkoli „hašovatelný“ typ jako klíč (který zahrnuje int s a tuple s), JSON podporuje pouze řetězcové klíče.
Takto byste implementovali pravidla pro mapy a dvojice:
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
V pair() , snažíme se pro klíč přečíst „QuotedString“ nebo „Unquoted“. Jak jsme již zmínili, „Unquoted“ může vrátit číslo nebo řetězec, takže explicitně kontrolujeme, zda je klíč, který jsme přečetli, řetězec. pair() pak vrátí n-tici s klíčem a hodnotou a map() volá pair() a přidá je do pythonovského diktátu.
Rozpoznávání null a boolean
Nyní, když jsou implementovány hlavní části našeho analyzátoru, začněme rozpoznáním jednoduchých tokenů, jako je null a booleans:
def null(self):
self.keyword('null')
return None
def boolean(self):
boolean = self.keyword('true', 'false')
return boolean[0] == 't'
None Pythonu je nejbližším analogem JSON null . 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.