- •6. Генерация команд в компиляторе 44
- •1. Языки и грамматики
- •1.1. Язык как множество
- •1.2. Порождающая грамматика
- •1.3. Процесс порождения
- •1.4. Классификация грамматик по Хомскому
- •1.5. Классификация языков по Хомскому
- •1.6. Задача распознавания цепочек языка
- •2. Принципы трансляции языков программирования
- •3. Лексический анализ
- •3.1. Конечный автомат
- •3.2. Построение детерминированного конечного автомата
- •3.3. Недетерминированный конечный автомат
- •3.4. Преобразование неоднозначной а-грамматики к однозначной
- •3.5. Удаление из грамматики бесполезных нетерминалов
- •3.6. Лексический анализатор
- •4. Синтаксический анализ
- •4.1. Дерево порождения для кс-грамматики
- •4.2. Автомат с магазинной памятью
- •4.4. Левая рекурсия и ее устранение
- •4.5. Преобразование кс-грамматики к обобщенной нормальной форме Грейбах
- •4.6. Детерминированный ll-разбор
- •5. Обратная польская строка, как промежуточная форма программы
- •5.1. Обратная польская строка для арифметических выражений
- •5.2. Генерация опс для арифметических выражений
- •5.3. Вычисление опс для присваиваний и арифметических выражений с индексами
- •5.4. Генерация опс для присваиваний и арифметических выражений с индексами
- •5.5. Опс для условных, циклических и составных операторов
- •5.6. Опс для стандартных операторов
- •5.7. Распределение памяти и описание переменных
- •5.8. Обработка ошибок
- •6. Генерация команд в компиляторе
- •6.1. Распределение памяти при генерации команд
- •6.2. Генерация команд для присваиваний и арифметических выражений
- •6.3. Генерация команд с индексными выражениями
- •6.4. Генерация команд сравнения и перехода
3.3. Недетерминированный конечный автомат
Среди правил перехода НКА для некоторых пар (a, qi) имеется по два или более правил перехода в различные новые состояния. Это значит, что КА должен на каждом шаге одновременно находиться в нескольких состояниях из всего множества возможных состояний, и каждый раз выполнять одновременный переход из всех этих состояний в новое множество состояний. Может случиться, что некоторые из возможных переходов попадают в тупики. Если же получится хотя бы один нетупиковый переход, то работа НКА продолжается. Цепочка, анализируемая НКА, считается распознанной, если она прочитана до конца, и если хотя бы одно из текущих состояний НКА является заключительным.
Таким образом, недетерминированность КА, возникающая при его построении из неоднозначной А-грамматики, означает, что одновременно отслеживаются несколько вариантов грамматического разбора, и для успешного распознавания достаточно, чтобы хотя бы один вариант разбора оказался успешным. При этом количество вариантов разбора не может превышать числа всех возможных состояний НКА, т.е. числа нетерминалов в А-грамматике.
Пример 2. А-грамматика задана правилами:
S → 0A| 1A, A → 0A| 1A| 0 | 1.
Здесь нетерминал S – начальный. Цепочки языка, порождаемого этой грамматикой, будут состоять из последовательностей нулей и единиц длиной не менее чем 2.
После изменения грамматика будет содержать правила:
S → 0A| 1A, A → 0A| 1A| 0R | 1R, R → ┴.
Табл. 2 содержит правила перехода НКА.
Табл. 2
-
0
1
┴
S
A
A
A
A/R
A/R
R
F
При поступлении на вход этого КА цепочки 010┴, состояния КА в процессе работы будут изменяться следующим образом:
S, A, (A,R), (A,R), F.
Здесь на 3-м шаге работы КА параллельно выполняются два действия:
(0,A) → (A,R) и (0,R) → ?
При этом второе действие попадает в тупик, однако работа КА продолжается, так как первое действие переводит КА опять в два состояния A и R. На 4-м шаге работы КА также параллельно выполняются два действия:
(┴, A) → ?, (┴, R) → F.
Первое действие приводит к тупику, а второе – к заключительному состоянию F. Так как цепочка прочитана вся, то она считается распознанной, т.е. цепочка принадлежит языку.
При входной цепочке 0┴ на втором шаге из состояния A возникнет тупик: для состояния A и входного символа ┴ перехода не задано. Это значит, что такая цепочка не принадлежит языку. Аналогичная ситуация возникнет и для входной цепочки 1┴.
Конец примера.