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

Министерство образования и науки Российской Федерации

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

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

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

«Комсомольский-на-Амуре государственный

технический университет»

Факультет компьютерных технологий

Кафедра «МОП ЭВМ»

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

по курсу «Теория языков программирования»

Студенты группы 4ВТ-1:                                                                          Александров С.Ю.

Сочнев И.Г.

Преподаватель:                                                                                                    Петрова А.Н.

Комсомольск-на-Амуре

2007

Тема:                 Синтаксический анализатор.

Цель работы: Изучить работу синтаксического анализатора.

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

Удаление леворекурсивных правил грамматики

ОБ_ТИПА ® ид_р

ДИСК_Д ® СК1 ДИА

СК1 ® ОБ_ТИПА RANGE │λ

ДИА ® ПР_ВЫР..ПР_ВЫР

ПР_ВЫР ® СК2 СЛАГ СП2

СК2 ® О_ОПЕР│λ

СЛАГ ® МН СП3

СП2 ® СП2 ОПЕР_Т_СЛ  СЛАГ│ОПЕР_Т_СЛ  СЛАГ

ОПЕР_Т_СЛ ® +│-│&

СП3 ® СП3 ОПЕР_Т_УМ  МН│ОПЕР_Т_УМ  МН

СП2 ® ОПЕР_Т_СЛ  СЛАГ  СП__2

СП__2® ОПЕР_Т_СЛ СЛАГ СП__2│ λ

СП3 ® ОПЕР_Т_УМ   МН  СП__3

СП__3®ОПЕР_Т_УМ  МН  СП__3│ λ

МН ® ПЕРВ СК3

СК3 ® **ПЕРВ│λ

ПЕРВ ® число│строка │ ИН_Д   СК4│ ид_р СК5

ПОСТ ® число│строка│λ

ПЕРЕМ ® ИН_Д   СК4

СК4 ® СК1 ДИА │λ

ВЫЗ_ПОД ® ид_р СК5

СК5 ® (СООТ_ПАР СП4)│λ

СП4 ® , СООТ_ПАР   СП__4

СП__4®, СООТ_ПАР  СП__4│λ

СООТ_ПАР ® СК6   ВЫР

СК6 ® ПАР:=│λ

ПАР ® ид_р

ВЫР ® ОТН  СП5│ОТН  СП6│ОТН  СП7

СП5 ® AND ОТН СП__5

СП__5® AND ОТН СП__5│λ

СП6 ® OR ОТН СП__6

СП__6®OR ОТН СП__6│λ

СП7 ® XOR ОТН СП__7

СП__7® XOR ОТН СП__7│λ

ОТН ® ПР_ВЫР   СК7

СК7 ® ОПЕР_ОТН  ПР_ВЫР│λ

ОБ_ОБ ® СП_ИД : СК8 тип СК9

СП_ИД ® ид_р  СП8

СП8 ® ид_р  СП__8

СП__8® , ид_р СП__8│λ

СК8 ® CONSTANT │λ

СК9 ® ОТН  СП5│ОТН  СП6│ОТН  СП7│λ

ОП_ПРИС ® ПЕРЕМ := ВЫР

ОП_ВОЗВ ® RETURN  СК10

СК10 ® ОТН  СП5│ОТН  СП6│ОТН  СП7│λ

УСЛ_ОП ® IF УСЛ THEN ПОСЛ_ОПЕР   СП9  СК11 END IF;

УСЛ ® ВЫР  СП10│ВЫР СП11

СП9 ® ELSIF УСЛ THEN ПОСЛ_ОПЕР СП__9

СП__9® ELSIF УСЛ THEN ПОСЛ_ОПЕР СП__9 │λ

СК11 ® ELSE ПОСЛ_ОПЕР│λ

СП10 ® AND THEN ВЫР  СП__10

СП__10® AND THEN ВЫР СП__10│λ

СП11 ® OR ELSE ВЫР СП__11

СП__11® OR ELSE ВЫР СП__11│λ

ПОСЛ_ОПЕР ® СП12   ОПЕРАТОР│ ПЕРЕМ := ВЫР │ ид_р СК5│ EXIT СК12 СК13│ RETURN СК14│ GOTO   ид_р │ DELAY   ПР_ВЫР

СП12 ® ПЕРЕМ := ВЫР  СП__12│ ид_р СК5  СП__12│ EXIT СК12 СК13  СП__12│ RETURN  СК14 СП__12│ GOTO ид_р  СП__12│ DELAY   ПР_ВЫР  СП__12

СП__12®ОПЕРАТОР СП__12│ λ

ОПЕРАТОР ® ПЕРЕМ := ВЫР │ ид_р СК5│ EXIT СК12 СК13│ RETURN СК14│ GOTO   ид_р │ DELAY   ПР_ВЫР

ПР_ОПЕР ® ПЕРЕМ := ВЫР │ ид_р СК5│ EXIT СК12 СК13│ RETURN СК14│ GOTO   ид_р │ DELAY   ПР_ВЫР

ОП_ВЫЗ_ПОД ® ид_р СК5

ОП_ВЫХ ® EXIT СК12 СК13

СК12 ® ид_р│λ

СК13 ® WHEN   УСЛ│λ

ОП_ВОЗВ ® RETURN СК14

СК14 ® ОТН  СП5│ОТН  СП6│ОТН  СП7│λ

ОП_ПЕР ® GOTO   ид_р

ОП_ЗАД ® DELAY   ПР_ВЫР

ОП_ВЫБ ® CASE   ВЫР   OF   СП13  END CASE;

СП13 ® WHEN  ВАРИ СП14 => ПОСЛ_ОПЕР СП__13

СП__13® WHEN  ВАРИ СП14 => ПОСЛ_ОПЕР  СП__13│λ

СП14 ® |ВАРИ СП__14

СП__14®|ВАРИ СП__14│λ

ВАРИ ® СК2 СЛАГ СП2│ СК1 ДИА │OTHERS

ОП_ЦИКЛ ® СК15  ОСН_ЦИКЛ

ОСН_ЦИКЛ ® LOOP ПОСЛ_ОПЕР END LOOP СК16

СК16 ® ид_р │λ

СК15 ® FOR ид_р IN СК17 ДИСК_Д│WHILE УСЛ│λ

СК17 ® REVERSE│λ

ОБ_ПОД ® СПЕЦ_ПОД;│ПР_ПОД ОБОЗ

ПР_ПОД ® FUNCTION│PROCEDURE

ОБОЗ ® ид_р│строка символов

СПЕЦ_ПОД ® ПР_ПОД   ОБОЗ  СК18  СК19

СК18 ® (ОБ_ТИПА   СП15)│λ

СК19 ® RETURN ид_р│λ

СОВ_ПАР ® (ОБ_ТИПА   СП15)

СП15 ® ;ОБ_ПАР СП__15

СП__15® ;ОБ_ПАР СП__15│λ

ОБ_ПАР ® СП_ИД : ВИД_СВ  тип

ВИД_СВ ® IN│OUT│IN OUT│λ

БЛОК ® BEGIN   ПОСЛ_ОПЕР  END СК20;

СК20 ® ид_р│λ

СОВ_ОБ ® СП16  СП17

СП16 ® СП_ИД : СК8 тип СК9 СП__16│ СПЕЦ_ПОД; СП__16│ПР_ПОД ОБОЗ СП__16

СП__16® ОБ_Е  СП__16│λ

ОБ_Е ® СП_ИД : СК8 тип СК9│ СПЕЦ_ПОД;│ПР_ПОД ОБОЗ

СП17 ® ТЕЛО_ПОД СП__17

СП__17® ТЕЛО_ПОД СП__17│λ

ТЕЛО_ПОД ® СПЕЦ_ПОД   IS  

СОВ_ОБ

BEGIN

ПОСЛ_ОПЕР

END СК21;

СК21 ® ид_р│строка символов │λ

Таблица множеств для выбора правил грамматики