Lexikální analýza Teorie programovacích jazyků

Lexikální analýza Teorie programovacích jazyků doc. Ing. Jiří Rybička, Dr. ústav informatiky PEF MENDELU v Brně [email protected]

Úvod do teorie překladačů

Lexikální analýza

Příklad implementace

Osnova dnešní přednášky 1

Úvod do teorie překladačů – – – –

2

kompilátor a interpret možnosti využití překladačů struktura překladače reakce na chybu ve vstupu

Lexikální analyzátor – lexikální symboly a jejich atributy – rozpoznávání symbolů ze vstupu – možnosti implementace

3

Příklad implementace – návrh jazyka – realizace

Teorie programovacích jazyků

Přednáška 5: Lexikální analýza

2 / 32




Základní pojmy z teorie překladačů • Překladač je program, který čte zdrojový program • •

•

•

a převádí ho do ekvivalentního cílového programu Zdrojový program je napsán ve zdrojovém jazyce, cílový program je v cílovém jazyce Důležitou částí procesu překladu jsou diagnostické zprávy například o přítomnosti chyb ve zdrojovém programu Generační překladač (kompilátor) převádí zdrojový jazyk do ekvivalentního strojového kódu nebo jazyka symbolických instrukcí Interpretační překladač (interpret) přímo interpretuje příkazy zdrojového jazyka tak, jak jsou napsány



3 / 32




Kompilátor × interpret Data

Zdrojový program

Cílový program

Překladač

Výsledky

Data

Zdrojový program


Interpret


Výsledky

4 / 32




Kompilátor × interpret Vlastnost

Kompilátor Interpret

Rychlost běhu cílového programu Rychlost spuštění cílového programu Rychlost překladu

lepší lepší

Spotřeba paměti – operační (při běhu) Spotřeba paměti – cílový soubor na médiu

lepší

Přenositelnost kódu mezi SW platformami Možnosti optimalizace Nezávislost na překladači



lepší lepší lepší lepší lepší

5 / 32




Možnosti využití překladačů • Překladače programovacích jazyků – nejčastější použití • Strukturované editory – analýza textu, vkládání hierarchické struktury – kontrola syntaxe, doplňování párových závorek – kontextová nápověda při psaní • Formátovací programy – analýza programu a jeho tisk se zřetelnou strukturou – barevné odlišení poznámek, příkazů apod. • Programy pro sazbu textů – TEX, jeho formáty a rozšíření



6 / 32




Struktura překladače

Lexikální analýza Syntaktická analýza

Intermediární jazyk

Sémantická analýza


Koncová (syntetická) část

Přední (analytická) část

Zdrojový jazyk

Optimalizace intermediárního kódu Generátor kódu

Cílový jazyk

Optimalizace cílového kódu


7 / 32




Schéma konstrukce překladače i

f

a

>

=

4

lineární gramatiky ⇒ regulární gramatiky ⇒ ⇒ nedeterministický konečný automat ⇒ ⇒ deterministický konečný automat

Lexikální analyzátor

bezkontextové gramatiky ⇒ ⇒ deterministické bezkontextové gramatiky ⇒ ⇒ deterministický zásobníkový automat

Syntaktický analyzátor

Sémantický analyzátor


jednosměrná vstupní páska

...

proměnné, vyhodnocení výrazů, podprogramy, podmínky, cykly, pole, systémová volání . . . atributové gramatiky


8 / 32




Analytická část překladače • Lexikální analyzátor – čte posloupnost znaků zdrojového kódu a sestavuje z ní lexikální symboly, vynechává oddělovače a komentáře – na každé zavolání vrátí jeden lexikální symbol (token) – konstanty, identifikátory, operátory, klíčová slova • Syntaktický analyzátor – vytváří hierarchicky zanořené struktury vytvořené na základě posloupnosti tokenů a kontroluje syntaxi – výrazy, příkazy, deklarace • Sémantický analyzátor – kontrola vazeb, které nelze provádět na úrovni syntaktické analýzy – deklarace, typová kontrola, intermediární kód Teorie programovacích jazyků


9 / 32




Informace o chybě ve zdroji • Místo výskytu chyby – číslo řádku a pozice na něm • Druh chyby – lexikální analyzátor – neznámé symboly (12YT) – syntaktický analyzátor – chyby v syntaktické struktuře (begyn), přehozená či chybějící klíčová slova nebo symboly (if x else x := 3) – sémantický procesor – chyby zjistitelné při překladu (nedeklarovaná proměnná, nekompatibilní datový typ) a běhové chyby související s aktuální hodnotou proměnné (dělení nulou, přetečení, nedovolený přístup do paměti) • U některých překladačů také návrhy na opravu chyby • Logické chyby (chybná posloupnost příkazů, záměna

operátorů, překlep v číslech) prakticky nelze odhalit! Teorie programovacích jazyků


10 / 32




Reakce překladače na chybu • Při prvním výskytu chyby se zastaví, provede

diagnózu, informuje uživatele a čeká na opravu chyby (Turbo Pascal) • Pokouší se najít co nejvíce chyb najednou, zastaví se až při určitém maximálním počtu a informuje uživatele o všech objevených chybách, příp. o maximálním počtu chyb, které je schopen zobrazit (C++)



11 / 32




Zotavení po chybě v lexikální analýze • Obecně se při lexikální analýze rozpozná jen malé

množství chyb • Možnosti reakce analyzátoru na neznámý symbol na vstupu – vypouštění znaků ze zbývajícího vstupu tak dlouho, dokud není rozpoznán známý symbol – vrácení kódu zvláštního terminálního symbolu bez ohlášení chyby a předání řešení problému syntaktickému analyzátoru – vypuštění přebývajícího znaku – vložení chybějícího znaku – náhrada nesprávného znaku správným – vzájemná výměna dvou sousedních znaků Teorie programovacích jazyků


12 / 32




Lexikální analýza • Na vstupní pásce rozlišujeme množiny řetězců, které

tvoří stejné významové kategorie – tzv. lexikální symboly (tokeny) jazyka – – – – – – – –

klíčová slova operátory identifikátory konstanty (literály) řetězce interpunkční symboly (závorky, čárky, středníky) komentáře oddělovače (bílé znaky)

• Na složitost lexikální analýzy mají značný dopad některé

jazykové konvence Teorie programovacích jazyků


13 / 32




Problémy lexikální analýzy • Pevná pozice určitých konstrukcí na vstupním řádku – umístění může být důležité při určování správnosti zdrojového programu (Fortran) – trendy tvorby moderních programovacích jazyků směřují spíše ke vstupu ve volném formátu • Zpracování mezer – v některých jazycích nejsou mezery významné (s výjimkou mezer uvnitř řetězce) – mohou být doplněny pro zvýšení čitelnosti programu – konvence týkající se mezer mohou značně komplikovat identifikaci symbolů



14 / 32




Problémy lexikální analýzy • Rezervované řetězce – předdefinovaný význam, který uživatel nemůže změnit – nejsou-li klíčová slova rezervována, musí je od uživatelem definovaného identifikátoru rozlišit lexikální analyzátor – definice klíčových slov jako samostatných symbolů jazyka – definice klíčových slov pomocí ztotožnění s běžnými identifikátory, následné porovnání s tabulkou klíčových slov je jednodušší na implementaci



15 / 32




Atributy symbolů • Lexikální analyzátor musí následujícím fázím překladače • • • •

poskytovat informaci o tom, jaký symbol byl rozpoznán Důležitý je nejen typ symbolu (např. identifikátor), ale také jeho skutečný obsah (např. vysledek) Informace o jednotlivých rozpoznaných symbolech jsou shromažďovány v atributech symbolů Atributy symbolů významně ovlivňují překlad, neboť mají vliv na rozhodování syntaktického analyzátoru Pro účely diagnostiky nás často kromě samotného symbolu zajímá také číslo řádku, na kterém se symbol objevil



16 / 32




Lexikální analýza Příklad Vstup:

pozice := počátek + rychlost * 60

Výstup: • • • • • • •

identifikátor symbol přiřazení identifikátor operátor identifikátor operátor číslo


pozice := počátek + rychlost * 60


17 / 32




Vstup zdrojového textu • Může být v nejjednodušším případě realizováno voláním

standardních funkcí programovacích jazyků, avšak obecně se jedná o problém daleko složitější – čtení po jednotlivých znacích může být značně neefektivní ve srovnání se čtením po řádcích nebo po velkých blocích textu – při čtení zdroje se může provádět jeho opis do výstupní tiskové soustavy doplněný o další získané informace – při vkládání částí zdrojového textu z jiných souborů, práci s makrodefinicemi nebo podmíněném překladu je třeba tuto činnost provést samostatně předem nebo současně s lexikální analýzou během čtení znaků – největším problémem je nutnost návratu zpět ve vstupním souboru po rozpoznání symbolu Teorie programovacích jazyků


18 / 32




Specifikace a rozpoznávání symbolů • Při implementaci lexikálního analyzátoru vycházíme

z popisu struktury jednotlivých lexikálních jednotek • Tento popis může být v jednom z následujících tvarů – – – –

slovní popis lineární nebo regulární gramatika přechodový graf konečného automatu regulární výraz



19 / 32




Implementace lexikálního analyzátoru • Přímá implementace – využití všech prostředků, které poskytuje implementační jazyk • Implementace konečného automatu – deterministický konečný automat se stavovým řízením • Vytvoření konstruktorem – nejvýhodnější popis struktury regulárním výrazy – nejjednodušší, ale nejméně efektivní způsob implementace



20 / 32




Implementace lexikálního analyzátoru konečným automatem • Navrhneme jazyky pro skupiny významových tokenů,

které jsou výstupem lexikální analýzy – – – – –

jazyk identifikátorů (včetně klíčových slov) – Lid jazyk operátorů – Lop jazyk konstant – Lcon jazyk řetězců – Lstr jazyk ostatních symbolů – Lsym

• Navrhneme jazyky pro skupiny nevýznamových tokenů,

které nejsou zahrnuty do výstupu lexikální analýzy – jazyk komentářů – Lkom – jazyk bílých znaků – Lbz Teorie programovacích jazyků


21 / 32




Implementace lexikálního analyzátoru konečným automatem • Jazyk významových tokenů

Lvt = Lid ∪ Lop ∪ Lcon ∪ Lstr ∪ Lsym

• Jazyk nevýznamových tokenů (oddělovačů)

Lod = Lkom ∪ Lbz • Programovací jazyk L = (L∗od · Lvt )∗ · L∗od • Dva významové tokeny mohou jít bezprostředně po sobě pouze tehdy, jsou-li různého typu, v opačném případě musí být odděleny alespoň jedním oddělovačem • V každém kroku zpracuje lexikální analyzátor jazyk (L∗od · Lvt ), na konci vstupu může být posloupnost oddělovačů L∗od Teorie programovacích jazyků


22 / 32




Implementace lexikálního analyzátoru Příklad – návrh jazyka pracujícího s celými čísly Nejdříve navrhneme abecedu jazyka: Σ = {A, …, Z, a, …, z, 0, …, 9, +, −, ∗, /, >, <, =, (, ), ; , :} Stanovíme potřebné lexikální jednotky: • celá nezáporná čísla (pro konstanty) • vyhrazená klíčová slova (BEGIN, END, VAR, CONST, IF, THEN, ELSE, PRINT) • ostatní nerezervované identifikátory (proměnné) • aritmetické operátory (+, −, ∗, /) • relační operátory (<, <=, >, >=, <>, =) • operátor přiřazení (:=) • pomocné symboly (závorky, středník) Teorie programovacích jazyků


23 / 32




Implementace lexikálního analyzátoru Příklad – pokračování Popíšeme navržený jazyk pomocí regulárních gramatik dílčích jazyků: Gramatika jazyka identifikátorů: Gid = ({Sid , A}, {l, d}, P, Sid ) Sid → l | lA A → l | d | lA | dA Gramatika jazyka celých nezáporných čísel: Gcis = ({Scis , B}, {d}, P, Scis ) Scis → d | dB B → d | dB



24 / 32




Implementace lexikálního analyzátoru Příklad – pokračování Gramatika jazyka aritmetických operátorů: Gao = ({Sao }, {+, −, ∗, /}, P, Sao ) Sao → + | − | ∗ | / Gramatika jazyka relačních operátorů: Gro = ({Sro , C, D}, {<, >, =}, P, Sro ) Sro → < | > | = | D C → =|> D → = Gramatika jazyka operátoru přiřazení: Gop = ({Sop , E}, {:, =}, P, Sop ) Sop → :E E → = Teorie programovacích jazyků


25 / 32




Implementace lexikálního analyzátoru Příklad – pokračování Gramatika jazyka pomocných symbolů: Gsym = ({Ssym }, {(, ), ; }, P, Ssym ) Ssym → ( | ) | ; Sestavíme jazyk významových tokenů a gramatiku, která jej generuje: Lvt = Lid ∪ Lcis ∪ Lao ∪ Lro ∪ Lop ∪ Lsym Gvt = ({Svt , Sid , Scis , Sao , Sro , Sop , Ssym , A, B, C, D, E}, Σ, P, Svt ) Svt → Sid | Scis | Sao | Sro | Sop | Ssym Dále sestavíme jazyk nevýznamových tokenů Lod popsaný gramatikou God = ({Sod }, {L, ←-}, P, Sod ): Sod → L | ←Teorie programovacích jazyků


26 / 32




Implementace lexikálního analyzátoru Příklad – pokračování V každém kroku lexikální analyzátor zpracuje jazyk L = L∗od · Lvt , který lze intuitivně popsat (bezkontextovou) gramatikou G = (N, Σ, P, S): S → Sod S | Svt Pro účely implementace analyzátoru konečným automatem bezkontextovou gramatiku využít nemůžeme, proto použijeme ekvivalentní lineární gramatiku G = (N, Σ, P, S): S → LS | ←-S | Svt Pokud povolíme existenci prázdného jazyka, tj. pokud ϵ ∈ L, přidáme nový startovací symbol S ′ a nová pravidla S ′ → ϵ | S. Nakonec odstraníme jednoduchá pravidla a dostaneme výslednou regulární gramatiku. Teorie programovacích jazyků


27 / 32




Implementace lexikálního analyzátoru Příklad – pokračování Výsledná regulární gramatika lexikálního analyzátoru: G = ({S, A, B, C, D, E}, {l, d, +, −, ∗, /, <, >, =, :, (, ), ; , L, ←-}, P, S) S S S A B C D E


→ → → → → → → →

LS | ←-S l | lA | d | dB | + | − | ∗ | / | < | > | = D | :E | ( | ) | ; l | d | lA | dA d | dB =|> = =


28 / 32




Implementace lexikálního analyzátoru Příklad – pokračování Převedeme gramatiku na nedeterministický konečný automat M = ({qS , qA , qB , qC , qD , qE , qbF }, Σ, δ, qS , {qbF }) δ

l

d

+

−

∗

/

<

>

=

:

(

)

;

L

←-

→ qS {qA , qbF } {qB , qbF } {qbF } {qbF } {qbF } {qbF } {qC , qbF } {qD , qbF } {qbF } {qE } {qbF } {qbF } {qbF } {qS } {qS } qA {qA , qbF } {qA , qbF } qB {qB , qbF } qC {qbF } {qbF } qD {qbF } qE {qbF } ← qbF



29 / 32




Implementace lexikálního analyzátoru Příklad – pokračování Převedeme konečný automat na deterministický, odstraníme nepotřebné stavy: M = ({qS , qE , qbF , qAbF , qBbF , qCbF , qDbF }, Σ, δ, qS , {qbF , qAbF , qBbF , qCbF , qDbF }) δ

l

d

+ − ∗ /

<

> = :

→ qS qAbF qBbF qbF qbF qbF qbF qCbF qDbF qE ← qbF ← qAbF qAbF qAbF ← qBbF qBbF ← qCbF qbF ← qDbF Teorie programovacích jazyků

(

)

; L ←-

qbF qE qbF qbF qbF qS qS qbF

qbF qbF


30 / 32




Implementace lexikálního analyzátoru Příklad – pokračování d qAFb l

l

qC Fb >

qDFb

< + − ∗

>

= =

/

←֓

=

qS

qFb

(

L

) ; :

qBFb


=

qE

d

d


31 / 32




Realizace analyzátoru v program. jazyce • Ze všech stavů automatu vytvoříme výčtový typ,

z koncových stavů vytvoříme množinu • V každém stavu automatu načteme ze zdrojového

programu jeden znak a podle toho se rozhodneme, kterou větví pokračovat • V koncovém stavu provedeme test korektního ukončení načteného symbolu – načteme následující znak • Pokud automat nenalezne větev, po které by pokračoval, a je v koncovém stavu, právě načetl jeden symbol a po analýze dalšího znaku (viz předchozí bod) se přesouvá do počátečního stavu qS • Pokud automat nenalezne větev, po které by mohl pokračovat, a není v koncovém stavu, načtený znak je chybný a je ohlášena lexikální chyba Teorie programovacích jazyků


32 / 32

Lexikální analýza Teorie programovacích jazyků

Recommend Documents