- •1. Постановка задачи
- •Исходные данные:
- •Описание синтаксиса входного языка:
- •Описание семантики входного языка:
- •Объявления и области действия
- •Операции.
- •Лексический анализ
- •Определение синтаксиса лексем
- •49 Таблица констант
- •Тестирование лексического анализатора
- •Описание кс-грамматики входного языка
- •Разбиение на подграмматики
- •Описание языка триад
- •Построение атрибутной транслирующей грамматики
- •Построение атрибутного дмп – процессора
- •Организация взаимодействия дмп-процессоров
Лексический анализ
Описание типов лексем
Рассматриваемые лексическим анализатором лексемы могут относиться к одному из следующих типов:
- Идентификаторы – пользовательские имена объектов программы.
- Константы – числовые или логические значения, указанные явно.
- Знаки операций – символы, обозначающие унарные и бинарные операции.
- Специальные символы – квадратные и круглые скобки, запятые и т.д.
- Разделители – пробелы и символы новой строки. Если в тексте программы, в каком- либо месте, может стоять хотя бы один разделитель, то в этом месте может стоять сколько угодно разделителей.
- Ключевые слова – зарезервированные идентификаторы, имеющие строго определённый смысл.
Токен |
Лексема |
Языковая конструкция |
WH |
while |
Ключевые слова |
IF |
if | |
EL |
else | |
GT |
goto | |
RD |
read | |
WR |
write | |
T |
true | |
F |
false | |
INT |
int | |
DB |
double | |
STR |
String | |
CH |
char | |
PKG |
package | |
IMP |
import | |
CLS |
class | |
VD |
void | |
NW |
new | |
NL |
null | |
MN |
main | |
LNG |
length | |
CONC |
concat | |
SUBST |
substring | |
REP |
replace | |
FND |
find |
ID |
<идентификатор> |
Идентификаторы |
Cconst |
1, 1000,-20 |
Целочисленная константа |
Rconst |
1.15 |
Вещественная константа |
Chconst |
‘f’ |
Символьная константа |
Stconst |
“test” |
Строковая константа |
IncDec |
++, -- |
Унарные арифметические операции |
PlusMin |
+, - |
Аддитивные арифметические операции |
Multi |
*, / |
Мультипликативные арифметические операции |
Not |
! |
Отрицание (логическая операция) |
LOR |
|| |
ИЛИ (логическая операция) |
LAND |
&& |
И (логическая операция) |
Comp |
>, <, < =, > = |
Отношения (логические операции) |
Ecvi |
= =, ! = |
Эквивалентность (логические операции) |
Assign |
= |
Операторы присваивания |
( |
( |
Открывающая круглая скобка |
( |
) |
Закрывающая круглая скобка |
[ |
[ |
Открывающая квадратная скобка |
] |
] |
Закрывающая квадратная скобка |
{ |
{ |
Открывающая фигурная скобка |
} |
} |
Закрывающая фигурная скобка |
; |
; |
Точка с запятой |
? |
? |
Вопросительный знак |
: |
: |
Двоеточие |
. |
. |
Точка |
, |
, |
Запятая |
Определение синтаксиса лексем
Определение автоматных грамматик, описывающих синтаксис лексем.
3. 2. 1. Классы литер, с помощью которых записываются программы на входном языке:
класс «буква»: a A … z Z _ $
класс «ноль»: 0
класс «цифра без нуля»: 1 2 3 4 5 6 7 8 9
класс «однолитерные разделители»: ; , + - * / ( ) [ ] ? : . ^
класс «литеры однолитерных и двулитерных разделителей»: < > = ! & |
3. 2. 2. Составление автоматных грамматик, описывающих синтаксис лексем:
Терминальными символами грамматики являются классы литер, а начальным символом грамматики – символ S.
Автоматная грамматика, описывающая синтаксис лексем «идентификатор» и «ключевое слово». Здесь “Буква” – класс «буква», “Цифра” – класс «цифра», “1” – класс, включающий все литеры, за исключением букв и цифр.
Правила грамматики:
S |
|
Буква Id |
Id |
|
Буква Id |
Id |
|
Цифра Id |
Id |
|
1 |
Автоматная грамматика, описывающая синтаксис лексемы «целая константа без знака». Здесь “Цифра” – класс «цифра без нуля» , “2” – класс, включающий все литеры, за исключением цифр , “Ноль” – класс «ноль»
Правила грамматики:
S |
|
Sign Ноль |
S |
|
Sign Цифра C |
Sign |
|
+ |
Sign |
|
- |
Sign |
|
2 |
C |
|
Цифра C |
C |
|
Ноль C |
C |
|
2 |
Автоматная грамматика, описывающая синтаксис лексемы «вещественная константа без знака». Здесь “2” – класс, включающий все литеры, за исключением цифр.
Правила грамматики:
S |
|
Sign Ноль |
S |
|
Sign Ноль . T |
S |
|
Sign Цифра C |
Sign |
|
+ |
Sign |
|
- |
Sign |
|
2 |
C |
|
Цифра C |
C |
|
. T |
T |
|
Цифра T |
T |
|
Ноль T |
T |
|
2 |
Автоматные грамматики, описывающие синтаксис лексем «однолитерный разделитель» и «двулитерный разделитель». Здесь “Знак” – классы «однолитерные разделители» и «литеры однолитерных и двулитерных разделителей», “3” – класс, включающий все литеры.
Правила грамматики:
однолитерные разделители:
|
S |
|
Знак L |
L |
|
3 |
лексема «<=» |
S |
|
< Next | |||||||
|
Next |
|
= E | |||||||
|
E |
|
3 | |||||||
|
|
|
|
| ||||||
|
|
|
| |||||||
|
|
|
|
лексема «>=» |
S |
|
> Next |
|
Next |
|
= E |
|
E |
|
3 |
лексема «! =» |
S |
|
Next = |
|
Next |
|
! E |
|
E |
|
3 |
лексема «&&» |
S |
|
& Next |
|
Next |
|
& E |
|
E |
|
3 |
лексема «||» |
S |
|
| Next |
|
Next |
|
| E |
|
E |
|
3 |
Структуры данных Статические таблицы: Составная таблица ключевых слов
1 WH
0 |
while |
2 IF
0 |
if |
3 EL
0 |
else |
4 GT
0 |
goto |
5 RD
0 |
read |
6 WR
0 |
write |
7 T
0 |
true |
8 F
0 |
false |
9 INT
0 |
int |
10 DB
0 |
double |
11 STR
0 |
String |
12 CH
0 |
char |
13 PKG
0 |
package |
14 IMP
0 |
import |
|
|
15 CLS
0 |
class |
16 VD
0 |
void |
17 NW
0 |
new |
18 NL
0 |
null |
19 MN
0 |
main |
20 LNG
0 |
length |
21 CON
0 |
concat |
22 SUBS
0 |
substring |
23 REP
0 |
replace |
24 FND
0 |
find |
25 таблица базовых типов
0 |
int |
1 |
double |
2 |
char |
3 |
String |
26 таблица унарных операторов
0 |
++ |
1 |
-- |
27 таблица аддитивных операторов)
0 |
+ |
1 |
- |
28 таблица мультипликативных операторов
0 |
* |
1 |
/ |
29 таблица операторов отрицания
0 |
! |
30 таблица операторов ИЛИ
0 |
|| |
31 таблица операторов И
0 |
&& |
32 таблица операторов отношения
0 |
> |
1 |
< |
2 |
>= |
3 |
<= |
33 таблица операторов эквивалентности
0 |
= = |
1 |
! = |
34 таблица операторов присваивания
0 |
= |
Составная таблица разделителей
35 (
0 |
( |
36 )
0 |
) |
37 [
0 |
[ |
38 ]
0 |
] |
39 {
0 |
{ |
40 }
0 |
} |
41 ;
0 |
; |
42 ?
0 |
? |
43 :
0 |
: |
44 .
0 |
. |
45 ,
0 |
, |
Кроме того есть 46 таблица атомарных символов.
Динамические таблицы
47 таблтца типов
Тип |
Базовый тип |
размер в байтах |
Int |
0 |
4 |
double |
1 |
8 |
char |
2 |
2 |
String |
3 |
… |
В таблицу типов изначально занесены базовые типы…. все типы пользователя добавляются в эту таблицу на этапе синтаксического анализатора. Каждому типу сопоставлен номер базового типа, которому он соответсвует. 48 таблица идентификаторов (ID)
|
идентификатор |
тип |
значение |
0 |
|
|
|
….. |
|
|
|
N |
|
|
|
если идентификатор – не относится к типам, то тип 4 (последний тип + 1) , а в значении может быть ссылка на базовый тип последовательность идентификаторов
идентификатор |
номер в таблице идентификаторов |
|
|
последовательность операторов
оператор |
номер в таблице операторов |
|
|
(таблица операторов формируется из совокупности таблиц операторов по приоритетам)