Студопедия

Главная страница Случайная страница

Разделы сайта

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






Общий алгоритм работы синтаксического анализатора






Синтаксический анализатор работает, опираясь на построенную матрицу предшествования. На его вход поступает обработанный сканером текст исходной программы. Каждый идентификатор или константа представляются для него некоторым терминальным символом (в примере он обозначен как p, в задании - a). Тогда первым шагом общего алгоритма анализа должно являться построение таблицы лексем (что уже выполнялось в предыдущей работе).

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

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

 

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

Пример 3. Входная цепочка -p^p& p.

E ® - E ® - E & E ® - E & p ® - E ^ E & p ® - E ^p& p ® -p^p& p

Пример 4. Входная цепочка -p& p^p.

E ® - E ® - E & E ® - E & E ^ E ® - E & E ^p ® - E & p^p ® -p& p^p

Деревья вывода для этих двух примеров приведены на рис. 1.

 
 

Рис. 1.

После построения дерева остается заменить терминальные символы (p или a) грамматики на соответствующие константы и идентификаторы из таблицы лексем. Для этого достаточно просматривать таблицу от начала к концу и, обходя построенное дерево от корня сверху вниз слева направо, последовательно заменить все листья, помеченные искомым символом, на лексемы из таблицы. Это последний шаг общего алгоритма работы синтаксического анализатора.

Построенное дерево и будет деревом синтаксического разбора предложения грамматики.

 

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

1. Получить вариант задания у преподавателя.

2. Построить матрицу предшествования для заданной грамматики.

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

5. Подготовить и защитить отчет.

6. Написать и отладить программу на ЭВМ.

7. Сдать работающую программу преподавателю.

Требования к оформлению отчета

Отчет должен содержать следующие разделы:

- Задание по лабораторной работе.

- Краткое изложение цели работы.

- Запись заданной грамматики входного языка в форме Бэкуса-Наура.

- Множества крайних правых и крайних левых символов с указанием шагов построения.

- Множества крайних правых и крайних левых терминальных символов.

- Заполненную матрицу предшествования для грамматики.

- Пример выполнения разбора простейшего предложения (по выбору).

- Текст программы (оформляется после выполнения программы на ЭВМ).

Основные контрольные вопросы

1. Какую роль выполняет синтаксический анализ в процессе компиляции?

2. Какие типы грамматик существуют? Как связаны типы грамматик и языков?

3. Дайте определение приведенной грамматики, грамматики в нормальной форме Хомского.

4. Поясните правила построения дерева вывода грамматики.

5. Что такое грамматики простого предшествования?

6. Как вычисляются отношения предшествования для грамматик простого предшествования?

7. Что такое грамматика операторного предшествования?

8. Как вычисляются отношения для грамматик операторного предшествования?

9. Расскажите о задаче разбора. Что такое распознаватель языка?

10. Расскажите об общих принципах работы распознавателя языка.

11. Что такое перенос, свертка. Для чего необходим алгоритм “перенос-свертка”?

12. Как работает алгоритм “перенос-свертка” (объясните на своем примере)?

 

Варианты исходных грамматик

Ниже приведены четыре варианта грамматик. Во всех вариантах символ S является начальным символом грамматики; S, и E обозначают нетерминальные символы. Терминальные символы выделены жирным шрифтом. Вместо символа a должны подставляться лексемы.

1. S®S+T | T T®T*E | T/E | E E®-F | F F®(S) | a 2. S®S or T | S xor T | T T®T and E | E E®(S) | not (S) | a 3. S®S or T | T T®T xor E | E E®E and F | F F®a< a | a> a | a=a 4. S®T< T | T> T | T< =T | T> =T T®T+E | T-E | E E®a*a | a/a | a

 

Варианты заданий

№ варианта № варианта грамматики Допустимые лексемы входного языка*
    Идентификаторы, римские числа
    Идентификаторы, булевские константы True и False, числа 0 и 1
    Идентификаторы, целые десятичные числа со знаком
    Идентификаторы, римские числа
    Идентификаторы, шестнадцатеричные числа
    Идентификаторы, римские числа
    Идентификаторы, десятичные числа с плавающей точкой
    Идентификаторы, целые десятичные числа со знаком
    Идентификаторы, десятичные числа с плавающей точкой
    Идентификаторы, восьмеричные числа (начинающиеся с цифры 0)
    Идентификаторы, римские числа
    Идентификаторы, десятичные числа с плавающей точкой
    Идентификаторы, строковые константы (в двойных кавычках)

* Примечание: римскими числами считать последовательности больших латинских букв X, V и I.

Рекомендуемая литература

1. Коровинский В.В., Жаков В.И., Фильчаков В.В. Синтаксический анализ и генерация кода – СПб.: ГААП, 1993.

2. Бржезовский А.В., Корсакова Н.В., Фильчаков В.В. Лексический и синтаксический анализ. Формальные языки и грамматики - Л.: ЛИАП, 1990.

3. Льюис Ф. и др. Теоретические основы построения компиляторов - М.: Мир, 1979.

4. Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции - М.: Мир, 1978, т.1.

5. Грис Д. Конструирование компиляторов для цифровых вычислительных машин - М.: Мир, 1975.

 






© 2023 :: MyLektsii.ru :: Мои Лекции
Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав.
Копирование текстов разрешено только с указанием индексируемой ссылки на источник.