ВУЗ:
Составители:
42
ния по n-эквивалентным, мы будем увеличивать число классов эквивалентно-
сти. Прекратим этот процесс тогда, когда n+1-эквивалентное состояние совпа-
дет с n-эквивалентным. Каждый полученный класс эквивалентности и будет со-
стоянием нового минимизированного КА, эквивалентного исходному.
Рассмотрим конечный автомат, представленный на рисунке:
1
1
E
D
C
B
A
F
G
0
1
1
0
1
0
1
1 0
0
Можно вычислить, что состояния F и G недостижимы. Построим классы n-
эквивалентности для оставшихся состояний: 0. (ABC) (DE); 1. (A) (BC) (DE);
2. (A) (BC) (DE).
В результате будет получен следующий конечный автомат:
1, 0
0
BC
DE
A
1
7. Синтаксический анализ
После работы лексического анализатора дальнейшую обработку исходной
программы выполняет синтаксический анализатор. Перед синтаксическим ана-
лизатором стоят две основные задачи: проверить правильность конструкций
программы, которая представляется в виде уже выделенных слов входного язы-
ка, и преобразовать ее в вид, удобный для дальнейшей семантической обработ-
ки и генерации кода.
Иными словами, на этапе синтаксического анализа нужно установить,
имеет ли цепочка лексем структуру, заданную синтаксисом языка, а также за-
фиксировать эту структуру. Следовательно, снова надо решать задачу разбора:
дана цепочка лексем, и надо определить, выводима ли она в грамматике, опре-
деляющей синтаксис языка. Однако структура синтаксиса языка, представлен-
ного в виде таких конструкций как: выражения, описания, операторы и т.п., бо-
лее сложная, чем структура лексем. Поэтому для описания синтаксиса языков
программирования нужны более мощные грамматики, чем регулярные. Обычно
для этого используют укорачивающие контекстно-свободные грамматики
(УКС-грамматики). Грамматики этого класса, с одной стороны, позволяют дос-
Страницы
- « первая
- ‹ предыдущая
- …
- 38
- 39
- 40
- 41
- 42
- …
- следующая ›
- последняя »
