Лекция 6. 09/03/2004.
Лексический анализатор.
Лексический анализ – 1 этап процесса компиляции.
Программа разбивается на лексемы – отдельные минимальные значащие единицы.
Задачи лексического анализа:
-
выделить лексемы во входном тексте, проверить правильность их записи.
-
удалить пробельные литеры и комментарии.
-
преобразовать цепочку, представляющую лексему, в удобное представление – пару (тип_лексемы, указатель_на_информацию_о_лексеме).
-
фиксировать в специальных таблицах факты появлений лексемы в тексте программы
Существуют следующие классы лексем:
Числа, слова, ограничители (разделители), строковые константы.
Последовательности цифр преобразуются в число посредством схемы Горнера
t1, t2,………..,tn
А B
D1, D2, ………Dm - действия при переходе
А, В – состояния.
Синтаксис модельного языка:
P -> program D1; B _ \\конец цепочки
D1 -> var D {,D}
D -> I {,I} : [int | bool]
B -> begin S {,S} end
S -> I := E | if E then S else S | while E do S | B | read (I) | write (E)
E -> E1 [ = | < | > | <= | >= | != ] E1 | E1
- в книге отсутствие этого Е1 – опечатка
E1 -> T {[ + | - | or] T }
T -> F {[ * | / | and ] F }
F -> I | N | L | not F | (E)
- эти вышестоящие правила – правила синт. анализа
L -> true | false
I -> C | IC | IR - идентификаторы
N -> R | NR - правила выделения лексем
C -> a | b | …………| A | ……… | Z - буквы
R -> 0 | 1 | 2 …….. | 9 - цифры
{α} – те цепочки, которые внутри, могут быть повторены или ни разу, или любое количество раз.
αn, n >= 0
[ ] – в выражении языка используется одна из альтернатив внутри скобок.
[ ] и { } – метасимволы.
Приоритет операций задается правилами грамматики за счет порядка определения грамматики ( not выше, чем and и т.д.)
В данном случае нет усечённости условного оператора => нет однозначности.
Любой лексический анализатор строится по регулярной грамматике. Грамматика в примере не регулярна, но легко приводится к регулярной. Это сделано для упрощения.
В грамматике не отражено, что между любыми лексемами, составляющими язык, могут быть пробелы, и что в любом месте может быть комментарий.
(Обозначается {…}, в нем не может быть других {…} и символа конца программы &)
Принятое ограничение в компиляторе – он работает до первой ошибки.
Лексемы надо выделить и занести в таблицы, организованные в виде массивов.
1 – служебные слова - ΤW
2 – ограничители - TD
3 – константы - TNUM
4 – идентификаторы - TID
Перейдем к классовой структуре программы.
Рассмотрим класс лексем.
class lex {
int t_lex; //тип лексемы
int v_lex; //значение лексемы
//=> любая лексема представляется парой
public:
lex (nt t=0; int v=0;) {t_lex = t; v_lex = v;};
//- задаются начальные значения
int get_type ( ) {return t_lex};
int get_value ( ) {return v_lex}; //показывают тип и значение
bool is_keyword ( ) {return t_lex == 1;}
bool eq (const char *str); //сравнивает текущее значние с заданным параметром
void print ( ) {cout << ‘(‘<<�’,’<<�”);”;)
};
функция eq:
bool lex:: eq(const char *str) {
if (t_lex == 1) return !(strcmp (str,TW [t_lex]);
//т.е. если лексема – служебное слово
…………………………………………………………
{//работа лексического анализатора
…………………………………………..
……………. eq (“program”) …………...
//сравнение первой лексемы с “program”: если нет – выход
…………………………………………..}
if (t_lex==3) return atoi(str)==TNUM[v_lex];
идентификаторы:
class ident {
char *name;
bool declare; //описана переменная или нет
char *type;
bool assign;
int value;
public:
ident( ) {declare = false; assign = false;}
char * get_name( ) {return name;}
void put_name (const char * n) //задание имени
{ name = new char[strlen(n)+1];
strcpy (name,n);
//заносим значение через закрытое поле name
}
class table_ident {
int * p;
int size;
int top;
public:
(int max_size) {p=new ident[size=max_size]; top=1;}
~tabl_ident ( ) {delete[ ]p;}
//т.к. существует контекстный массив, нужно определить символ “[ ]”
ident & operator [ ] (int k) {return p[k];}
int put (const char * buf);
}
таблица имён
int tabl_ident :: put (const char * buf) {
for (int j=1; j
if (!strcmp (buf,p[j].get_name( )))
return j;
//если в таблице идентификаторов находим вновь встретившееся имя,
//оно выдаётся как информация о том, что имя встречалось/
//buf содержит имя, которое нужно поместить в таблицу
p[top].put_name(buf); top++;
return top-1;
}
таблица чисел:
class tabl_number {
ident * p;
int size;
int top;
public:
tabl_number (int max_size)
{p=new int [size=max_size]; top=1;}
~tabl_number ( ) {delete[ ] p;}
int & operator [ ] (int k) {return p[k];}
int put (int number);
};
int tabl_number :: put(int number) {
for (int j=1; j
if (number == p[j]) return j; //выводим индекс – место в таблице
p[top] = number; top++;
return top-1;
}
|
