МГТУГА

Категории раздела

История воздухоплавания [31]
Системное программное обеспечение [55]
Сети 3-4 курс [41]
Методы и средства защиты информации [17]
Вычислительный системы [42]
про САПР [41]
Безопасность жизнедеятельности. БЖД. [46]
Интернет-технологии ГА [49]

Статистика


Онлайн всего: 3
Гостей: 3
Пользователей: 0

Форма входа

Каталог статей

Главная » Статьи » Системное программное обеспечение

59. Общие принципы организации синтаксического разбора. Назначение, классификация методов синтаксического разбора

59.  Общие принципы организации синтаксического разбора. Назначение, классификация методов синтаксического разбора.

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

·         чем сложнее синтаксис языка программирования, тем сложнее его грамматика;

  • чем сложнее грамматика, тем больше сложность и универсальность методов разбора;
  • универсальные методы разбора ведут к более медленному его выполнению.

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

 

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

Разбор предназначен для доказательства того, что анализируемая входная цепочка, записанная на входной ленте, принадлежит или не принадлежит множеству цепочек порождаемых грамматикой данного языка. Выполнение синтаксического разбора осуществляется распознавателями, являющимися автоматами. Поэтому данный процесс также называется распознаванием входной цепочки. Цель доказательства в том, чтобы ответить на вопрос: принадлежит ли анализируемая цепочка множеству правильных цепочек заданного языка. Ответ "да" дается, если такая принадлежность установлена. В противном случае дается ответ "нет". Получение ответа "нет" связано с понятиям отказа. Единственный отказ на любом уровне ведет к общему отказу.

Чтобы получить ответ "да" относительно всей цепочки, надо его получить для каждого правила, обеспечивающего разбор отдельной подцепочки. Так как множество правил образуют иерархическую структуру, возможно с рекурсиями, то процесс получения общего положительного ответа можно интерпретировать как сбор по определенному принципу ответов для листьев, лежащих в основе дерева разбора, что дает положительный ответ для узла, содержащего эти листья. Далее анализируются обработанные узлы, и уже в них полученные ответы складываются в общий ответ нового узла. И так далее до самой вершины. Данный принцип обработки сильно напоминает бюрократическую систему, используемую в организационном управлении любого предприятия. Так поднимается наверх информация, подтверждающая выполнение указания начальника организации. До этого, теми же путями, вниз спускалось и разделялось исходное указание.

Классификация методов синтаксического разбора.

Если попытаться формализовать задачу на уровне элементарного метаязыка, то она будет ставиться следующим образом. Дан язык L(G) с грамматикой G, в которой S - начальный нетерминал. Построить дерево разбора входной цепочки    a = a1a2a3...an.

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

На самом верхнем уровне выделяются:

·         методы разбора;

  • последовательность разбора;
  • использование просмотра вперед;
  • использование возвратов.
Категория: Системное программное обеспечение | Добавил: mgtuga (15.01.2009)
Просмотров: 2005 | Рейтинг: 0.0/0
Всего комментариев: 0
Имя *:
Email *:
Код *:

Поиск

Дисциплины