Software is all about logic. Programování získalo pověst pole, které je těžké na matematiku a bláznivé rovnice. A počítačová věda se zdá být jádrem této mylné představy.

jistě, existuje nějaká matematika a existují nějaké vzorce – ale nikdo z nás ve skutečnosti nemusí mít PhD v počtu, abychom pochopili, jak naše stroje fungují! Ve skutečnosti, mnoho pravidel a paradigmat, které se učíme v procesu psaní kódu, jsou stejná pravidla a paradigmata, která platí pro složité koncepty informatiky. A někdy, tyto myšlenky skutečně pocházejí z informatiky, a my jsme to nikdy nevěděli.

bez Ohledu na to, jaký programovací jazyk použijeme, když většina z nás psát náš kód, naším cílem je zapouzdřit odlišné věci do tříd, objektů, či metod, záměrně odděluje, co různé části našeho kodexu se zabývá. Jinými slovy, víme, že to je obecně dobré věci rozdělit náš kód tak, že jedna třída, objekt, nebo metoda se zabývá pouze a zodpovědný za jednu jedinou věc. Kdybychom to neudělali, mohlo by to být super chaotické a propletené do nepořádku webu. Někdy se to stále děje, dokonce i s oddělením obav.

Jak se ukazuje, i vnitřní fungování našich počítačů se řídí velmi podobnými paradigmaty designu. Náš kompilátor má například různé části a každá část je zodpovědná za zpracování jedné konkrétní části procesu kompilace. Trochu jsme se s tím setkali minulý týden, když jsme se dozvěděli o analyzátoru, který je zodpovědný za vytváření parsových stromů. Ale analyzátor nemůže mít za úkol všechno.

analyzátor potřebuje pomoc od svých kamarádů a konečně je čas, abychom se dozvěděli, kdo jsou!

Když jsme se nedávno dozvěděli o analýze, ponořili jsme prsty do gramatiky, syntaxe a toho, jak kompilátor reaguje a reaguje na tyto věci v programovacím jazyce. Ale nikdy jsme opravdu zdůraznili, co přesně kompilátor je! Jak se dostaneme do vnitřního fungování procesu kompilace, budeme se hodně učit o návrhu kompilátoru, takže je důležité, abychom pochopili, o čem přesně zde mluvíme.

kompilátory mohou znít trochu děsivě — ale jejich práce ve skutečnosti nejsou příliš složité na pochopení-zvláště když rozdělíme různé části kompilátoru na části o velikosti kousnutí.

ale nejprve začněme s nejjednodušší možnou definicí. Kompilátor je program, který čte náš kód (nebo jakýkoli kód v jakémkoli programovacím jazyce) a překládá jej do jiného jazyka.

obecně lze říci, že kompilátor bude překládat kód z jazyka vysoké úrovně do jazyka nižší úrovně. Jazyky nižší úrovně, do kterých kompilátor překládá kód, se často označují jako kód sestavy, strojový kód nebo objektový kód. Za zmínku stojí, že většina programátorů nejsou ve skutečnosti zabývají nebo psaní strojového kódu; spíše, jsme závislí na kompilátoru, aby se naše programy a přeložit do strojového kódu, což je to, co náš počítač bude běžet jako spustitelný program.

kompilátory můžeme považovat za prostředníka mezi námi, programátory a našimi počítači, který může spouštět spustitelné programy pouze v jazycích nižší úrovně.

kompilátor dělá práci překládám, co chceme, aby se stalo způsobem, který je srozumitelný a spustitelný tím, že naše stroje.

Bez kompilátor, budeme nuceni komunikovat s našich počítačích psaní strojového kódu, který je neuvěřitelně nečitelné a těžko dešifrovat. Strojový kód může často vypadat jako banda 0 a 1 pro lidské oko — je to všechno binární, pamatuješ? – což je velmi těžké číst, psát a ladit. Kompilátor abstrahuje pryč strojového kódu pro nás jako programátory, protože to dělal to velmi snadné pro nás ani přemýšlet o strojový kód a psát programy pomocí daleko více elegantní, jasné a snadno-až k-číst jazyků.

budeme pokračovat v rozbalování stále více a více o tajemném kompilátoru v příštích několika týdnech, což doufejme, že v tomto procesu bude méně záhadou. Ale prozatím se vraťme k otázce: jaké jsou nejjednodušší možné části kompilátoru?

každý kompilátor, bez ohledu na to, jak by mohl být navržen, má odlišné fáze. Tyto fáze jsou, jak můžeme rozlišit jedinečné části kompilátoru.

už Jsme se setkali s jedním z fází v naší kompilace dobrodružství, když jsme se nedávno dozvěděli o parser a derivační stromy. Víme, že syntaktická analýza je proces, kdy některé vstupní a budování derivační strom, který je někdy označován jako zákon rozebrat. Jak se ukazuje, práce parsování je specifická pro fázi procesu kompilace zvanou syntaktická analýza.

analyzátor však nevytváří pouze strom analýzy z tenkého vzduchu. Má nějakou pomoc! Připomeňme si, že analyzátor dostane nějaké žetony (nazývané také terminály) a z těchto tokenů vytvoří strom analýzy. Ale odkud bere ty žetony? Naštěstí pro analyzátor nemusí pracovat ve vakuu; místo toho má nějakou pomoc.

to nás přivádí do další fáze procesu kompilace, která přichází před fází analýzy syntaxe: fáze lexikální analýzy.

termín „lexikální“ odkazuje na význam slova v izolaci od věty, které ho obsahují, a to bez ohledu na jeho gramatické souvislosti. Pokud se budeme snažit odhadnout vlastní význam založena pouze na tuto definici, můžeme předpokládat, že lexikální analýza fáze má co do činění s jednotlivými slovy/výrazy v programu sami, a nemá nic společného s gramatikou, nebo význam věty, který obsahuje slova.

fáze lexikální analýzy je prvním krokem v procesu kompilace. Nezná ani se nestará o gramatiku věty nebo význam textu nebo programu; vše, o čem ví, je význam samotných slov.

lexikální analýza musí proběhnout dříve, než bude možné analyzovat jakýkoli kód ze zdrojového programu. Než jej analyzátor může přečíst, musí být program nejprve naskenován, rozdělen a seskupen určitými způsoby.

Když jsme začali při pohledu na syntaxi analytické fáze minulý týden jsme se dozvěděli, že derivační strom je postaven při pohledu na jednotlivé části věty a poškodí výrazy na jednodušší části. Ale během fáze lexikální analýzy kompilátor nezná nebo nemá přístup k těmto „jednotlivým částem“. Spíše je musí nejprve identifikovat a najít, a pak dělat práci rozdělení textu na jednotlivé kusy.

například, když čteme větu ze Shakespeara jako To sleep, perchance to dream. víme, že mezery a interpunkce jsou rozdělení na „slova“ věty. To je, samozřejmě, protože jsme byli vyškoleni, abychom četli větu, “ lex “ to, a analyzovat to pro gramatiku.

ale pro kompilátor může stejná věta vypadat takto Při prvním přečtení: Tosleepperhachancetodream. Když čteme tuto větu, je pro nás trochu těžší určit, jaká jsou skutečná „slova“! Jsem si jistý, že náš kompilátor to cítí stejně.

tak, jak se náš stroj vypořádat s tímto problémem? Během fáze lexikální analýzy kompilačního procesu vždy dělá dvě důležité věci: naskenuje kód a poté jej vyhodnotí.

práce skenování a vyhodnocování může být někdy spojovány do jednoho jediného programu, nebo by to mohly být dva samostatné programy, které na sobě vzájemně závisí; je to opravdu jen otázka, jak někdo complier se stalo, které mají být navrženy. Program v rámci kompilátor, který je zodpovědný za dělat práci, skenování a vyhodnocování je často odkazoval se na jako lexer nebo tokenizer, a celý lexikální analýza fáze se někdy nazývá proces lexing nebo tokenizing.

Chcete-li skenovat, snad číst

prvním ze dvou základních kroků lexikální analýzy je skenování. Skenování můžeme považovat za práci skutečně „čtení“ nějakého vstupního textu. Nezapomeňte, že tento vstupní text může být řetězec, věta, výraz nebo dokonce celý program! To opravdu nezáleží, protože v této fázi procesu, je to jen obří blob znaků, který nic neznamená, a je to jeden souvislý kus.

podívejme se na příklad, abychom zjistili, jak přesně se to děje. Použijeme naši původní větu, To sleep, perchance to dream., což je náš zdrojový text nebo zdrojový kód. Pro náš kompilátor bude tento zdrojový text čten jako vstupní text, který vypadá jako Tosleep,perchancetodream., což je jen řetězec znaků, který ještě nebyl dešifrován.

první věc, kterou musí náš kompilátor udělat, je rozdělit tuto blob textu na nejmenší možné části, což usnadní identifikaci toho, kde jsou slova v blobu textu.

nejjednodušší způsob, potápění se obří kus textu je tím, že čte pomalu a systematicky, jeden znak v čase. A to je přesně to, co kompilátor dělá.

často je proces skenování zpracován samostatným programem zvaným skener, jehož jediným úkolem je provádět práci čtení zdrojového souboru / textu, jeden znak najednou. Pro náš skener nezáleží na tom, jak velký je náš text; vše, co uvidí, když“ přečte “ náš soubor, je jeden znak najednou.

zde je to, co by naše Shakespearovská věta četla jako náš skener:

všimneme si, že To sleep, perchance to dream. byl náš skener rozdělen na jednotlivé znaky. Navíc i mezery mezi slovy jsou považovány za znaky, stejně jako interpunkce v naší větě. Na konci této sekvence je také znak, který je obzvláště zajímavý: eof. To je znak „konec souboru“, a to je podobné tabspacenewline. Od našeho zdrojového textu, je jen jedna jediná věta, kdy náš skener dostane na konec souboru (v tomto případě, na konci věty), čte do konce souboru a chová se to jako postava.

takže ve skutečnosti, když náš skener četl náš vstupní text, interpretoval jej jako jednotlivé znaky, což vedlo k tomuto: .

Nyní, když náš skener přečetl a rozdělil náš zdrojový text do nejmenších možných částí, bude mít mnohem snazší zjistit „slova“ v naší větě.

dále se skener musí podívat na své rozdělené znaky v pořadí a určit, které znaky jsou části slova a které ne. Pro každý znak, který skener čte, označuje řádek a pozici, kde byl tento znak nalezen ve zdrojovém textu.

zde zobrazený obrázek ilustruje tento proces pro naši shakespearovskou větu. Vidíme, že náš skener označuje řádek a sloupec pro každý znak v naší větě. Reprezentaci řádků a sloupců můžeme považovat za matici nebo pole znaků.

připomeňme, že protože náš soubor obsahuje pouze jeden jediný řádek, vše žije na řádku 0. Nicméně, jak se propracováváme větou, sloupec každého znaku se zvyšuje. Je to také stojí za zmínku, že, protože naše skener čte spacesnewlineseof, a všechny interpunkční znaky, ty se objeví v naší znak, tabulka, taky!

jakmile je zdrojový text naskenován a označen, náš kompilátor je připraven tyto znaky proměnit ve slova. Od skeneru ví, nejen kde spacesnewlineseof v souboru jsou, ale také, kde žijí, ve vztahu k jiné znaky, které je obklopují, je možné skenovat přes postavy, a rozdělit je do jednotlivých řetězců podle potřeby.

V našem příkladu, bude skener se podívat na znaky To a pak space. Když najde mezeru, rozdělí To do svého vlastního slova-nejjednodušší kombinace znaků, než skener narazí na mezeru.

je to podobný příběh pro další slovo, které najde, což je sleep. V tomto scénáři však přečte s-l-e-e-p a poté přečte ,, interpunkční znaménko. Protože tato čárka je lemovaný znak (p) a space na každé straně, čárka je, sám, považuje za „slovo“.

slovo sleep a interpunkční symbol , jsou tzv. lexémy, které jsou podřetězce zdroj textu. Lexém je seskupení nejmenších možných sekvencí znaků v našem zdrojovém kódu. Lexémy zdrojového souboru jsou považovány za jednotlivá „slova“ samotného souboru. Jakmile náš skener dokončí čtení jednotlivých znaků našeho souboru, vrátí sadu lexémů, které vypadají takto: .

Všimněte si, jak náš skener vzal jako svůj vstup blob textu, který nemohl zpočátku číst, a pokračoval ve skenování jednou znak najednou, současně čtení a označení obsahu. Poté pokračoval v rozdělení řetězce na jejich nejmenší možné lexémy pomocí mezer a interpunkce mezi znaky jako oddělovače.

nicméně, navzdory všem těmto pracím, v tomto okamžiku ve fázi lexikální analýzy náš skener o těchto slovech nic neví. Jistě, rozdělil text na slova různých tvarů a velikostí, ale pokud jde o to, co jsou tato slova, skener netuší! Slova by mohla být doslovný řetězec, nebo by to mohla být interpunkční znaménko, nebo by to mohlo být něco úplně jiného!

skener neví nic o samotných slovech ani o tom, jaký“ typ “ slova jsou. Prostě ví, kde slova končí a začínají v samotném textu.

tím se nastavuje druhá fáze lexikální analýzy: evaluace. Jednou prozkoumali jsme náš text a rozešli zdrojového kódu do jednotlivých lexém jednotky, musíme hodnotit slovy, že skener se vrátil k nám a zjistit, jaké typy slov se potýkáme s — zejména, musíme se podívat na důležitá slova, která znamenají něco zvláštního v jazyce, snažíme se sestavit.

Hodnocení důležité části

Jakmile jsme dokončili skenování náš zdroj textu a identifikovat naše lexémy, budeme muset něco udělat s naší lexém „slova“. Jedná se o vyhodnocovací krok lexikální analýzy, který je v complier design často označován jako proces lexingu nebo tokenizace našeho vstupu.

Když jsme se zhodnotit naše naskenovaný kód, vše, co děláme, je, že se blíže podívat na každý z lexémy, že naše skener vytvořený. Náš kompilátor se bude muset podívat na každé slovo lexeme a rozhodnout, jaké slovo to je. Proces určování, jaký druh lexému každé „slovo“ v našem textu je, jak náš kompilátor změní každý jednotlivý lexém do tokenu, čímž tokenizing náš vstupní řetězec.

s tokeny jsme se poprvé setkali, když jsme se učili o parse stromech. Tokeny jsou speciální symboly, které jsou jádrem každého programovacího jazyka. Tokeny, jako například (, ), +, -, if, else, then, pomáhají kompilátoru pochopit, jak se různé části výrazu a různé prvky vzájemně vztahují. Analyzátor, který je ústředním bodem fáze analýzy syntaxe, závisí na přijímání tokenů odněkud a poté tyto tokeny změní na strom analýzy.

no, hádejte co? Konečně jsme přišli na to „někde“! Jak se ukazuje, tokeny, které pošlou do analyzátoru jsou generovány v lexikální analýza fáze u tokenizer, také volal lexer.

tak jak přesně token vypadá? Token je poměrně jednoduchý a je obvykle reprezentován jako pár, skládající se z názvu tokenu a nějaké hodnoty (což je volitelné).

Pokud například tokenizujeme náš Shakespearovský řetězec, skončili bychom s tokeny, které by byly většinou řetězcové literály a separátory. Můžeme reprezentovat lexém "dream” jako token takto: <string literal, "dream">. V podobném duchu bychom mohli reprezentovat lexém . jako token, <separator, .>.

všimneme si, že každý z těchto tokenů vůbec nemění lexém — jednoduše k nim přidávají další informace. Token je lexém nebo lexikální jednotka s více podrobnostmi; konkrétně přidaný detail nám říká, jakou kategorii tokenu (jaký typ „slova“) máme co do činění.

Nyní, když jsme tokenizovali naši shakespearovskou větu, vidíme, že v našem zdrojovém souboru není tolik rozmanitosti typů žetonů. Naše věta měla pouze řetězce a interpunkci — ale to je jen špička ledovce tokenu! Existuje spousta dalších typů „slov“, do kterých lze lexém rozdělit.

zde uvedená tabulka ukazuje některé z nejběžnějších tokenů, které by náš kompilátor viděl při čtení zdrojového souboru v téměř jakémkoli programovacím jazyce. Viděli jsme příklady literals, který může být libovolný řetězec, číslo nebo logická/boolean hodnotu, stejně jako separators, které jsou jakýmkoliv typem interpunkce, včetně složených závorek ({}) a závorky (()).

However, there are also keywords, which are terms that are reserved in the language (such as ifvarwhilereturn), as well as operators, which operate on arguments and return some value ( +-x/). Můžeme také setkat s lexémy, které by mohly být tokenizovaný jako identifiers, které jsou obvykle názvy proměnných, nebo věci, které uživatel/programátor referenční něco jiného, stejně jako , která by mohla být linka nebo blok komentáře napsané uživatelem.

naše původní věta nám ukázala pouze dva příklady žetonů. Přepíšeme naši větu, abychom místo toho četli: var toSleep = "to dream";. Jak by mohl náš kompilátor lex tuto verzi Shakespeara?

zde uvidíme, že máme větší škálu žetonů. Máme keywordvar, kde budeme deklarovat proměnnou, a identifiertoSleep, což je způsob, který jsme pojmenovali naše proměnné, nebo odkazování na hodnotu přijít. Dále je naše =, což je operator token, následuje řetězec literál "to dream". Naše prohlášení končí oddělovačem ;, označujícím konec řádku a vymezujícím mezery.

důležitá věc, kterou je třeba si uvědomit o procesu tokenizace, je, že ani tokenizujeme žádné mezery (mezery, nové řádky, karty, konec řádku atd.), ani předání analyzátoru. Nezapomeňte, že analyzátoru jsou dány pouze žetony a skončí ve stromu analýzy.

je také třeba zmínit, že různé jazyky budou mít různé znaky, které tvoří jako mezery. Například v některých situacích programovací jazyk Python používá odsazení-včetně karet a mezer — k označení toho, jak se mění rozsah funkce. Takže, Python kompilátor je tokenizer musí být vědomi skutečnosti, že v určitých situacích, tab nebo space vlastně nemusí být tokenizovaný jako slovo, protože to vlastně musí být předán parseru!

Tento aspekt tokenizer je dobrý způsob, jak kontrastní, jak lexer/tokenizer je odlišný od skeneru. Zatímco skener je neznalý a ví pouze, jak rozdělit text na jeho menší možné části (jeho „slova“), lexer/tokenizer je mnohem více vědomý a přesnější ve srovnání.

tokenizer potřebuje znát složitosti a specifikace jazyka, který je kompilován. Pokud tabs jsou důležité, je třeba vědět, že;, pokud newlines může mít určité významy v jazyce, který je sestaven, tokenizer musí být vědomi těchto informací. Na druhou stranu skener ani neví, co jsou slova, která rozděluje, natož co znamenají.

skener complieru je mnohem více jazykově Agnostický, zatímco tokenizer musí být podle definice specifický pro jazyk.

tyto dvě části procesu lexikální analýzy jdou ruku v ruce a jsou ústředním bodem první fáze procesu kompilace. Samozřejmě, že různé compliers jsou navrženy svým vlastním jedinečným způsobem. Některé kompilátory udělat krok skenování a tokenizing v jediném procesu a jako jeden program, zatímco jiní se je rozdělit do různých tříd, v takovém případě tokenizer hovor třídy scanner, když je spuštěn.

v obou případech je krok lexikální analýzy pro kompilaci velmi důležitý, protože na něm přímo závisí fáze analýzy syntaxe. A i když každá část kompilátoru má své vlastní specifické role, opírají se o sebe a závisí na sobě-stejně jako vždy dobří přátelé.

zdroje

protože existuje mnoho různých způsobů, jak napsat a navrhnout kompilátor, existuje také mnoho různých způsobů, jak je naučit. Pokud provedete dostatečný výzkum základů kompilace, je zcela jasné, že některá vysvětlení jdou mnohem podrobněji než jiná, což může nebo nemusí být užitečné. Pokud zjistíte, že se chcete dozvědět více, níže jsou uvedeny různé zdroje kompilátorů — se zaměřením na fázi lexikální analýzy.

1. Kapitola 4 — Crafting Tlumočníků, Robert Nystromové
2. Výstavba Překladačů, Profesor Allan Gottlieb
3. Kompilátor Základy, Profesor James Alan Farrell
4. Psaní programovací jazyk — Lexer, Andy Balám
5. Poznámky na to, Jak Analyzátorů a Překladačů Práce, Stephen Raymond Ferg
6. Jaký je rozdíl mezi symbolickou a lexém?, StackOverflow