Википедија

Лексички анализатор

Лексичка анализа е процес во кој некој влез од низа од знаци (на пример изворниот код кај компјутерски програм) да произведе како излез низа од симболи наречени „лексички токени” или само „токени”. На пример, лексерите кај многу програмски јазици низата од знаци 123 abc ја делат на два токена: 123 и abc , празното место не се зема предвид. Целта на создавањето на токените е обично тие да се предадат на друга програма како што е расчленувачот (парсер).

Шема на лексер

За многу јазици правењето на лексичка анализа може да се направи во едно поминување - со читање на знак по знак од влезот. Но, многу комерцијални компајлери користат лексери напишани на рака (не автоматски генерирани) бидејќи во нив е возможно многу полесно да се интегрираат справувачи со грешки.

Лексерот или лексичкиот анализатор се состои од два дела: скенер и евалуатор. (Овие делови обично се интегрирани поради ефикасноста т.е. за да работат паралелно).

Во првата фаза, скенирањето, е засновано на детерминистички автомат. Тој ги енкодира информациите барајќи одредени токени. На пример токенот integer може да содржи некаква низа бројчени цифри. Во многу случаи првиот знак кој не е празно место може да се одреди за да се добие токенот кој следи, потоа влезот се обработува знак по знак сè додека не се стигне до знак кој не е прифатлив за таква секвенца.

Втората фаза, евалуацијата, кој ја ги поминува токените и им дава вредност т.е. создава стек на вредности. Токените комбинирани со нивните вредности потоа се даваат на расчленувачот.

На пример, во изворниот код на некој програм низата: 

net_worth_future = (assets - liabilities);

може да биде претворена во тек на лексички токени: 

NAME "net_worth_future" 
EQUALS 
OPEN_PARENTHESIS 
NAME "assets" 
MINUS 
NAME "liabilities" 
CLOSE_PARENTHESIS 
SEMICOLON

Иако е возможно, а понекогаш и пожелно да се пишуваат лексери, тие обично се генерираат од автоматски алатки. Овие алатки генерално прифаќаат регуларни изрази коишто ги опишуваат токените кои се дозволени на влез. Секој регуларен израз е проследен со продукција на лексичката граматика на програмскиот јазик којшто ги евалуира токените спојувајќи ги со регуларните изрази. Овие алатки можат да генерираат изворен код којшто може да биде компајлиран и извршен, или можат да конструираат табела на состојби за детерминистички автомат.

Пример за лексички анализатор

Ова е пример за скенер напишан во програмскиот јазик С. Симболите што ги препознава се:

'+', '-', '*', '/', '=', '(', ')', ',', ';', '.', ':=', '<', '<=', '<>', '>', '>='

Броеви: 0-9 {0-9} Идентификатори: a-zA-Z {a-zA-Z0-9} Клучни зборови: "begin", "call", "const", "do", "end", "if", "odd", "procedure", "then", "var", "while"

Скенирањето започнува со повикување на init_scan, со кое се предава името на изворната податотека. Ако изворната податотека успешно се отвори, тогаш расчленувачот ја повикува getsym последователно за сукцесивно да ги врати симболите од изворната податотека.

Срцето на скенерот, getsym, ги извршува акциите одејќи само нанапред. Прво, празните места се прескокнуваат, потоа знаците се класифицираат. Ако знаците претставуваат некој повеќезнаковен симбол тогаш треба да се направи некое дополнителна обработка. Броевите се претвораат во внатрешен облик, а идентификаторите се проверуваат за да се види дали имаат значење на некој клучен збор. 

int read_ch(void) {
 int ch = fgetc(source);
 cur_col++;
 if (ch == '\n') {
   cur_line++;
   cur_col = 0;
 }
 return ch;
}

void put_back(int ch) {
 ungetc(ch, source);
 cur_col--;
 if (ch == '\n') cur_line--;
}

Symbol getsym(void) {
 int ch;

 while ((ch = read_ch()) != EOF && ch <= ' ')
   ;
 err_line = cur_line;
 err_col  = cur_col;
 switch (ch) {
   case EOF: return eof;
   case '+': return plus;
   case '-': return minus;
   case '*': return times;
   case '/': return slash;
   case '=': return eql;
   case '(': return lparen;
   case ')': return rparen;
   case ',': return comma;
   case ';': return semicolon;
   case '.': return period;
   case ':':
     ch = read_ch();
     return (ch == '=') ? becomes : nul;
   case '<':
     ch = read_ch();
     if (ch == '>') return neq;
     if (ch == '=') return leq;
     put_back(ch);
     return lss;
   case '>':
     ch = read_ch();
     if (ch == '=') return geq;
     put_back(ch);
     return gtr;
   default:
     if (isdigit(ch)) {
       num = 0;
       do {  /* no checking for overflow! */
         num = 10 * num + ch - '0';
         ch = read_ch();
       } while ( ch != EOF && isdigit(ch));
       put_back(ch);
       return number;
     }
     if (isalpha(ch)) {
       Entry *entry;
       id_len = 0;
       do {
         if (id_len < MAX_ID) {
           id[id_len] = (char)ch;
           id_len++;
         }
         ch = read_ch();
       } while ( ch != EOF && isalnum(ch));
       id[id_len] = '\0';
       put_back(ch);
       entry = find_htab(keywords, id);
       return entry ? (Symbol)get_htab_data(entry) : ident;
     }

     error("getsym: invalid character '%c'", ch);
     return nul;
 }
}

int init_scan(const char fn[]) {
 if ((source = fopen(fn, "r")) == NULL) return 0;
 cur_line = 1;
 cur_col = 0;
 keywords = create_htab(11);
 enter_htab(keywords, "begin", beginsym);
 enter_htab(keywords, "call", callsym);
 enter_htab(keywords, "const", constsym);
 enter_htab(keywords, "do", dosym);
 enter_htab(keywords, "end", endsym);
 enter_htab(keywords, "if", ifsym);
 enter_htab(keywords, "odd", oddsym);
 enter_htab(keywords, "procedure", procsym);
 enter_htab(keywords, "then", thensym);
 enter_htab(keywords, "var", varsym);
 enter_htab(keywords, "while", whilesym);
 return 1;
}

Сега да го споредиме овој код со кодот потребен за Flex за истиот програмски јазик. 

%{
#include "y.tab.h"
%}

digit         [0-9]
letter        [a-zA-Z]

%%
"+"                  { return PLUS;       }
"-"                  { return MINUS;      }
"*"                  { return TIMES;      }
"/"                  { return SLASH;      }
"("                  { return LPAREN;     }
")"                  { return RPAREN;     }
";"                  { return SEMICOLON;  }
","                  { return COMMA;      }
"."                  { return PERIOD;     }
":="                 { return BECOMES;    }
"="                  { return EQL;        }
"<>"                 { return NEQ;        }
"<"                  { return LSS;        }
">"                  { return GTR;        }
"<="                 { return LEQ;        }
">="                 { return GEQ;        }
"begin"              { return BEGINSYM;   }
"call"               { return CALLSYM;    }
"const"              { return CONSTSYM;   }
"do"                 { return DOSYM;      }
"end"                { return ENDSYM;     }
"if"                 { return IFSYM;      }
"odd"                { return ODDSYM;     }
"procedure"          { return PROCSYM;    }
"then"               { return THENSYM;    }
"var"                { return VARSYM;     }
"while"              { return WHILESYM;   }
{letter}({letter}|{digit})* {
                      yylval.id = (char *)strdup(yytext);
                      return IDENT;      }
{digit}+             { yylval.num = atoi(yytext);
                      return NUMBER;     }
[ \t\n\r]            /* skip whitespace */
.                    { printf("Unknown character [%c]\n",yytext[0]);
                      return UNKNOWN;    }
 %%

 int yywrap(void){return 1;}

Околу 50 реда код за FLEX наспроти 100 реда на рачно напишан код. Обично скенерите не се тешки за пишување. Ако се напишани точно, рачно напишаните скенери можат да бидат побрзи и пофлексибилни од скенерите кои се направени со помош на генератор за скенер.

Наводи

уреди
Преземено од „https://mk.wikipedia.org/w/index.php?title=Лексички_анализатор&oldid=4889613“