Алгоритмы распознавания КС-языков

Существует алгоритм, позволяющий для любой КС-грамматики проверить принадлежность произвольной цепочки терминальных символов языку, порождаемому этой грамматикой, и получить вывод этой цепочки.

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

Количество этих сентенциальных форм конечно.

Такого рода алгоритм действует по принципу полного перебора. Объем перебора может быть сокращен, если процесс порождения сентенциальных форм будет организован так, что станет возможным определить тупики в ходе перебора еще до получения сентенциальной формы нужной длины.

Переборные алгоритмы работают с возвратами и вследствие своей неэффективности мало пригодны для практического использования. Для организации перебора с возвратами используют стек — структуру данных, подчиняющуюся дисциплине «последним пришел — первым ушел» (LIFO — Last In First Out).

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

Для синтаксического анализа КС-языков используются как нисходящие (строящие дерево разбора от корня к листьям), так и восходящие алгоритмы.

Дата добавления: 2014-01-03