Automatizovaná tvorba kompilátorov

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

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

• GNU Bison
• YACC
• PERL (pomalý ale veľmi pružný, skôr na skriptové draft-compilery, parsery a interpretery)

Kompilácia

Ciele kompilácie

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

• Binárny kód (pre určitý druh mikroprocesora)
• P-kód
• do inej formy (XML, iný zdrojový jazyk, metajazyk)

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

Parsovanie

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

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"