Оптические вычисления - Арратуна Р.
Скачать (прямая ссылка):
подде-
п
П - предложение
СФ - фраза с су шест -вительным
ГФ - глагольная фраза Г - глагол
ПФ -фраза с предлогом ПР - предлог
Дерево может быть записано:
ПР
СФ
П (СФ, ГФ, (Г, СФ,
ПФ (ПР, СФ) Н
Робот Переместил Пирамиду На
Стол
СФа СФб ПР
Рис. 11,15, Изображение дерева синтаксического анализа,
Таблица 11.2. Примеры шагов анализатора синтаксиса типа "ситуация -
действие", "жди и смотри"
Буфер
Стек
Шаг
Ожидание
Б2
Б1
К1
К2
КЗ
Правило
7
8 9 Ю
11
12
Предл1' СФб Г СФа П
СФв Предл СФб Г П(СФа)
СФв Предл СФб Г ГФ
СФв Предл СФб ГФ(Г)
СФв Предл ГФ(Г, СФб)
СФв Предл ПФ(Г, СФб)
СФв
ПФ(Предл,
СФв)
ГФ(Г, СФб,
ПФ(Предл,
СФв))
ПФ (Предл)
ПФ(Предл,
СФв)
ГФ(Г, СФб)
ГФ(Г, СФб, ПФ (Предл, СФв)) П(СФа)
П(СФа, ГФ(Г, СФб, ПФ (Предл, СФв)))
П(СФа)
П(СФа)
П(СФа)
П(СФа) П(СФа)
ГФ(Г, СФб) П(СФа) ГФ(Г, СФб) П(СФа) П(СФа)
П(СФа)
Если К1 = П, Б1 = СФ, П1* тогда подсоединить Если К1 = П(СФ), Б1 = Г,
тогда образовать ГФ ПЗ Если Х1 = ГФ, Б1 - Г, тогда подсоединить ГФ2+
ЕслиК1=ГФ, Б1=СФ, тогда подсоединить ГФЗ Если Б1=Предл,
Б2 = СФ и К1 =
= ГФ(Г, СФ), тогда образовать ПФ ГФ4
Если К1 = ПФ, Б1 =
= Предл, тогда под- + соединить ПФ1 +
Если К1=ПФ, Б1=СФ, тогда подсоединить ПФ2 Если К1 = ПФ, Б1 - 0, тогда К1-
>-Б1 ПФЗ
Если К1=ГФ, Б1=ПФ) тогда подсоединить ГФ5 Если К1 = ГФ, Б1 = 0, тогда К1-
>-Б1 ГФ6'
Если К1 = П, Б1 = ГФ, тогда подсоединить П2
Если К1=П, БI = 0, тогда завершить П4
Образовать фразу предложения + Начинается глагольная фраза ± П -Связать
ГФ к П
Предл - сокращение от "предлог".
Начинается фраза с предлогом § - Подсоединить ПФ
404
Часть IV. Символьные вычисления и искусственный интеллект
реву фразы с предлогом (ПФ), сдерживая формирование начатых ранее
поддеревьев в КЗ и К2. Шаги 7 и 8 надстраивают поддерево ПФ. Правило,
запускаемое на шаге 9, дает возможность связать ПФ и ГФ, а 10 и 12 шаги
связывают ГФ с предложением П, что завершает построение полного дерева
синтаксического анализа.
На рис. 11.16 для примера, описанного в табл. 11.2 и на рис. 11.15,
показан потоковый граф, который может быть реализован в оптическом
перекрестном процессоре, аналогично случаю, изображенному на рис. 11.2.
Имеется 13 правил с именами, а именно: от S1 до S4, от ГФ1 до ГФ6 и от
ПФ1 до ПФЗ, имеются входы от буферных регистров и верхнего стекового
регистра. За каждый тактовый цикл для каждого из правил сравнивают
содержащиеся в нем образцы с подаваемыми на вход сигналами. В данном
примере две операции сравнения необходимы для ввода в действие любого
правила, кроме как для ГФ4, которое требует трех операций. Также
предполагается, что правила не требуют упорядоченного выполнения.
Упорядоченные правила могут быть выполнены путем перестроения схемы
соединений (как на рис. 11.7). Восемь правил, будучи введенными в
действие, вызывают такое переключение выходного триггера, которое
вызывает продвижение содержимого буферов, включая перенос данных из В1
вниз, в регистры К1. Правила S3 и ГФ4, если они будут активированы,
вызывают следующие операции: сдвиг стековых регистров вправо, генерацию
вершины для новой фразы и размещение ее в К1. Правила ГФ6 и ПФЗ, будучи
запущенными в действие, вызывают сдвиг стековых регистров влево, включая
передачу данных из К1 и В1. Запуск правила 4 указывает на завершение
синтаксического анализа и вызывает считывание заключительного варианта
дерева поиска.
11.8. Выводы
Оптика обладает потенциальной возможностью обеспечить высокий уровень
параллелизма обработки и высокую полосу частот, необходимую для
реализации сетей межэлементных соединений, требуемых для быстрых,
эффективных параллельных вычислений в широком диапазоне символьных и
цифровых алгоритмов обработки. ПМС больших размеров и обладающие высокой
скоростью могут стать реальностью уже в течение нескольких следующих лет.
Была предложена архитектура, использующая ПМС в качестве полностью
перестраиваемого перекрестного переключателя. Процессор позволил получить
высокую скорость обработки за счет предварительной организации цифровых и
символьных потоков данных и обеспечил малые времена прогона. Система
показала значительные преимущества по сравнению с альтернативными
подходами.
Потоковый г раф для анализа синтаксиса по схеме 'ситуация -действие, жди
и смотри'*
Создает новую фразу Переключение вправо ]
1 1 I П П I. 1 П
' Р РУР? Р (Р;С Р)(Р)(Р',Р)\Р}' Р Р
f] П2] [| П3~1 ?П4[ у ГФЛ] Г|гФ2| Г|ГФ|1 Г^ГФД] j ГФ5[^ГФб]^ПФ|]_^ПФ21
^ПФз| _[|
(b
ГФ^
Переключение
вправо
rj [ ппт
Р ; ' Р р) 'ЧР) ' Р . i Р : Р" ;к Р". Р, . Р.
Правила
Переключение влево
К1 ' В1 Переключение вправо Создает новую фразу
одное дерево синтаксического анализа Завершен
синтаксический анализ
?
*
Список Логически слов вход
Импульс проходит, если выходной с^гнап совпадает с записанным в памяти
шаблоном
Генерирует хранящийся в памяти образец, если поступает входной сигнал
Синхро-низация'
:м
в
Вентиль И
Список Логически слов вход
Синхро- С1 I низация-ъ/ * Логический->'v. J Обратный j j ситная , ,,
