Задание 3. Разработка распознавателя

[ список заданий ]

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

Цель работы

Закрепление принципов синтаксического разбора. Изучение методов анализа и преобразования контекстно-свободных грамматик. Приведение заданной вариантом грамматики к КС(1) виду. Написание и отладка программы, реализующей функции распознавателя.

Порядок выполнения

1. В соответствии с вариантом задания провести переработку диаграмм Вирта, определяющих структуру программы. Ввести вместо обозначений нетерминалов, удобных для пользователя идентификаторы, используемые в разрабатываемой программе.
2. Провести анализ и преобразование синтаксических диаграмм к КС(1) виду. Расставить альтернативные точки, соответствующие состояниям динамически порождаемых конечных автоматов.
3. Разработать программу распознавателя. Провести ее комплексное тестирование и отладку.

Сведения, необходимые для работы, представлены в лекциях по трансляторам:

• Тема 6. Общие принципы организации синтаксического разбора
• Тема 7. Применение автоматов с магазинной памятью для нисходящего разбора слева направо
• Тема 8. Использование динамически порождаемых автоматов для нисходящего разбора слева направо
• Тема 9. Применение диаграмм Вирта для построения КС(1) грамматик, используемых при нисходящем разборе слева направо
• Тема 10. Разработка синтаксических диаграмм для распознавателя DPL

Исходные тексты распознавателя DPL

Содержание отчета

1. Диаграммы Вирта, разработанные для создания распознавателя.
2. Исходные тексты разработанной программы.
3. Тесты, используемые для проверки правильной работы программы.
4. Протоколы тестирования программы распознавателя применительно к созданным тестовым примерам и комплексным тестам.

[ список заданий ]