Automatizovaná tvorba kompilátorov

z Wikipédie, slobodnej encyklopédie
Skočit na navigaci Skočit na vyhledávání

Tento článok hovorí o nástrojoch pre automatickú lexikálnu analýzu a syntaktickú analýzu a ich využití pri tvorbe kompilátorov.

Nástroje[upraviť | upraviť kód]

V praxi sa na tvorbu kompilátorov sa používaju tri jazyky:

Kompilácia[upraviť | upraviť kód]

Ciele kompilácie[upraviť | upraviť kód]

Kompilátor transformuje zdrojový kód do inej podoby. Tie môžu byť:

Prvá fáza kompilácie sa nazýva parsovanie.

Parsovanie[upraviť | upraviť kód]

Zdrojový text je dobre čitateľný pre človeka, ale nie pre počítač. Preto musí byť transformovaný do binárnej podoby, ktorá je dobre spracovateľná pre počítač.

Pred syntaktickou analýzou je prvým krokom lexikálna analýza.

Tokeny sú síce pre človeka čitateľné, ale sú príliš dlhé, zaberajú miesto v pamäti a ich spracovanie je pomalé.

Pri lexikálnej analýze sa hľadajú v zdrojovom kóde terminálne tokeny a priraďujú im čísla pre vnútornú reprezentáciu. Tieto čísla zaberajú v pamäti málo miesta a sú pre počítač rýchlejšie.

Terminálne tokeny sú napr.:

  • identifikátory,
  • číselné a reťazcové konštanty

Terminálne tokeny dostanú číselné identifikátory.

Na identifikáciu tokenov sa použíavajú regulárne výrazy.

Po lexikálnej analýze nasleduje samotné parsovanie. Tu sa najčastejšie používa metóda LALR, t. j. definujú sa sekvencie tokenov, ktoré sa nazývajú neterminálne tokeny.

Neterminálne tokeny sú napr.:

  • definície funkcií
  • výrazy
    • unárne, binárne, ternárne výrazy
    • volania funkcií
  • deklarácie a definície funkcií

Príklady[upraviť | upraviť kód]

Príklad jednoduchého jazyka, ktorý dokáže zapísať sčítanie, oočítanie a zátvorky.

///////////////////////////////////////////////
// definicia kodov pre tokeny
#token identifier = 1
#token integer = 2
#token asign = 3
#token plus = 4
#token brace_l = 5
#token brace_r = 6
#token brace_s_l = 7
#token brace_s_r = 8
#token minus = 9

/////////////////////////////////////////////
// ake su nase tokeny
[_a-zA-Z] := identifier    // meno premennej podla definicie v ANSI C
[1-9][0-9]* := integer     // cele cislo (integer)
"=" := asign
"(" := brace_l
")" := brace_r
[ \t\n] := whitespace    // tieto znaky budu ignorovane (medzery atd.)

Whitespace je preddefinovaný token. Slúži na vizuálnu štylizáciu zdrojového kódu užitočnú pre programátora. Pre kompilátor nemá význam a parser ho ignoruje.

Zo zdrojového kódu

totok = (254+(10-4))

tak dostaneme

1 3 5 2 4 5 2 9 2 6 6

kde 5,6 sú zátvorky

Každé číslo má za sebou aj reťazec (napr. 1 má totok', 2 má "=" a prvá 2 má "254"). Potom je na rade parser, ktorý tieto "tokeny" spracuje

Parser už priamo vytvára výrazy, aké potrebujeme

/**********************************************************
* Some very simple parser
=====================================*/
expression: xpr_assignment | xpr_plus | xpr_minus ;
xpr_assignment: identifier assign expression {use 1,3} ;
xpr_plus: number plus number {use 1,3} ;
xpr_minus: number minus number {use 1,3} ;

// slovo 'use' znamena, ze pouzi len urcite tokeny, napr 1. a 3. --> number a number a 
// ignoruj '-'

token xpr_assignemnt(strIdent, strXpr)
{
 shell.show("assign %s to \"%s\"", strXpr, strIdent);
}

token xpr_plus(strNum1, strNum2)
{
 shell.show("add %s to %s", strNum1, strNum2);
 return string(num(strNum1)+num(strNum2));
}

token xpr_minus(strNum1, strNum2)
{
 shell.show("subtract %s from %s", strNum2, strNum1);
 return string(num(strNum1)-num(strNum2));
}

pri hore uvedený zdrojový kód vypíše (v tomto poradí):

subtract 4 from 10
add 254 to 6
assign 260 to "totok"