Lexikální analýza

transcript

Lexikální analýza

Miroslav Beneš

Dušan Kolář

Lexikální analýza 2

Rozhraní lexikálního analyzátoru

Úkoly

Čtení zdrojového textu Sestavování symbolů Odstranění mezer a poznámek Normalizace symbolů (velká/malá písmena,

spec. znaky, ...) Interpretace direktiv překladače Uchovávání informací pro hlášení chyb Zobrazení protokolu o překladu

Proč řešit lexikální analýzu samostatně?

Jednodušší návrh překladače Konvence pro mezery a poznámky

Vyšší efektivita Specializované algoritmy

Lepší přenositelnost Zvláštnosti vstupní abecedy ??( = [

Základní pojmy

Lexém – slovo nad abecedou Kategorie symbolů – identifikátor, číslo,

relační operátor, levá závorka, ... Atributy symbolu – řetězec, hodnota, kód

operátoru, ... Reprezentace symbolu – dvojice (kategorie,

atribut)

Příklady lexikálních symbolů

Symbol Lexém Vzor

const const const

relation <, <=, …, >= <>

id {ltr}({ltr}|{dig})* pi, D2

num {dig}+ 0, 123

Reprezentace symbolů// kategorie symbolůenum Symbol { IdSym, NumSym, RelOpSym, DotSym, ... };

// kategorie operátorůenum Oper { LthOp, GthOp, LeqOp, ... };

// atributy symbolůunion LexAttr { char* id; int num; Oper relop; ...};

// reprezentace lexikálního symbolustruct Token { Symbol sym; // kategorie LexAttr attr; // atribut};

Problémy se zdrojovým jazykem

Pevný/volný formát (FORTRAN) 12 X=7 * +12*K C poznámka

Zpracování mezer (FORTRAN, Basic) DO5I=1.25 / DO5I=1,25

Klíčová slova (PL/I) IF THEN THEN THEN=ELSE; ELSE ELSE=THEN

Příklad

1 INTEGER FUNCTIONA 2 PARAMETER(A=6,B=2) 3 IMPLICIT CHARACTER*(A-B)(A-B) 4 INTEGER FORMAT(10),IF(10),DO9E1 5 100 FORMAT(4H)=(3) 6 200 FORMAT(4 )=(3) 7 DO9E1=1 8 DO9E1=1,2 9 IF(X)=1 ...

Příklad (pokr.)

10 IF(X)H=1 11 IF(X)300,200 12 300 CONTINUE 13 END C this is a comment $FILE(1) 14 END

Specifikace symbolů

Popis běžným jazykem ‘identifikátor je posloupnost písmen a číslic

začínající písmenem’ Regulární (lineární) gramatika

I -> p X X -> p X | c X | p | c

Regulární výrazy a definice p (p | c)*

Graf přechodů konečného automatu (syntaktický graf)

Lexikální symboly lze obvykle popsat regulárními jazyky (typ 3)

Co nedokážeme popsat? Zanořené konstrukce (závorky) Opakované konstrukce {wcw|w{a,b}*} Zadaný počet opakování

nHa1a2…an (FORTRAN)

Regulární výrazy nad

RE označuje {} (prázdný řetězec) Je-li a, pak a označuje {a} Je-li a,b,c,…, pak [abc…] označuje

množinu {a, b, c, …} [aeiouy] [a-zA-Z] [^0-9] – všechno kromě [0-9]

Regulární výrazy

Jsou-li s, t reg. výrazy označující jazyky L(s) a L(t), pak (s) | (t) L(s) L(t) (s) (t) L(s) L(t) (s)* (L(s))* (s)+ (L(s))+ = L(s) (L(s))* (s)? L(s) {} (s) L(s)

Příklad

[A-Z]([A-Z]|[0-9])* [A-Z][A-Z0-9]* [0-9]+.[0-9]+(E[-+]?[0-9]+)?

| [0-9]+E[-+]?[0-9]+

Regulární definice

Pojmenované regulární výrazy d1 -> r1

d2 -> r2

dn -> rn

různá reg. výrazy nadjména {d1, d2,…, di-1}

Regulární definice

letter -> [A-Za-z] digit -> [0-9] id -> letter (letter | digit)*

Použití: konstruktory lex. analyzátorů

Konečné automaty

(Q, , f, q0, F) Q – konečná množina stavů - vstupní abeceda f – přechodová funkce q0 – počáteční stav F – množina koncových stavů

f: Q x ( {e}) -> 2Q rozšířený NKA f: Q x -> Q DKA

Konečné automaty

desítkové číslo

šestnáctkové číslo

Konečné automaty

deterministický konečný automat

Algoritmy pro transformaci

Reg. gramatika ↔ konečný automat korespondence pravidel gramatiky a přechodové

funkce Reg. výraz → konečný automat

skládání primitivních KA, převod na DKA, minimalizace

stromová reprezentace důležité pro konstruktory lex. analyzátorů

Algoritmy pro transformaci

Konečný automat → reg. výraz soustava algebraických rovnic

X = a X + b X = a* b derivace reg. výrazu

Konečný automatpro lexikální analýzu

Zpracování začíná vždy prvním dosud nezpracovaným znakem ze vstupu

Zpracování končí, je-li automat v koncovém stavu a pro další vstupní znak již neexistuje žádný přechod (maximal match): 123 není 12 následované 3

Není-li v nekoncovém stavu přechod možný, vrací se automat do posledního dosaženého koncového stavu nebo je chyba: < <= << 1. 1.2 1..5

Speciální případy

akce po přijetí symbolu samostatný koncový stav pro každou kategorii výpočet hodnot atributů z lexému

klíčová slova koncový stav pro každé klíčové slovo – mnoho

stavů obvykle jako id, pak následuje rozlišení tabulkou

klíč. slov

Speciální případy

komentáře uzavřená cesta procházející poč. stavem diagnostika – neukončený komentář dokumentační komentář – Javadoc zanořené komentáře

znakové řetězce escape sekvence ‘\n’ ukončení řádku v řetězci je obvykle chyba Unicode

Implementace lexikálního analyzátoru Přímá

Efektivita na úkor složitosti návrhu Stav je reprezentován pozicí v programu

Simulace konečného automatu Vhodné spíš pro konstruktory

Využití konstruktoru Snadná modifikovatelnost Především v počátečních fázích implementace

Přímá implementace

char text[256];

int leng, ival;

int lex(void) {

int ch;

START:

while((ch=getchar())==‘ ‘) ;

/* odstranění mezer */

if( isalpha(ch) ) {

leng = 0;

text[leng++] = ch;

} while( isalnum(ch=getchar()) );

text[leng] = ‘\0’;

ungetc(ch,stdin);

return(IDENT);

else if( isdigit(ch) ) { ival = 0; do { ival = 10*ival+(ch-’0’); } while( isdigit(ch=getchar()) );

ungetc(ch,stdin); return(NUM); }

else if (ch==‘{‘) {

while( (ch=getchar())!=‘}’ && ch!=EOF);

if( ch==EOF ) {

error(“Missing end of comment”);

return(EOF);

goto START;

else return(ch); /* ostatní znaky */

getchar() čte znaky ze vstupu udržuje aktuální číslo řádku kopie zdrojového textu do protokolu správa vyrovnávacích pamětí makrogenerátor (např. C, C++)

ungetc() vrací zpět jeden nebo více znaků Java: java.io.PushbackInputStream

Implementace konečného automatu

Tabulka + Přechodová funkce + Interpret výhodné jako výstup konstruktoru

Přímý přepis do programu

static int state;

int next(int newstate) { state = newstate; return getchar();}

int lex(void) { int ch = next(0);

for(;;) switch(state) { case 0: if (ch==‘ ‘) ch = next(0); else if( isalpha(ch) ) { leng = 0; text[leng]=ch; ch = next(1); }

/* case 0: */ else if (isdigit(ch)) { ival = ch-’0’; ch = next(2); } else if (ch==‘{‘) ch = next(3);

else return(ch); break;

case 1:

if (isalnum(ch)) {

text[++leng] = ch;

ch = next(1);

else {

text[++leng] = ‘\0’;

unget(ch,stdin);

return(IDENT);

break;

case 3:

if (ch==EOF) {

error(“Missing end of comment”);

return(EOF);

else if (ch==‘}‘) ch = next(0);

else ch = next(3);

break;

Konstruktor LEX / FLEX

#include <stdlib.h>

#define IDENT 256

#define NUM 257

int yyival;

space [ \t\n]

ws {space}+|\{[^}]*\}

letter [A-Za-z]

digit [0-9]

id {letter}({letter}|{digit})*

number {digit}+

{ws} {/* no action, no return */}

{id} return(IDENT);

{number} {

yyival=atoi(yytext);

return(NUM);

. return(yytext[0]);

Lexikální analýza

Documents