Стр. 53 - Информационные структуры и их преобразование

Содержание 51
ИНФОРМАЦИОННЫЕ СТРУКТУРЫ И ИХ ПРЕОБРАЗОВАНИЕ
Синтаксический анализ «сверху вниз»
Любой контекстно свободный язык может быть принят некоторым
недетерминированным магазинным автоматом. Из недетерминированности
указанного автомата следует, что построенный на его основе синтаксический
анализатор контекстно свободного языка может осуществлять возврат к
предыдущему состоянию в процессе функционирования. Сам алгоритм
синтаксического разбора определяет вполне однозначный процесс, поэтому,
при возникновении необходимости выбора одной из возможных логических
ветвей, алгоритм выбирает и в дальнейшем следует всегда единственной из
возможных логических ветвей. Это означает, что, обнаружив ошибку выбора,
необходимо вернуться к моменту осуществления выбора, вновь осуществить
выбор и выполнить другое перемещение. Однако если на порождающую
язык грамматику были наложены определенные ограничения, а автомат
эффективно использует свой стек, то становится корректным применение
ряда хорошо изученных и отработанных приемов, позволяющих построить
эффективный синтаксический анализатор для такого языка. На практике все
реальные проекты языков программирования, безусловно, содержат все
необходимые ограничения, поскольку они получат практическую ценность
лишь в том случае, если будут поддержаны достаточно эффективными
компиляторами.
При решении задачи синтаксического разбора строки вида х=
=а1,а2…аnЄL(G)используют, как правило, один из двух основных методов.
Первый из них заключается в построении дерева вывода, корень которого
помечен символом S, а листьями являются узлы, помеченные символами
а1,а2…аn.
Так называемый LL- разбор относится к методам синтаксического
разбора типа «сверху-вниз». Для успешного LL- разбора предложений
некоторого языка на порождающую его грамматику должны быть наложены
строгие ограничения. И хотя практически это означает, что воспользоваться
методом LL- разбора можно лишь на подмножестве класса
детерминированных языков, он представляет значительный интерес, так как
заложенные в нем принципы использованы в большинстве современных
компиляторов.