[25.04.11] Лекция №11 (Конспекты - Теория формальных языков)

Лекция №11 [25.04.11]

Методы синтаксического анализа

, грамматика, порождающая язык

- слово. И вот принадлежит ли оно языку ?

Используем МП-автомат. Но в нём неправильный выбор команды может привести к попаданию автомата в тупиковую конфигурацию даже в том случае, когда слово принадлежит . Сделать МП-автомат в общем случае детерминированным невозможно.

Надо превратить МП-автомат из распознавателя в анализатор, дополнив его механизмом управления выводом, который должен однозначно определять, какую команду МП-автомата следует применять к данной конфигурации для получения безтупикового вывода.

Вообще, никто не запрещает сделать алгоритм, работающий и при наличии тупикового вывода – можно возвращаться на развилку, после которой можно попасть в тупик. Короче, просто перебор всех возможных деревьев вывода. Или построить граф и выполнить поиск в глубину. Но это всё очень трудоёмко и никто не обещал, что число выводов конечное.

Безтупиковый анализ невозможен для произвольного КС-языка. Теоретический, типа, факт. Однако, существуют классы КС-языков, для которых такой анализ возможен. При нисходящем анализе дерево вывода цепочки восстанавливается от корня к листьям. А при восходящем – от листьев к корню (цепочка сворачивается в аксиому)

Нисходящий анализ -грамматики

Пусть у нас есть КС-грамматика . Построим по ней МП-автомат. На каждом шаге работы МП-автомата осуществляется моделирование левого вывода (при котором правило вывода применяется к самому левому вхождению нетерминала в цепочку) цепочки в грамматике .

Существует класс грамматик, называемых -грамматики, в котором применяемая на каждом шаге команда однозначно определяется:

1) прочитанной частью входной цепочки (левый контекст);

2) нетерминальным символом , находящимся в данный момент в верхней ячейке магазина;

3) началом непрочитанной цепочки , состоящей не более чем из букв, этот префикс называют аванцепочкой;

Для -грамматики, строится управляющая таблица, которая по пунктам 1, 2, 3 однозначно указывает правило, которое надо применять.

,

,

, , - аванцепочка

поскольку применяется левый вывод, то цепочка состоит только из терминальных символов (или пустая). Нужно определить некоторое свойство цепочки .

Для цепочки в объединенном алфавите определим множество:

Пример:

цепочки длины 3 (для примера):

это мы смотрели из аксиомы:

1 правило:

2 правило: , заменяя можно получить

3 правило: , то же, что и во втором

4 правило: , заменяя можно получить

Короче, мы выяснили, какие нетерминальные цепочки выводятся. И из них нашли трёхбуквенный префикс, с которого они начинаются. Было бы двух, искали бы двух. Это я не очень понял, кстати. По ходу, начинаем с максимальной длины, нам же нужен максимально большой префикс. Наверное. А вот ещё что есть:

КС-грамматику стандартного вида называют -грамматикой для , , , если

и из

Теорема: КС-грамматика для фиксированного является -грамматикой тогда и только тогда, когда для любой цепочки выполняется условие:

, : , , ,

Пример:

Число заранее неизвестно, и поэтому данное условие проверяют, последовательно увеличивая .

Возьмём

Сначала для :

(формально), ,

что-то тут не то

смотрим , , тогда

Теперь для :

что-то тут не то

пересечение не пустое, значит, данная грамматика не является -грамматикой

Возьмём

Для :

(формально), ,

пересечение пустое, значит, для условие выполняется