Комбинированные алгоритмы предполагают совмещение этих двух стратегий. Эти алгоритмы обладают более высокой производительностью, чем нисходящие, и применимы к рекурсивным грамматикам с эллиптиче- скими НС.
Порядок построения НС тремя видами алгоритмов в предложении Мама мыла раму изображён на рисунке 3 (здесь изображена работа более простого в реализации поиска «в глубину», при поиске «в ширину» поря- док меняется). Следует отметить, что НС «ГГ» при реализации восходя- щего или комбинированного алгоритма встраивается в НС «Предложение» только после шага 10, т. е. когда все её дочерние позиции заполнены.
Рис. 3. Порядок работы нисходящих, восходящих и комбинированных алгоритмов
Рассмотрим пример простейшей НС-грамматики и одной из возмож- ных дериваций.
Грамматика:
Предложение (П) → Именная группа (ИГ) + Глагольная группа (ГГ)
ИГ → форма имени существительного (С)
С → Мама
С → раму
ГГ → ГГ + ИГ
ГГ → форма глагола (Г)
Г → мыла.
Деривация (в скобках между стрелками указаны номера правил грамматики):
Достарыңызбен бөлісу: |
