Общие методы синтаксического анализа

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

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

Алгоритмы, рассматриваемые во втором разделе, носят табличный характер; это алгоритм Кока-Янгера-Касами и алгоритм Эрли. Они затрачивают емкость и время . Алгоритм Эрли работает для любой КС-грамматики и для него требуется время , если грамматика однозначная.

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

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

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