Системное программное обеспечение: Основы трансляции. Карпушин А.Н - 19 стр.

UptoLike

ВУЗ: 

УлГТУ | Ульяновск

Составители: 

Рубрика: 

21
для каждого из указанных выше 4-х типов языков существует свой тип распо-
знавателя с определенным составом компонентов и, следовательно, с заданной
сложностью алгоритма работы.
Для языков с фразовой структурой (тип 0) необходим недетерминирован-
ный двусторонний автомат, имеющий неограниченную внешнюю память.
Поэтому для языков данного типа нельзя гарантировать, что за ограниченное
время на ограниченных вычислительных ресурсах распознаватель завершит ра-
боту и примет решение о том, принадлежит или не принадлежит входная це-
почка заданному языку. В связи с этим, практического применения языки с
фразовой структурой не имеют.
Для контекстно-зависимых языков (тип 1) распознавателями являются
двусторонние недетерминированные автоматы с линейно ограниченной внеш-
ней памятью. Алгоритм работы такого автомата в общем случае имеет экспо-
ненциальную сложность – количество шагов (тактов), необходимых автомату
для распознавания входной цепочки, экспоненциально зависит от длины этой
цепочки. Следовательно, и время, необходимое на разбор входной цепочки по
заданному алгоритму, экспоненциально зависит от длины входной цепочки.
Такой алгоритм распознавателя уже может быть реализован – зная длину
входной цепочки, всегда можно сказать, за какое максимально возможное вре-
мя будет принято решение о принадлежности цепочки данному языку и какие
вычислительные ресурсы для этого потребуются. Однако экспоненциальная за-
висимость времени разбора от длины цепочки существенно ограничивает при-
менение распознавателей для контекстно-зависимых языков. Как правило, та-
кие распознаватели применяются для автоматизированного перевода и анализа
текстов на естественных языках, когда временные ограничения на разбор текста
несущественны (поскольку естественные языки более сложны, чем контекстно-
зависимые, то после такой обработки часто требуется вмешательство человека).
В компиляторах контекстно-зависимые распознаватели не применяются,
поскольку скорость работы компилятора имеет существенное значение, а син-
таксический разбор текста программы можно выполнять в рамках более про-
стого, контекстно-свободного типа языков.
Для контекстно-свободных языков (тип 2) распознавателями являются од-
носторонние недетерминированные автоматы со стековой внешней памятью.
При простейшей реализации алгоритма работы такого автомата он имеет экс-
поненциальную сложность, однако путем некоторых усовершенствований ал-
горитма можно добиться полиномиальной зависимости времени, необходимого
на разбор входной цепочки, от длины этой цепочки. Следовательно, можно го-
ворить о полиномиальной сложности распознавателя для КС-языков.
Среди всех КС-языков можно выделить класс детерминированных
КС-языков, распознавателями для которых являются детерминированные ав-
томаты со стековой внешней памятью. Эти языки обладают свойством одно-
значности – доказано, что для любого детерминированного КС-языка всегда
можно построить однозначную грамматику. Кроме того, для таких языков су-
ществует алгоритм работы распознавателя с квадратичной сложностью. По-

Страницы