Стр. 14 - Информационные структуры и их преобразование
Упрощенная HTML-версия
12
ИНФОРМАЦИОННЫЕ СТРУКТУРЫ И ИХ
ПРЕОБРАЗОВАНИЕ
E:=E+T|T эквивалентно E:=T{+T}
0
.
Классификация языков
Классификацию языков ввел Хомский. В терминах формальных
грамматик определяется 4 основных класса:
1)
грамматика типа 0 порождает язык с фразовой структурой
(естественные языки).
U
+
: = V
*
, где U
∈
V
∪Σ
, U
+
∈
{ V
∪Σ
}
+
.
2)
грамматика типа 1 – контекстно-зависимая или контекстно-
чувствительная.
xUy: = xuy , где U
∈
V, u
∈
{ V
∪Σ
}
+
.
3)
грамматика типа 2 – контекстно-свободная.
U: = u, где U
∈
V, u
∈
{ V
∪Σ
}
*
.
4)
грамматика типа 3 – регулярная (автоматная).
Q: = RT|T, где Q,R
∈
V, T
∈Σ
.
Языки, порождаемые автоматной грамматикой, получили название
регулярных множеств.
2. СКАНЕРЫ (ЛЕКСИЧЕСКИЕ АНАЛИЗАТОРЫ)
Сканер
представляет собой ту часть транслятора, которая читает
литеры исходной программы и строит из них слова (лексемы).
Подмножества формальных языков (синтаксический класс):
1.
Служебные слова.
2.
Целые числа.
3.
Разделители.
4.
Идентификаторы.
5.
Оператор.
Сущности языка можно разделить на пять подмножеств.
Этапы работы транслятора
лексический
синтаксический
генерация кода
ИП
определение
языка
проверка
правильности
структуры
