Принципы построения распознавателей КС-языков без возвратов

Общие принципы работы табличных распознавателей

Табличные распознаватели для КС-языков

Табличные распознаватели используют для построения цепочки вывода КС-грамматики другие принципы, нежели МП-автоматы. Как и МП-автоматы, они получают на вход цепочку входных символов a = а₁а₂…a_n, aÎVT^*, | a| = n, a по­строение вывода основывают на правилах заданной КС-грамматики G(VT,VN,P,S). Принцип их работы заключается в том, что искомая цепочка вывода строится не сразу — сначала на основе входной цепочки порождается некоторое промежу­точное хранилище информации объема n*n (промежуточная таблица), а потом уже на его основе строится вывод.

Табличные алгоритмы обладают полиномиальными характеристиками требуе­мых вычислительных ресурсов в зависимости от длины входной цепочки. Для произвольной КС-грамматики G(VT,VN,P,S) время выполнения алгоритма Т_э имеет кубическую зависимость от длины входной цепочки, а необходимый объ­ем памяти М_э — квадратичную зависимость от длины входной цепочки: a, aÎVT^*, n= |a|: Т_э = O(n³) и М_э= О(n²). Квадратичная зависимость объема необходимой памяти от длины входной цепочки напрямую связана с использованием проме­жуточного хранилища данных.

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

Выше были рассмотрены различные универсальные распознаватели для КС-языков — то есть распознаватели, позволяющие выполнить разбор цепочек для любого КС-языка (заданного произвольной КС-грамматикой). Они универсаль­ны, но имеют неудовлетворительные характеристики. Распознаватели с возвра­тами имеют экспоненциальную зависимость требуемых для выполнения алго­ритма разбора вычислительных ресурсов от длины входной цепочки символов, а табличные распознаватели — полиномиальную. Для практического примене­ния в реальных компиляторах такие характеристики являются неудовлетвори­тельными.

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

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

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

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

Однако следует всегда помнить, что проблема преобразования КС-грамматик алго­ритмически неразрешима. Если какая-то грамматика не принадлежит к требуе­мому классу КС-грамматик, это еще не значит, что заданный ею язык не может быть описан грамматикой такого класса. Иногда удается выполнить преобразо­вания и привести исходную грамматику к требуемому виду. Но, к сожалению, этот процесс не формализован, не поддается алгоритмизации и требует участия человека. Чаще всего такую работу вынужден выполнять разработчик компиля­тора (правда, выполняется она только один раз для синтаксических конструкций каждого языка программирования).

Существуют два принципиально разных класса распознавателей. Первый — нис­ходящие распознаватели, которые порождают цепочки левостороннего вывода и строят дерево вывода сверху вниз. Второй — восходящие распознаватели, кото­рые порождают цепочки правостороннего вывода и строят дерево вывода снизу вверх. Названия «нисходящие» и «восходящие» связаны с порядком построения дерева вывода. Как правило, все распознаватели читают входную цепочку симво­лов слева направо, поскольку предполагается именно такая нотация в написании исходного текста программ.

Нисходящие распознаватели используют модификации алгоритма с подбором альтернатив. При их создании применяются методы, которые позволяют одно­значно выбрать одну и только одну альтернативу на каждом шаге работы МП-автомата (шаг «выброс» в этом автомате всегда выполняется однозначно). Алго­ритм подбора альтернатив без модификаций был рассмотрен выше.

Восходящие распознаватели используют модификации алгоритма «сдвиг-сверт­ка» (или «перенос-свертка», что то же самое). При их создании применяются методы, которые позволяют однозначно выбрать между выполнением «сдвига» («переноса») или «свертки» на каждом шаге работы расширенного МП-автома­та, а при выполнении свертки однозначно выбрать правило, по которому будет производиться свертка. Алгоритм «сдвиг-свертка» без модификаций был рассмот­рен выше.

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