Разработка компиляторов
Распознаватели для различных классов грамматик
Под распознавателем мы будем понимать обобщенный алгоритм, позволяющий определить некоторое множество (в нашем случае - язык) и использующий в своей работе следующие компоненты: входную ленту, управляющее устройство с конечной памятью и дополнительную рабочую память. Обычно считается, что управляющее устройство может только читать информацию, записанную на входной ленте (чтение производится с помощью входной головки, указывающей на текущий символ) и продвигаться по ней вперед и, возможно, назад. Распознаватель также может изменять состояние памяти, которая может быть организована как конечный линейный список ячеек или как стек (в русской литературе называемый также магазином). В качестве примеров распознавателей можно назвать машину Тьюринга, конечные и магазинные автоматы, которые должны быть известны студентам из предыдущих курсов.
Язык определяется путем задания некоторого множества допустимых заключительных состояний распознавателя: если цепочка, поданная на входную ленту, позволяет распознавателю выполнить последовательность шагов и остановиться в заключительном состоянии, то цепочка принадлежит языку.
Оказывается, каждому классу грамматик из иерархии Хомского соответствует класс распознавателей, определяющий тот же класс языков:
- Язык L праволинейный тогда и только тогда, когда он определяется (односторонним детерминированным) конечным автоматом
- Язык L контекстно-свободный тогда и только тогда, когда он определяется (односторонним недетерминированным) автоматом с магазинной памятью
- Язык L контекстно-зависимый тогда и только тогда, когда он определяется (двусторонним недетерминированным) автоматом с магазинной памятью
- Язык L рекурсивно перечислимый тогда и только тогда, когда он определяется машиной Тьюринга (этими понятиями мы оперировать не будем; формально они определяются в курсе "Вычислимость" или в базовом курсе "Компьютерные науки").
Дальнейший материал лекции будет посвящен определению свойств распознавателей, упомянутых в этих утверждениях, и обсуждению их применимости на практике.
