Правила задающие неоднозначность грамматик
Грамматика называется однозначной, если для нее можно построить единственный левосторонний или правосторонний вывод.
Однозначность – это свойство грамматики, а не языка.
Для KС языков сущ-т правила определения однозначности:
1) A -> AA | α
2) A -> A α A | β
3) A -> α A | A β | γ
4) A -> α A | α A β A | γ
Здесь А Î VN α, β, γ € (VNUVT)
Если в заданной грамматике встречается хотя бы одно правило подобного вида, то доказано, что такая грамматика точно будет неоднозначной. Однако, если подобных правил во всем множестве правил грамматики нет, то это не означает, что грамматика является однозначной. Такая грамматика может быть однозначной, а может и не быть. Т.е. отсутствие правил указанного вида (всех вариантов) – это необходимое, но не достаточное условие однозначности грамматики.
Распознаватель
Распознаватель – это специальный алгоритм, который позволяет определять принадлежность заданной цепочки символов данному языку.
Основные компоненты:
1. лента, содержащая входную цепочку символов, и считывающая головка, обозревающая очередной символ в этой цепочке;
2. устройство управления (УУ), которое координирует работу распознавателя (имеет конечное число состояний и огромную память);
3. внешняя память, которая используется для хранения информации.
Распознаватель работает с символами своего алфавита. В процессе работы выполняются следующие операции:
|
|
|
- чтение очередного символа из входной цепочки;
- сдвиг входной цепочки на определенное количество символов;
- доступ к внешней памяти для записи или чтения информации;
- преобразование информации в памяти;
- изменение состояния устройства управления.
Распознаватель работает по тактам. В начале такта состояние распознавателя определяется след-ми параметрами:
- содержимым входной цепочки символов и положением считывающей головки в ней;
- состоянием УУ;
- содержимым внешней памяти.
Для распознавателя задают начальное состояние (конфигурацию) и множество конечных состояний (конфигураций).
1. Считывающая головка обозревает начальный символ входной цепочки символов;
2. Устройство управления находится в заданном начальном состоянии;
3. Внешняя память либо пустая, либо содержит строго определенную информацию.
Классификация распознавателей осуществляется по составляющим элементам:
1. по виду считывающего устройства:
- односторонние - допускают перемещение считывающей головки по ленте только в одном направлении;
- двусторонние.
2. по виду УУ:
- детерминированный - для каждой допустимой конфигурации, которая возникла на некотором шаге его работы, существует единственно возможная конфигурация, в которую распознаватель перейдёт на следующем шаге;
|
|
|
- недетерминированный - имеет такие допустимые конфигурации, для которых существует конечное множество конфигураций возможных на следующем шаге работы.
3. по виду внешней памяти:
- без внешней памяти;
- ограниченная внешняя память;
- неограниченная внешняя память.
(Если автомат без внешней памяти, то используется память УУ)
Классификация распознавателей по типу языков:
1. Тип 0. Язык – с фразовой структурой
Распознаватель – двусторонние недетерминированные автоматы с неограниченной внешней памятью.
2. Тип 1. КЗ языки
Распознаватель - двусторонние недетерминированные автоматы с линейноограниченной внешней памятью.
3. Тип 2. КС языки
Распознаватель – односторонние недетерминированные автоматы с магазинной памятью.
4. Тип 3. Регулярные языки
Распознаватель - односторонние недетерминированные автоматы без ВП, конечные автоматы.
Задача разбора
Заключается в следующем, что на основе имеющейся грамматики некоторого языка, необходимо построить распознаватель этого языка.
Задача разбора не решается для всех языков.
Задача разбора решается с помощью следующих задач:
|
|
|
- определить смысловую нагрузку входной цепочки символов;
- определить правила, на основании которых построена цепочка;
- определить факт наличия ошибки, место и тип ошибки.
Этапы семантического анализа
1. проверка соблюдения во входной программе семантических соглашений входного языка.
Данная проверка заключается в сопоставлении входных цепочек программы, с требованием семантики входного языка программирования а:=в+с
2. дополнение внутреннего представления программы в компиляторе операторами, неявно предусмотренными семантикой входного языка.
Данные действия связаны с преобразованием типов операндов выражения и при передаче параметров процедур и функций.
3. проверка элементарных семантических норм языков программирования напрямую не связанных с входным языком.
Данная проверка является сервисной функцией, которую предоставляют большинство современных языков программирования. Выполнение данного согласования не является обязательным.
4. Идентификация лексических единиц языка.
Идентификация переменных, типов, процедур, функций и др. лексических языков программирования – это установление однозначности соответствия между данными объектами и их именами в тексте исходной программы.
Дата добавления: 2018-05-31; просмотров: 615; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!