Реферат: Лабораторные работы по Теории вычислительных процессов и структур
Литература.
1. Бек Л. Введение в системное программирование. -М.: Мир, 1988.-448 с.
2. Компаниец Р.И., Маньков Е.В., Филатов Н.Е. Системное программи-
рование. Основы построения трансляторов.-СПб.: КОРОНА принт,
2000 .-256 с.
3. Шильд Г. Справочник программиста по С/С++.-М.: Издательский дом
«Вильямс», 2000.-448 с.
Министерство образования Российской Федерации
Саратовский государственный технический университет
Построение детерминированного синтаксического
анализатора.
методические указания к выполнению лабораторной
работы по курсу «Теория вычислительных процессов
структур» для студентов специальности ПВС
Составил доцент кафедры ПВС
Сайкин А.И.
Саратов, 2001 г.
1. Введение.
Данная лабораторная работа рассчитана на 4 аудиторных часа и ещё 4 часа самостоятельной работы для изучения литературы и оформление отчёта.
Объект исследования - синтаксический анализатор входных текстов, записанных на языке, порождаемых заданной контекстно-свободной (КС) грамматикой. Цель работы состоит в написании программы синтаксического анализатора, основывающегося на магазинном автомате.
Метод построения синтаксического анализатора основывается на применении грамматик типа LL(1), что позволяет решить задачу, используя детерминированный алгоритм.
Лабораторная работа выполняется в дисплейном классе. Результат представляет собой работающую программу, которая может анализировать любые тексты и сообщать об ошибках программирования.
2. Содержание работы.
Языки программирования описываются КС-грамматиками. Но описание языка с помощью КС-грамматики не является описанием алгоритма порождения предложений этого языка. Правила подстановки грамматики - это не последовательность предписаний, а совокупность разрешений, причём порядок применения правил в грамматике произволен, тогда как в алгоритме должен быть задан жёсткий порядок применения отдельных инструкций.
Получение алгоритмического описания процесса распознавания языка является одной из первоочередных задач при разработке блока синтаксического анализа транслятора.
Одним из способов описания алгоритма распознавания языка является задание его в виде некоторого распознающего устройства. Для КС-языков такими устройствами являются магазинные автоматы - автоматы с магазинной памятью.
Методов синтаксического анализа достаточно много, в данной работе применяется нисходящий синтаксический анализ, который в свою очередь порождает ряд проблем. Во-первых, необходимо из грамматики языка исключить леворекурсивные продукции, во избежание зацикливания в при работе анализатора. Вторая проблема состоит в выборе альтернативных продукций в заданной грамматике, что достигается за счёт заглядывания вперёд на несколько, в общем случае К символов. В-третьих, возникает проблема локализации ошибок. Компилятор должен локализировать место ошибки, помимо указания её наличия. Ошибка обнаруживается, когда все подходящие продукции грамматики использованы. Для локализации ошибки все альтернативы подходя?