Princípy programovacích jazykov

Ján Kollár, 2008

 

 

 

1. Návrh jazyka

 

Programovací jazyk je prostriedkom, v ktorom programátor formuluje

problémy pre pocítac. Každý program je popisom problému, vykonatelným

na pocítaci. Cielom programovania je teda presné vyjadrenie problémov

v programovacom jazyku, nazývaných tiež algoritmickými problémami.

Pocítac je technické zariadenie, schopné vykonávat strojové inštrukcie.

Jazyk strojových inštrukcií je jazykom, v ktorom je problém pripravený

pre vykonanie na pocítaci. Prekladac je program, ktorý transformuje problém

vyjadrený vo vyššom programovacom jazyku do jazyka strojových inštrukcií.

Táto transformácia je možná, pretože problém ostáva tým istým

problémom, bez ohladu na to, ci je vyjadrený vo vyššom programovacom

jazyku alebo v jazyku strojových inštrukcií.

Dôvodom pre návrh vyšších programovacích jazykov a konštrukciu ich

prekladacov je to, že cím vyššia je úroven programovacieho jazyka, a cím

primeranejší je programovací jazyk oblasti riešených problémov, tým je

vyjadrenie algoritmických problémov spolahlivejšie a rýchlejšie.

Navrhnút programovací jazyk znamená teda definovat jeho syntax, t.j.

štruktúru a sémantiku, t.j. význam jeho prvkov, a to pomocou formálnych

prostriedkov návrhu. Na základe takéhoto návrhu, t.j. špecifikácie jazyka je

možné konštruovat jeho prekladac, napríklad prepísaním formálnej špecifikácie

do programu v programovacom jazyku, ako je napr. C alebo Pascal.

 

Tento program je prekladacom a má dve základné funkcie:

 

analyzovat syntaktickú správnost zdrojového kódu, nazývaného v

teórii formálnych jazykov a automatov retazcom terminálnych symbolov.

transformovat zdrojový kód do cielového kódu, zachovávajúc jeho

význam.

 

Volba formálnych prostriedkov, ako aj metóda konštrukcie je silne závislá

od triedy, do ktorej patrí navrhovaný jazyk. Ak povieme, že pre návrh

jazyka stací poznat tieto formálne prostriedky návrhu:

 

rozšírenú Backus-Naurovu formu pre zápis gramatiky jazyka a

denotacnú sémantiku pre vyjadrenie významu prvkov jazyka

musíme dodat, že to platí pre bezkontextové jazyky LL(1).

 

 

 

 

 

1.1 Gramatiky a jazyky

 

Syntax jazyka je definovaná jeho gramatikou G, ktorá je vo všeobecnosti

štvoricou podla nasledujúceho vztahu:

G = (VN, VT , P, S)

kde

VN je množina neterminálnych symbolov

VT je množina terminálnych symbolov

P je množina pravidiel v tvare alfa -> beta

S je zaciatocný symbol (S patri do VN)

 

V gramatike G alfa aj beta sú retazce lubovolných symbolov. Gramatika G

sa nazýva tiež gramatikou G0. Podla tvaru pravidiel je možné rozlíšit dalšie

tri druhy gramatík, kontextovú gramatiku G1, bezkontextovú gramatiku

G2 a regulárnu gramatiku G3.

 

Tvar pravidiel pre gramatiky G0, G1, G2 a G3 je takýto

 

pre kontextovú gramatiku G1

 

omega1 A omega2 -> omega1 omega omega2

 

pre bezkontextovú gramatiku G2

 

A -> omega

 

pre regulárnu gramatiku

 

A -> a

alebo

A -> a B

 

 

kde a, b patria do  VT ,

 

A,B patria do VN

 

omega1, omega2, a omega,  su retazce tvorene symbolmi z  VN  alebo  VT

 

Medzi jazykmi generovanými jednotlivými typmi gramatík platí nasledujúci

vztah:

 

L(G3) je podmnožinou L(G2) je podmnožinou L(G1) je podmnožinou L(G0)

 

 

Algoritmus rozpoznania (analýzy) retazca terminálnych symbolov je

automat, pre regulárne jazyky konecný, a pre bezkontextové zásobníkový

 

To prakticky znamená, že algoritmus, ktorý je konecným automatom,

nie je schopný rozpoznat bezkontextový jazyk, iba regulárny jazyk.

 

Pri návrhu vyšších programovacích jazykov sú v centre záujmu bezkontextové

jazyky, pretože na jednej strane ich štruktúra je dostatocná pre

vyjadrenie algoritmických problémov a na druhej strane existuje pre ne

efektívny algoritmus syntaktickej analýzy – zásobníkový automat. Všetky

súcasné jazyky, v praxi najcastejšie používané (napr. C, Pascal, Ada, atd.)

sú bezkontextové.

 

 

1.2 Štruktúra jazyka

 

Terminálne symboly bezkontextovej gramatiky, ktorá definuje syntax

programovacieho jazyka samy môžu mat svoju štruktúru.

 

Regulárne jazyky (nazývané tiež regulárne množiny) možno definovat nielen regulárnymi

gramatikami, ale úplne rovnocenne aj regulárnymi výrazmi.

 

Definícia 1.2.1 Rozšírená definícia regulárneho výrazu.

 

1. a je regulárny výraz (symbol a 2 VT ), ktorý definuje množinu {a}.

2. Ak r, s sú regulárne výrazy, potom:

(a) r | s je regulárny výraz na definíciu množiny {r} [ {s}, ktorá

je zjednotením množín.

(b) r s je regulárny výraz na definíciu množiny {r s}, ktorá je

množinou všetkých zretazení retazcov r a s, definovaných regulárnymi

množinami {r} a {s}.

(c) (r) je regulárny výraz na definíciu množiny {r}. To znamená,

že regulárne výrazy môžu byt uzavreté v zátvorkách.

(d) [r] je regulárny výraz, ekvivalentný regulárnemu výrazu epsilon | r

na definíciu množiny { epsilon } zjednotenie s {r}. epsilon je prázdny symbol

(e) {r} je regulárny výraz na definíciu množiny, ktorá sa nazýva

tranzitívnym, alebo Kleeneho uzáverom množiny {r}, ktorý je

definovaný nasledovne:

{r} = epsilon | r | r r | r r r | ....

 

Kladný uzáver množiny je potom r {r}, t.j. neobsahuje epsilon

 

 

 

Pri návrhu jazyka je potrebné dbat na to, aby jazyk symbolov bezkontextovej

gramatiky bol regulárny. Vyššie programovacie jazyky majú teda

dvojúrovnovú štruktúru: syntax jazyka, ktoré je definovaná bezkontextovou

gramatikou a syntax samotných symbolov bezkontextovej gramatiky,

ktoré sa nazývajú lexikálne jednotky a ktorých syntax je definovaná regulárnou

gramatikou. Všimnime si, že regulárne výrazy neobsahujú žiadne

neterminálne symboly.

 

 

 

 

1.3 Formálne prostriedky návrhu jazyka

 

Prostriedkom pre návrh syntaxe jazyka je Backus Naurova forma (BNF),

ktorá je kompaktnejším zápisom pravidiel bezkontextovej gramatiky, využívajúc

aj operáciu sumy |, známu z regulárnych výrazov. Okrem toho v

BNF je možné definovat pravidlá v tvare A -> epsilon.

 

Treba však povedat, že BNF nie je velmi vhodná ani návrh jazyka,

ani pre konštrukciu syntaktického analyzátora programom v rekurzívnom

procedurálnom jazyku. Dôvod je rýdzo praktický a spocíva v tom, že BNF

je funkcionálnou formou špecifikácie, ktorá nemá (na rozdiel od rozšírenej

BNF) špeciálne zátvorkované výrazy, ktoré je možné priamo prepísat do

procedurálneho jazyka, ci už vo forme príkazov vetvenia alebo cyklu.

 

1.3.1 Rozšírená Backus Naurova forma

 

Rozšírená Backus Naurova forma – EBNF (Extended BNF) vyjadruje

gramatiku bezkontextového jazyka spôsobom, ktorým sa jednak vyhýba

prázdnemu symbolu a ktorý je tiež primeraný realizácii syntaktického analyzátora,

ktorý je jadrom prekladaca, v procedurálnom rekurzívnom jazyku.

 

Pretože regulárne jazyky sú podtriedou bezkontextových jazykov,

EBNF je zároven prostriedkom na definovanie gramatiky lexikálnych jednotiek,

teda lexikálnej gramatiky jazyka.

 

Gramatika lexikálnych jednotiek, zapísaná v EBNF je regulárna vtedy,

ak je možné ju prepísat do tvaru množiny pravidiel takých, že na pravej

strane každého pravidla sú regulárne výrazy, t.j. syntaktické výrazy, ktoré

neobsahujú žiadny neterminálny symbol.

 

 

Syntax EBNF je uvedená v definícii 1.3.1, ktorá je zapísaná pomocou

EBNF samotnej.

 

Definícia 1.3.1 Syntax EBNF.

 

EBNF -> Pravidlo { Pravidlo }

Pravidlo -> A  “->   fi

fi -> alfa { |” alfa }

alfa  ->  X { X }

X -> a| A| ”(” fi ”)” | ”[” fi ”]” | {” fi }

kde fi je syntaktický výraz, ktorý je sumou postupností alfa symbolov

X, z ktorých každý môže byt bud terminálnym symbolom a, alebo neterminálnym

symbolom A, alebo zátvorkovaným syntaktickým výrazom v

troch formách.

 

Rozšírenie oproti BNF spocíva v tom, že symbolom X nemôže byt

prázdny symbol epsilon, môžu však ním byt zátvorkované výrazy v tvare (fi),

[fi], {fi}, pricom platí:

 

 

 ( fi1  |  fi2 ) fi 3 = fi1  fi 3 | fi2  fi3

[ fi ] = epsilon | fi

{ fi } = epsilon | fi | fi fi | fi fi fi | . . .

 

 

 

 

1.3.2 Denotacná sémantika jazyka

 

 

Gramatika jazyka môže mat definované iba tie prvky jazyka, ktoré majú

svoj význam.

Denotacná sémantika slúži ako špecifikacný prostriedok definície významu

prvkov jazyka a je podkladom pre preklad – generovanie medzijazykov,

resp. cielového jazyka.

Denotacná sémantika v najvšeobecnejšej rovine znamená význam urcený

popisom, t.j. vyjadrenie významu funkciou Eval, ktorej argument V

(uvedeným v zátvorkách [[ a ]] ) je syntaktický výraz a hodnota syntaktického

výrazu je urcená hodnotou výrazu v na pravej strane nasledovne:

Eval [[ V ]] ro a1 a2 . . . an = v

Argumentom funkcie Eval okrem syntaktického výrazu V je aj funkcia

ro nazývaná prostredím. Táto funkcia urcuje hodnoty premenných prostredia

používaných vo výraze v. Okrem toho funkcia Eval môže mat dalšie

parametre a1, a2, . . . , an (n >= 0).

 

Premennú x možno zaviest do prostredia ro výrazom ro[x = 2], a okamžite

definovat hodnotu syntaktického výrazu oznacujúcu premennú x aplikáciou

ro x, ktorej hodnota je 2, a to takto:

 

Eval [[ x ]] ro[x = 2] = ro x

 

Je podstatný rozdiel medzi premennou x v zátvorkách [[ a ]] , kde x

je syntaktickým výrazom, t.j. prvkom nejakého programovacieho jazyka a

premennou x prostredia, ktorá je matematickou premennou.

 

Dôvod pre použitie zložitej sémantickej funkcie ro v denotacnej sémantike

vyplýva z toho, že denotacná sémantika definuje význam celku na

základe významu stavebných kamenov, z ktorých tento celok pozostáva.

 

Formalizmus denotacnej sémantiky je teda funkcionálny a preto

neumožnuje pracovat s hodnotami premenných prostredia. Ak by sme vyjadrili

hodnotu syntaktického výrazu exp

 

Eval [[ exp ]] = Val y

 

je to možné, ak dodáme, že Val y je hodnota premennej y, treba však

neformálne vysvetlit, co je premenná y prostredia. Takýto nepresný prístup

sa však v praxi casto používa, pretože denotacná sémantika je strucná

a výstižná a neformálne vysvetlenie prostredia je casto omnoho prehladnejšie

ako jeho formálna definícia zložitou sémantickou funkciou ro. Napríklad,

prostredie prekladu vyššieho prgramovacieho jazyka je tvorené štyrmi tabulkami

symbolov: tabulkou konštánt a tabulkou identifikátorov, ktoré

sú používané vo fáze lexikálnej analýzy, tabulkou pre sémantickú analýzu

a tabulkou adries používanou v poslednej fáze prekladu - pri generovaní

cielového (strojového) kódu. V tejto poslednej fáze sa opätovne používa

tabulka konštánt.

 

Pomocou denotacnej sémantiky je zvycajné definovat syntaktický výraz

– císlicu 2 matematickou hodnotou 2, a to takto:

 

Eval [[ 2 ]] = 2

 

Je zrejmé, že možno definovat aj hodnotu pre syntaktický výraz reprezentujúci

rímsku císlicu II, teda

 

Eval [[ II ]] = 2

 

Rozdiel medzi syntaktickým výrazom a jeho hodnotou by mal byt

zrejmý, napriek tomu uvedme ešte jeden extrémnejší príklad.

Eval [[ exp ]] vyhodnocuje výraz exp

Eval [[ exp1 * exp2 ]] = Eval [[ exp1 ]] + Eval [[ exp2 ]]

Eval [[ 2 ]] = 3

Eval [[ 1 ]] = 6

Po vyhodnotení syntaktického výrazu 2 * 2 v jazyku Pascal alebo C

je výsledok 4. V uvedenom prípade na výstupe sa objaví 1, pricom matematická

hodnota tejto „jednotky“ je 6. Je to tak preto, že matematická

hodnota „dvojky“ je 3, a matematická hodnota výrazu 2 * 2 je 3 + 3, t.j.

6, pretože operátor * symbol _ reprezentuje operáciu scítania. Výpocet sa

vykonáva v tvare 3 + 3 = 6, ale výsledok 6 sa na výstupe znovu objaví v

syntaktickej forme hodnoty 6, t.j. vo forme jednotky.

 

Uvedený príklad je jasným dôkazom toho, že sémantika jazyka nie je

vlastnostou syntaxe automaticky a väzba syntaxe a sémantiky jazyka je

urcená záležitostou definície pri návrhu jazyka.

 

 

1.4 Podmienky realizácie

Vyjadrenie syntaxe jazyka pomocou EBNF samo osebe nie je dostatocné

pre realizáciu syntaktického analyzátora programom v rekurzívnom jazyku.

Ak by sme vychádzali pri návrhu jazyka iba z doterajších poznatkov,

mohlo by sa lahko stat, že syntaktický analyzátor by sa zacyklil, alebo

by nerozpoznal retazec, ktorý patrí do jazyka, alebo by rozpoznal retazec

takým spôsobom, že pri preklade by došlo k nesprávnej sémantickej interpretácii.

Pri programovej realizácii syntaktickej analýzy v rekurzívnom jazyku

cítame analyzovaný retazec zlava (L) a konštruujeme najlavejšie odvodenie

(Leftmost derivation), t.j. také, v ktorom pocnúc zaciatocným symbolom

gramatiky, nahradíme v každej vetnej forme najlavejší neterminálny

symbol príslušnou pravou stranou pravidla. Ak odvodený retazec terminálnych

symbolov je rovnaký ako vstupný retazec, tento vstupný retazec

patrí do jazyka. Ak navyše rozhodnutie pre výber pravej strany pravidla

je možné na základe jedného terminálneho symbola na vstupe, potom

nazývame takýto jazyk jazykom LL(1) a príslušnú metódu syntaktickej

analýzy syntaktickou analýzou zhora nadol.

Metódu pri ktorej cítame vstupný retazec opät zlava (L), ale zacíname

pri odvodení s tým istým retazcom, pricom hladáme pravú stranu pravidla

v každej vetnej forme tak, že konštruujeme najpravejšie odvodenie

(Rightmost derivation), až k zaciatocnému symbolu, pricom rozhodnutie

pre výber pravidla je možné urobit na základe k symbolov na vstupe,

nazývame syntaktickou analýzou zdola nahor a jazyk, ktorý je možné rozpoznat

týmto spôsobom jazykom LR(k).

 

 

 

1.5 Návrh interpretátora

Cielom tejto kapitoly je ukázat praktický rozsah a konkrétnu realizáciu

metodiky návrhu jazyka typu BASIC.

 

1.5.1 Reprezentatívny program

 

Návrh jazyka vychádza najprv z neformálnej analýzy reprezentatívnych

fragmentov programov, zapísaných v navrhovanom jazyku, a to z hladiska

ich syntaxe aj sémantiky. Iba pre jednoduché jazyky stací napísat jeden

program, napríklad v nasledujúcej forme:

 

input z; print z;                     ’precitanie z a vypis’

x=3;                                      ’priradenie 3 do x’

y=4;                                      ’priradenie 4 do y’

z=(x+y*y+z)/2+10;               ’priradenie hodnoty vyrazu’

print z;                                   ’vypis hodnoty premennej’

print (x+y)/3.                         ’vypis hodnoty vyrazu’

 

Uvedený príklad programu ilustruje štruktúru navrhovaného jazyka a

ciastocne v komentároch aj jeho sémantiku. Lexikálne jednotky sú klúcové

slová (input a print), identifikátory (x,y, z, dovolíme však aj viacpísmenové

identifikátory), konštanty (3, 4, 2, 10, t.j. iba obmedzíme sa na celocíselné

konštanty), operátory  +, -,*, / ,  a dovolíme aj binárne odcítanie

 

a špeciálne symboly  ;   =  (  ) a .   

 

Dalej sú prípustné komentáre ako retazce

symbolov v apostrofoch a prázdnymi znakmi sú medzery, tabelátory

a znaky konca riadku.

 

Z komentárov je síce intuitívne jasné, co od uvedeného programu ocakávame,

upresnime však dalej (zatial stále neformálne) sémantiku na príklade

výpoctu.

 

 

Na výzvu INPUT z[0] : predpokladajme vstup císla 10 z klávesnice

a nasledujúci výsledok vykonania vyššieuvedného programu na obrazovke:

INPUT z[0] : 10

PRINT 10

x[1] = 3

y[2] = 4

z[0] = 24

PRINT 24

PRINT 2

STOP

 

Vidíme, že okrem výstupu, na aký sme zvyknutí v jazyku BASIC,

interpretátor má produkovat aj urcité kontrolné výpisy.

 

1.5.2 Definícia gramatiky jazyka

Definujme teraz gramatiku jazyka, pre syntaktickú analýzu zhora nadol.

Najprv neformálne, takto:

Z hladiska štruktúry jazyka program je postupnostou príkazov oddelených

bodkociarkami, zakoncenou bodkou. Príkazy sú tieto: príkaz input

s argumentom – premennou vo forme identifikátora, príkaz print s argumentom

– výrazom expr a príkaz priradenia s premennou (identifikátorom)

na lavej strane znamienka = a výrazom na pravej strane. Vo výraze,

ktorý môže byt zátvorkovaný, sa vyskytujú operátory asociatívne zlava

pricom násobenie a delenie má vyššiu prioritu ako scítanie a odcítanie.

Operandom je bud konštanta alebo hodnota premennej, reprezentovaná

identifikátorom.

Na základe tejto neformálnej špecifikácie štruktúry jazyka, formálna

definícia gramatiky jazyka v tvare EBNF je takáto:

 

 

Program -> Stat Seq .

Stat Seq -> Stat { ”; ” Stat }

Stat -> input id  | print Expr | id ” = ” Expr

Expr -> Mul { ( ” + ” | ” ) Mul }

Mul -> Op { ( ”* | /” ) Op }

Op -> const | id | ”(” Expr ”)”

 

Dodajme ešte lexikálnu gramatiku identifikátora a konštanty v tvare:

id -> P { P | C }

const -> C { C }

P -> A | . . . | Z | a | . . . | z

C -> 0 | . . . | 9

 

Tým je formálny návrh syntaxe jazyka ukoncený.

 

 

1.5.3 Sémantika jazyka

Najprv neformálna analýza sémantiky.

Lexikálny analyzátor zapisuje hodnoty konštánt do tabulky ctab, pocnúc

od indexu 0 a to tak, že kontroluje, ci konštanta v programe už nie je

v ctab zaznamenaná. Ak lexikálny analyzátor podá syntaktickému analyzátoru

a interpretátoru symbol sconsthattri, reprezentujúci v gramatike

konštantu const, potom pri interpretácii možno hodnotu tejto konštanty

nájst v ctab[attr]. I ked pracujeme iba s celocíselnými konštantami, a bolo

by výhodnejšie hodnotu konštanty zaznamenat priamo v atribúte attr,

pre ilustráciu sú tieto konštanty zapisované do tabulky konštánt ctab.

Retazce identifikátorov sú zapisované do tabulky identifikátorov tid,

pocnúc od indexu 0 a to tak, že lexikálny analyzátor kontroluje, ci identifikátor

v programe už nie je v tid zaznamenaný. Podá symbol idhattri pricom je zarucené, že pre rovnaké identifikátory je hodnota attr rovnaká.

Interpretátor môže vždy nájst retazec identifikátora v tid[attr].

Pretože identifikátory oznacujú premenné na globálnej úrovni, atribút

attr symbolu id možno použit na indexovanie hodnoty premennej v

pamäti mem celých císel. Napr. postupnost symbolov input idhattri znamená,

že treba vypísat meno premennej z tid[attr] a precítat a uložit jej

hodnotu do mem[attr] takto:

write(”INPUT”, tid[attr], ”[”, attr, ”] : ”); read(mem[attr]);

hoci by bolo možné sa uspokojit aj s takouto interpretáciou:

read(mem[attr]);

Príkaz read znamená cítanie z klávesnice a write výpis na obrazovku.

Pri popise sémantiky interpretátora nebudeme používat jednu sémantickú

funkciu Eval, ale množinu sémantických funkcií, zodpovedajúcich

neterminálnym symbolom gramatiky. Tento prístup je v súlade so skutocnostou,

že každé pravidlo gramatiky je interpretované samostatným interpretátorom.

Napríklad Program je meno sémantickej funkcie, ktorá definuje

hodnotu syntaktického výrazu – pravej strany pravidla pre Program

na lavej strane. To znamená, že Program interpretuje sémanticky presne

to, co je syntakticky rozpoznané ako Program. Ako uvidíme v nasledujúcej

kapitole, to presne zodpovedá realizácii interpretátora ako množiny

procedúr v procedurálnom jazyku. V prípade potreby spodnými indexami

odlíšime syntaktické výrazy. Bodkociarka oddeluje sémantickú interpretáciu

v postupnosti. Všimnime si, že sémantiku každého syntaktického

výrazu vyjadrujeme matematickým výrazmi obsahujúcimi aplikácie sémantických

funkcií na syntaktické výrazy alebo príkazy cielového jazyka

(v danom pripade podobnému jazyku Pascal).

 

Program [[ Program ]] interpretuje Program

Program [[ Stat Seq .” ]] = Stat Seq [[ Stat Seq ]] ; write(”STOP”)

 

Stat Seq [[ Stat Seq ]] interpretuje Stat Seq

Stat Seq [[ Stat0 { ”; ” Stati } ]] = Stat [[ Stat0 ]] ; { Stat [[ Stati ]] ; }

 

Stat [[ Stat ]] interpretuje Stat

Stat [[ input id<attr> ]] = write(”INPUT”); write(tid[attr], ”[”, attr, ”] : ”); read(mem[attr])

Stat [[ print Expr ]] = write(”PRINT”, Expr [[ Expr ]] )

Stat [[ id<attr> ” = ” Expr ]] = attr0 := attr; mem[attr0] := Expr [[ Expr ]] write(tid[attr0], ”[”, attr0, ”] = ”); write(mem[attr0])

 

Expr [[ Expr ]] interpretuje Expr

Expr [[ Mul1 “+“ Mul2 ]] =Mul [[ Mul1 ]] +Mul [[ Mul2 ]]

Expr [[ Mul1 Mul2 ]] =Mul [[ Mul1 ]] −Mul [[ Mul2 ]]

Mul [[ Mul ]] interpretuje Mul

Mul [[ Op1 ”*” Op2 ]] = Op [[ Op1 ]] _ Op [[ Op2 ]]

Mul [[ Op1 /Op2 ]] = Op [[ Op1 ]] / Op [[ Op2 ]]

 

Op [[ Op ]] interpretuje Op

Op [[ idhattri ]] = mem[attr]

Op [[ sconsthattri ]] = ctab[attr]

Op [[ ”(”Expr”)” ]] = Expr [[ Expr ]]

Definíciou gramatiky a sémantiky je návrh jazyka ukoncený a možno

prikrocit k jeho realizácii.

 

 

2. Lexikálna analýza

Lexikálna analýza je fáza prekladu, pri ktorej sú lexikálne jednotky atomizované

a podávané na vstup syntaktického analyzátora vo forme symbolov.

Lexikálny analyzátor je programový modul realizujúci lexikálnu analýzu.

 

2.1 Lexikálny analyzátor ako procedúra

Nasledujúci program v jazyku Pascal realizuje lexikálny analyzátor ako

procedúru getsymbol. Každé jej volanie precíta zo vstupu znak, alebo

retazec znakov, reprezentujúci lexikálnu jednotku a transformuje ho do

symbolickej formy. Hodnota symbola je uložená do premennej symbol, a

atribút symbola (v prípade konštanty a identifikátora) do premennej attr.

 

unit lex;

interface

procedure getsymbol;

{---- definicie pre lexikalnu analyzu ----}

const MAXIDL = 8; { max. dlzka identifikatora }

MAXIDS = 100; { max. pocet identifikatorov }

MAXNUMS = 100; { max. pocet konstant }

{ typ identifikatora v tabulke identifikatorov }

type TID_ITEM = string[MAXIDL];

var tid : record { tabulka identifikatorov }

                 n: integer;

                 tab: array[0..MAXIDS] of TID_ITEM;

              end;

var ctab : record { tabulka konstant }

                  n: integer;

                  tab: array[0..MAXNUMS] of integer;

                 end;

{ symboly identifikator, konstanta, (, ), =,

+, -, *, /, ;, ., eof, input, print }

 

type symbols = (sid,sconst,lpar,rpar,sassign, add,sub,smul,sdiv,semicolon,period,seof,sinput,sprint);

 

type KEYWORD = record

                                    kwstring:string[MAXIDL];

                                    syvalue :symbols;

                                    end;

const kwtab: array[0..1] of KEYWORD=(

(kwstring:’input ’;syvalue:sinput),

(kwstring:’print ’;syvalue:sprint));

 

var ch:char; { prave precitany znak}

geton:boolean; { ak true, potom precitat dalsi znak }

lexoff:boolean; { ak false, bol precitany symbol }

id:string[MAXIDL]; { prave nacitany identifikator }

cval:integer; { prave nacitana konstanta }

infile:text; { vstupny subor }

k: integer; { pomocna premenna }

{ ----------- volanie getsymbol poskytuje : }

var symbol: symbols; { symbol a pre id a sconst aj }

attr : integer; { jeho atribut }

 

implementation

procedure getsymbol;

procedure getchar;

{ citanie jedneho znaku.

transformacia znaku konca suboru na ’$’

a tabelatora a znaku konca riadku na

medzeru }

begin

if eof(infile) then begin

ch:=’$’

end else if eoln(infile) then begin

ch:=’ ’; readln(infile)

end else begin

read(infile,ch); if ch=chr(8) then ch:=’ ’;

end

end; { getchar }

begin { getsymbol }

repeat

if geton then begin

getchar

end;

geton:=true; lexoff:=false;

case ch of

’=’: symbol:=sassign; { specialny symbol }

’;’: symbol:=semicolon; { specialny symbol }

’.’: symbol:=period; { specialny symbol }

’$’: symbol:=seof; { specialny symbol }

’(’: symbol:=lpar; { specialny symbol }

’)’: symbol:=rpar; { specialny symbol }

’+’: symbol:=add; { operator }

’-’: symbol:=sub; { operator }

’*’: symbol:=smul; { operator }

’/’: symbol:=sdiv; { operator }

’0’..’9’: { konstanta }

begin

cval:= ord(ch)-ord(’0’);

getchar;

while ch in [’0’..’9’] do begin

cval:= cval * 10 + ord(ch)-ord(’0’);

getchar

end;

geton:=false; { ch uz obsahuje nasledujuci znak }

k:=0; symbol:=sconst;

while (k<ctab.n) and (cval<>ctab.tab[k])

do begin

k:=k+1

end;

if k<ctab.n then begin { najdena konstanta}

attr :=k

end else begin { nova konstanta }

ctab.tab[k]:=cval; ctab.n:=k+1; attr:=k

end { attr ukazuje na konstantu v ctab.tab }

end;

’A’..’Z’,’a’..’z’: { identifikator }

begin

id:=’ ’;

id[1]:=ch; k:=1; getchar;

while ch in [’A’..’Z’,’a’..’z’,’0’..’9’] do begin

k:=k+1; id[k]:= ch;

getchar

end;

geton:=false; { ch uz obsahuje nasledujuci znak }

k:=0;

while (k<2) and (id<>kwtab[k].kwstring)

do begin

k:=k+1

end;

if k<2 then begin { klucove slovo najdene }

symbol:=kwtab[k].syvalue

end else begin { hladanie identifikatora }

k:=0; symbol:=sid;

while (k<tid.n) and (id<>tid.tab[k])

2.2. TECHNOLÓGIA LEXIKÁLNEJ ANALÝZY 29

do begin

k:=k+1

end;

if k<tid.n then begin { najdeny identifikator}

attr :=k

end else begin { novy identifikator }

tid.tab[k]:=id; tid.n:=k+1; attr:=k

end { attr ukazuje na identifikator v tid.tab }

end

end;

’’’’: begin { citanie komentara }

getchar;

while ch<>’’’’ do begin

getchar

end;

lexoff:=true { treba citat symbol }

end;

’ ’: lexoff:=true; { prazdny znak }

else { nepripustny znak }

end; { case }

until not lexoff;

end; { getsymbol }

end.

 

2.3 Autonómny lexikálny analyzátor

Nasledujúci program je autonómnym lexikálnym analyzátorom, ktorý generuje

všetky symboly zdrojového textu programu. Autonómny lexikálny

analyzátor by mohol tvorit samostatný prechod, ktorý by generoval symboly

do docasného súboru, odkial by ich mohol cítat syntaktický analyzátor.

Konštrukcia viacprechodových prekladacov bola kedysi aktuálna z dôvodu

nedostatku pamäti, dnes toto nebezpecie nehrozí. Preto autonómny

lexikálny analyzátor je pomocným prostriedkom na samostatné testovanie

lexikálneho analyzátora pred realizáciou syntaktického analyzátora.

 

program lexout;

uses lex;

begin

assign(output,’prog.out’); rewrite(output);

assign(infile, ’prog.bas’ );

reset(infile);

{ inicializacia lex. analyzatora:

- znak treba citat,

- tabulky konstant a identifikatorov

su prazdne }

geton:=true; ctab.n:=0; tid.n:=0;

{------------------------------------}

repeat

getsymbol;

case symbol of

sassign : writeln(’assign’);

lpar : writeln(’lpar’);

rpar : writeln(’rpar’);

semicolon : writeln(’semicolon’);

period : writeln(’period’);

add : writeln(’add’);

sub : writeln(’sub’);

smul : writeln(’mul’);

sdiv : writeln(’div’);

sinput : writeln(’input’);

sprint : writeln(’print’);

sconst : writeln(’const ’,attr);

sid : writeln(’id ’,attr);

seof : writeln(’eof’);

else

end

until symbol=seof;

{------------------------------------}

close(infile) { uzavretie vstupneho suboru }

end.

 

 

 

 

 

 

Symboly, generované autonómnym lexikálnym analyzátorom pre program

v casti 1.5.1, sú pre ilustráciu v textovej forme. Postupnost generovania

je urcená stlpcami. Atribúty symbolov id a const sú indexy do

tabulky identifikátorov tid, resp. indexy do tabulky konštánt ctab.

input assign add print

id 0 const 1 id 0 lpar

semicolon semicolon rpar id 1

print id 0 div add

id 0 assign const 2 id 2

semicolon lpar add rpar

id 1 id 1 const 3 div

assign add semicolon const 0

const 0 id 2 print period

semicolon mul id 0 eof

id 2 id 2 semicolon

Možno si všimnút, že ak na vstup lexikálneho analyzátora dáme

text obsahujúci lexikálne jednotky, ktorých štruktúra je v súlade

s lexikálnou gramatikou a to v lubovolnom poradí, ignorujúc syntax

jazyka, takýto program je lexikálne správny. Napr. program

3 = = x y ; 56 x0 print + / je lexikálne správnym programom, nie

však program x=3 , y=4, pretože znak , (ciarka) je neprípustným znakom.

 

 

 

 

 

 

 

 

 

 

3. Syntaktická analýza, interpretácia a preklad

 

Programová realizácia fázy syntaktickej analýzy zhora nadol vo forme prechodu

– programového modulu v rekurzívnom jazyku je podmienená gramatikou,

ktorá definuje bezkontextový jazyk LL(1), t.j.

Na lavej strane každého pravidla je iba jeden neterminálny symbol,

co je príznakom bezkontextovosti jazyka.

Gramatika nie je rekurzívna zlava, co je príznakom jazyka LL.

V lubovolnom bode vetvenia možno pokracovat v odvodení na základe

jedného terminálneho symbolu vstupného retazca, co je príznakom,

že jazyk je jazykom LL(1).

Takáto syntaktická analýza sa nazýva syntaktickou analýzou zhora

nadol, pretože postup pri odvodení je presne urcený (predikovaný) aktuálnym

symbolom na vstupe – t.j. symbolom podaným lexikálnym analyzátorom

na základe volania procedúry getsymbol.

 

3.1 Konštrukcia syntaktického analyzátora

 

Syntaktický analyzátor možno konštruovat priamociarym prepísaním pravidiel

gramatiky jazyka LL(1) z EBNF do programu v rekurzívnom jazyk

(napr. Pascal alebo C), a to takto:

Neterminálnemu symbolu na lavej strane každého pravidla gramatiky

zapísanej v EBNF zodpovedá deklarácia procedúry.

Neterminálnemu symbolu na pravej strane každého pravidla zodpovedá

volanie procedúry.

Terminálnemu symbolu zodpovedá použitie procedúry getsymbol,

ktora precíta zo vstupného retazca další terminálny symbol.

Postupnosti symbolov na pravej strane každého pravidla zodpovedá

postupnost volaní procedúr uvedených v bode 1, 2 a 3.

Operácii sumy | a výrazu v hranatých zátvorkách [ a ] zodpovedá

príkaz vetvenia (napr. case, if, switch v jazykoch Pascal, resp C).

Vstup do príkazu vetvenia je bodom rozhodnutia.

Uzáveru {. . .} zodpovedá príkaz cyklu (napr. while, repeat, do v

jazykoch Pascal, resp C). Vstup do príkazu cyklu je bodom rozhodnutia.

Hlavný program volá procedúru reprezentujúcu zaciatocný symbol

gramatiky.

Body rozhodnutia sú extrémne dôležité pre rozšírenie syntaktického

analyzátora o zotavenie pri výskyte syntaktickej chyby, teraz ich ponechajme

bokom.

Pritom podla toho, aký je aktuálny symbol na vstupe, uskutocní sa

výber vetvy príkazu vetvenia, resp. rozhodne sa o dalšej iterácii cyklu. Ak

takéto rozhodnutie nie je jednoznacné, gramatika nie je gramatikou LL(1)

a treba sa vrátit k návrhu gramatiky LL(1).

Ak po vykonaní takto konštruovaného syntaktického analyzátora bude

vstupný retazec symbolov precítaný, potom tento retazec patrí do jazyka.

Ak vykonávanie neskoncí, alebo zhavaruje iným spôsobom, resp. ak skoncí,

ale celý retazec nebude precítaný, potom vstupný retazec nepatrí do jazyka.

Všimnime si, že postupnost pravidiel pri odvodení a strom odvodenia

sú dve ekvivalentné formy, ktoré charakterizujú odvodenie vstupného

retazca terminálnych symbolov zo zaciatocného symbolu gramatiky, t.j.

priebeh syntaktickej analýzy zhora nadol konkrétneho retazca na vstupe.

Tieto dve formy nemajú nic spolocné so sémantikou jazyka, ktorá definuje

preklad, resp. interpretáciu jazyka. Navyše, syntaktický analyzátor

zhora nadol nekonštruuje ani postupnost pravidiel, ani strom odvodenia

fyzicky, iba riadiacim tokom vyplývajúcim z postupnosti volaní procedúry

getsymbol a procedúr reprezentujúcich neterminálne symboly gramatiky.

 

Cielom prekladu je transformácia vstupného retazca symbolov v jazyku, z

ktorého prekladáme, do výstupného retazca symbolov zapísaných vo výstupnom

jazyku. Cielom interpretácie je transformácia vstupného retazca

do formy, v ktorej môže byt vykonaný. Aj preklad aj interpretácia sa opierajú

o definíciu sémantiky jazyka. Aj vykonanie kompilátorom preloženého

programu vo forme strojových inštrukcií je interpretáciou. Pretože je však

relizované na úrovni architektúry, nie je súcastou prekladaca.

Pretože denotacná sémantika definuje sémantiku syntaktických výrazov,

samozrejmým riešením pri konštrukcii prekladacov a interpretátorov

je obohatenie syntaktického analyzátora o pravidlá denotacnej sémantiky.

Hovoríme potom o preklade, resp. interpretácii riadených syntaxou.

Pretože preklad s následnou sémantickou analýzou je nepomerne zložitejší

ako interpretácia, ukážeme spôsob programovej realizácie

interpretátora, riadeného syntaxou.

 

 

3.2.1 Syntaxou riadený interpretátor

 

Nasledujúci program v jazyku Pascal realizuje syntaxou riadený preklad

a okamžitú interpretáciu jazyka definovaného gramatikou v casti 1.5.2,

ktorého sémantika je definovaná v casti 1.5.3.

Interpretátor využíva lexikálny analyzátor vo forme procedúry

getsymbol definovanej v jednotke lex, vid cast 2.

Možno si všimnút, že každá procedúra v interpretátore nie je už iba

zobrazením pravidla gramatiky EBNF, napr. ale aj príslušného sémantického

pravidla. Napr. expr nie je iba zobrazením Expr, ale aj Expr.

To umožnuje interpretátor vykonat takým spôsobom, že cíta (syntakticky

správne) programy zapísané v jednoduchom jazyku typu BASIC a

okamžite ich interpretuje v súlade s definovanou sémantikou prvkov tohto

jazyka.

 

 

 

program test;

uses lex;

{--------- definicie pre interpretaciu ---------}

const MAXMEM = MAXIDS; { velkost pamati premennych }

var mem : array[0..MAXMEM] of integer; { pamat premennych }

i : integer; { pomocna premenna }

 

function expr:integer;

var v1,v2:integer; sy:symbols;

 

function operand:integer;

begin

case symbol of

sconst : begin { sconst<attr> }

operand:=ctab.tab[attr];

getsymbol { dalsi symbol }

end;

sid : begin { sid<attr> }

operand:=mem[attr];

getsymbol { dalsi symbol }

end;

lpar : begin { ( }

getsymbol; { dalsi symbol }

operand:=expr; { ) }

getsymbol { dalsi symbol }

end;

else

end

end; { operand }

 

function mul:integer;

var v1,v2:integer; sy:symbols;

begin

v1:=operand;

while symbol in [smul,sdiv] do begin

sy:=symbol; { ulozenie * alebo / }

getsymbol; { dalsi symbol }

v2:=operand;

case sy of

smul : v1:=v1 * v2;

sdiv : v1:=v1 div v2;

end;

end;

mul:=v1

end; { mul }

 

begin { expr }

v1:=mul;

while symbol in [add,sub] do begin

sy:=symbol; { ulozenie + alebo - }

getsymbol; { dalsi symbol }

v2:=mul;

case sy of

add : v1:=v1 + v2;

sub : v1:=v1 - v2;

end;

end;

expr:=v1

end; { expr }

 

 

procedure stat;

var adr:integer;

begin

case symbol of

sinput: begin { input }

getsymbol; { dalsi symbol (sid<attr>) }

write(’INPUT ’,tid.tab[attr],

’[’,attr,’] : ’);

readln(mem[attr]);

{ citanie do mem[attr] }

getsymbol; { symbol (; alebo .) }

end;

sprint: begin { print }

getsymbol; { symbol zaciatku expr }

writeln(’PRINT ’,expr);

{ vypis hodnoty vyrazu }

end;

sid : begin { sid<attr> }

adr:=attr; { uchovanie adresy ciela }

getsymbol; { dalsi symbol (=) }

getsymbol; { symbol na zaciatku expr }

mem[adr]:=expr;

{ ulozenie hodnoty vyrazu }

writeln(tid.tab[adr],

’[’,adr,’] = ’,mem[adr]);

end;

else

end

end; { stat }

 

procedure statseq;

begin

stat; { ; alebo . }

while symbol = semicolon do begin

getsymbol; { dalsi symbol za ; }

stat

end;

end; { statseq }

 

procedure prog;

begin

statseq; { . }

getsymbol; { dalsi symbol seof }

writeln; writeln(’STOP’);

end; { prog }

 

begin

{ inicializacia pamati premennych }

for i:=0 to MAXMEM do begin

mem[i]:=0

end;

{ otvorenie vstupneho suboru ’prog.bas’ }

assign(infile, ’prog.bas’ );

reset(infile);

{ inicializacia lex. analyzatora:

- znak treba citat,

- tabulky konstant a identifikatorov

su prazdne }

geton:=true; ctab.n:=0; tid.n:=0;

getsymbol; { precitanie prveho symbolu }

prog; { start syntaktickeho analyzatora

a interpretacia programu prog.bas }

close(infile) { uzavretie vstupneho suboru }

end.