Федеральное агентство по образованию

Государственное образовательное учреждение

высшего профессионального образования

Уфимский государственный авиационный технический университет

ПОСТРОЕНИЕ СИНТАКСИЧЕСКОГО АНАЛИЗАТОРА

Методические указания

к лабораторной работе по дисциплине

«Системное программное обеспечение»

Уфа 2008

Составитель Ю.Г. Строкина

УДК 004.43(07)

ББК 32.973-018.1(я7)

Построение синтаксического анализатора: Методические указания к лабораторной работе по дисциплине «Системное программное обеспечение» / Уфимск. гос. авиац. техн. ун-т.; Сост. Ю.Г. Строкина. − Уфа, 2008. − 31 с.

Лабораторная работа посвящена построению синтаксического анализатора, который является основной частью компилятора на этапе анализа.

Предназначены для студентов специальности 230101 «Вычислительные машины комплексы, системы и сети».

Табл. 4. Ил. 9. Библиогр.: 3 назв.

Рецензенты : канд. техн. наук, доц. Д.И. Кардаш;

канд. техн. наук, доц. Р.Н. Уразбахтин

© Уфимский государственный

авиационный технический университет, 2008

Содержание

Введение 4

ЛАБОРАТОРНАЯ РАБОТА 5

ПОСТРОЕНИЕ СИНТАКСИЧЕСКОГО АНАЛИЗАТОРА 5

1. Цель работы 5

2. Теоретическая часть 5

2.1. Анализатор многочленов 5

2.2. Умножение многочленов 12

2.3. Табличный LL(1) – анализатор 22

2.4. Табличный транслятор многочленов 24

2.5. Реализация стека 25

2.6. LL(1) – драйвер 27

3. Порядок выполнения работы 29

4. Контрольные вопросы 31

Список литературы 31

Введение

Синтаксический анализатор (синтаксический разбор) – это часть компилятора, которая отвечает за выявление и проверку синтаксических конструкций входного языка. В задачу синтаксического анализа входит:

• поиск и выделение синтаксических конструкций в тексте исходной программы;

• установка типа и проверка правильности каждой синтаксической конструкции;

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

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

К классу контекстно-свободных (КС) относятся грамматики, у которых не накладывается никаких ограничений на вид правых частей их правил, а левая часть каждого правила – единственный нетерминал.

Для проектирования языков программирования используются синтаксические диаграммы, которые играют роль схемы алгоритма.

В теоретической части данной лабораторной работы рассмотрены основные этапы построения синтаксического анализатора многочленов.

ЛАБОРАТОРНАЯ РАБОТА

ПОСТРОЕНИЕ СИНТАКСИЧЕСКОГО АНАЛИЗАТОРА

1. Цель работы

Целью лабораторной работы является закрепление теоретических знаний и приобретение практических навыков при построении синтаксического анализатора методом рекурсивного спуска.

2. Теоретическая часть

2.1. Анализатор многочленов

Пользуясь методом рекурсивного спуска, запрограммируем синтаксический анализатор многочленов. Будем считать, что анализатор должен просто отвечать на вопрос, является ли введенная пользователем строка правильно записанным многочленом.

2.1.1. Язык многочленов

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

199

Последний пример не содержит переменной x. Условимся считать такую запись правильным многочленом нулевой степени. Чтобы запись многочленов могла быть обработана компьютерной программой (транслятором), предусмотрим возможность записи символов без надстрочных показателей степени: .

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

Рис. 1. Синтаксическая диаграмма многочлена

Построим теперь диаграмму для нетерминала «Слагаемое». Одна ветвь должна соответствовать полному варианту слагаемого, когда присутствуют все его элементы: коэффициент, буква x, знак возведения в степень и сама степень. Другие ветви (обходные) должны позволять предусмотреть такие варианты слагаемого, когда нет коэффициента, буквы x и последующей степени, или только степени. При этом на диаграмме не должно появиться такого пути, пройдя по которому мы минуем как коэффициенты, так и x.

Рис. 2. Синтаксическая диаграмма слагаемого

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

Рис. 3. Синтаксическая диаграмма для целого и для цифры