Компиляторы. Формальные языки и грамматики. Распознаватели.

Распознаватели могжно классифицировать в зависимости от вида составляющих их компонентов (считывающее у-во, УУ, внешняя память).

По видам считывающего у-ва распознаватели могут быть двусторонними и односторонними. По видам УУ распознаватели могут быть детерминированные и недетерминированные. Распознаватель называется детерминированным в том случае, если для каждой допустимой конфигурации распознавателя, которая возникла на некотром шаге его работы, существуют единственно возможная конфигурация, в которую распознаватель перейдет на следующем шаге работы. Иначе распознаватель называется недетерминированным, т.е. такой распознаватель может иметь допустимую конфигурацию для которой существует некоторое конечное множество конфигураций, возможных иметь на следующем шаге работы. Достаточно иметь хотя бы одну такую конфигурацию, чтобы распознаватель был недетерминированным. По видам внешней памяти распознаватели бывают след типов: 1)Распознаватели без внешней памяти; 2)Распознаватели с ограниченной внешней памятью; 3)Распознаватели с неограниченной внешней памятью.

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