2015-04-01
810
Так как деревья вывода в автоматной грамматике имеют одну и ту же структуру, то для восстановления вывода в заданной грамматике надо знать только последовательность нетерминалов в узлах дерева вывода.
Это последовательность совпадает с последовательностью состояний соответствующего автомата.
Пример: Язык для записи целых чисел.
Необходимо сконструировать язык, на котором записывается целое число, а транслятор переводит его в машинное представление. Примеры цепочек нашего языка: 102, -1489, +633.
Грамматика:
| S® ц C S® +A S® – B A ® ц C | B ® ц C C ® ц C C ® ð K K ® e ц – произвольная цифра (терминал). |
Дерево вывода для цепочки +124ð:
 |
Программа, моделирующая автомат, представляет собой распознаватель:
вход – дерево вывода,
выход – относится цепочка к данному автомату или нет.
Чтобы построить распознаватель, нужно сконструировать семантические вычисления (функции), которые выполняются при прохождении дуг графа.
Построение семантической функции зависит от того, какой смысл вкладывается в каждую цепочку.
|
|
|
Определим семантические функции для каждого перехода так, чтобы при движении под действием входной цепочки, последовательность вычислений давала выход, соответствующий смыслу данной входной цепочки.
Обозначения для примера:
z – переменная хранящая знак (1 или –1);
r – вспомогательная числовая переменная;
y – функция, переводящая машинное представление цифры в число.
| Функции автомата: y1: z = 1 y2: z = –1 y3: z = 1, r= y(ц) y4: r= y(ц) y5: r= r*10 + y(ц) y6: r= z*r | Пример +124ð: y1: z = 1 y4: r = y(‘1’) = 1 y5: r = 1*10 + y(‘2’) = 10 + 2 = 12 y5: r = 12*10 + y(‘4’) = 120 + 4 = 124 y6: r = 124*1= 124 |
Вопросы и упражнения
1. Постройте автоматную грамматику, распознающую цепочки:
стол, столы.
2. Постройте граф данного автомата. Является ли данный автомат детерминированным? Приведите примеры вариантов семантических функций для данного распознавателя.
