ид   ид     { ид }                                      

                                                                       ИД     ИД     ИД     ИД

IF  (          A      <      B            )   B     U     L     L            ()                ;    

В программе данные функции размещены в соответствии с входным языком G < Оператор>. В случае смены входного языка

требуется всего на всего заменить очередность вызова функций. Например в пределах заданного базиса можно сконструировать грамматику  G < Инструкция >.

G < Инструкция > à PRINT ( < УВ > ) ( < УВ > ) < Функция >;

( Дальнейшая конструкция языка идентична языку G < Оператор > ).

Сконструируем дерево вызова следующим образом:

TREATMENT à TYPE(«print») à BRACKET(1) à TERM() à SIGN() à TERM() à BRACKET(2) à BRACKET(1) à TERM() à SIGN() à TERM() à BRACKET(2) à FUNC() à TZ()

                Таким образом можно порождать необходимые языковые конструкции. На данном этапе имеются уже два оператора

IF и PRINT. Можно продолжать дальнейшее наращивание входного словаря операторов, таким образом расширяя сам свой собственный язык.

                Язык G  < Оператор > выполнен со значительными усечениями поэтому не претендует на роль идеального базиса. Например обязателен вызов функции после круглой скобки,

хотя реально это только мизерная часть возможных операций.

Автор данной работы не ставил перед собой задачу сконструировать более менее приемлимый язык. Главная цель -это отразить понимание принципа построения грамматик и выработки языка.

          Несколько слов о самой программе. Программа выполнена,

как я уже упомянал, на языке Си, с элементами Си++. После запуска

программы непосредственно сразу последует запрос на анализ синтаксиса. Словом в верхней части экрана необходимо ввести строку и нажать клавишу «ENTER». В зависимости от набора символов в нижнем окне появятся соответствующие сообщения:

a) Об ошибках -в случае несоответствия входного и текущего языков

b) «Успех!!!» -в противном случае

          Имеется возможность использования ключевых слов:

1. «help» -выводит на экран окно помощи

2. «helpme» -выводит на экран авторское окно

3. «exit» -выход из программы

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

Постановка задачи

Пользуясь базовым языком высокого уровня Си ++ разработать и реализовать синтаксический анализатор условного оператора

IF ELSE языка Си.

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

1. Построение формального языка L  

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

2. Подбор грамматики G[Z] по языку L

Построенный формальный язык L, подвергается декомпозиции, в процессе которой выявляются лексические составляющие - идентификаторы, константы и др. терминальные символы.

3. Классификация G[Z]  

Для гарантии однозначности и безвозвратности разработанного языкового процессора выбранный язык отнести согласно класси-

фикации формальных грамматик, предложенных Хомским.

4. Выбор метода анализа

Проанализировать и выбрать наиболее подходящий анализ входного языка.

5. Диагностика и нейтрализация ошибок  

Разработать алгоритм диагностики и нейтрализации ошибок.

6. Тестирование на программы на символьных цепочках

Протестировать разработанный языковой процессор на конкретных символьных цепочках.

7. Листинг

В конце отчета поместить распечатку программы с подробными коментариями.

Построение формального языка L

< Оператор >   à   IF  ( < УслВыр > ) < Функция >;

[ ELSE  < Функция >; ]

< Оператор > -- начальный нетерминальный символ

IF  --  входной терминальный символ

ELSE -- входной терминальный символ (может и отсутствовать)

< УВ > -- условное выражение

< Функция > -отражает функциональную конструкцию языка Си

Пример правильного синтаксиса:

if (   a  <  b  )  CallTheFunction( code1 );  else  TheNextFunction( code2 );

a < b - есть условное выражение

«CallTheFunction» и «TheNextFunction» -- функции

code1 & code2  -- параметры функции

Подбор грамматики  G[Z]  по языку  L

          Любой язык, назовём его G <Z> в независимости от его классификации и функционального назначения содержит следующие базисные элементы:  G <Z> ={ Vt, Vn, Z, P }, где:

Vt - словарь терминальных символов

Vn - словарь нетерминальных символов

Z  - начальный нетерминальный символ

P - множество правил вывода

          Для языка G <Оператор> имеем следующие множества:

Vt ={ 0, 1, 2, ... , 9 ; a, b, c, d, ... ,z ; A, B, C, ..., Z; <, >, = };

Vn ={«Оператор», «УслВыр», «Терм», «Операнд», «Функция», «Идентификатор», «Скобки», «Целое» };

Z = { «Оператор» };

P = {

1. < Оператор >   à   IF  ( < УслВыр > ) < Функция >                              [ ELSE  < Функция > ]

2. < УслВыр > à  T   |   T  <  T    |   T  >  T   |      T  =  T

3. < Операнд > à  «Идентификатор»  |   «ЦБЗ»

4. < Функция >  à   < Идентификатор > (< Список параметров >); 

5. < Список параметров > à < Параметр >  |   W

6. < Параметр > à   «Идентификатор»  |   «ЦБЗ»  |   W

7. < Идентификатор > à  Б {  Б  |  Ц  }

       }

Классификация G[Z]

1. < Оператор >   à   IF  ( < УслВыр > ) < Функция >                              [ ELSE  < Функция > ]

2. < УслВыр > à  T   |   T  <  T    |   T  >  T   |      T  =  T

3. < Операнд > à  «Идентификатор»  |   «ЦБЗ»

4. < Функция >  à   < Идентификатор > (< Список параметров >); 

5. < Список параметров > à < Параметр >  |   W

6. < Параметр > à   «Идентификатор»  |   «ЦБЗ»  |   W

7. < Идентификатор > à  Б {  Б  |  ЦБЗ  }

Сделаем замену нетерминальных символов:

< Оператор > à  Z

< УслВыр >  à  A

< Терм > à  B

< Функция > à C

< Список параметров > à D

< Параметр > à E

< Идентификатор > à F

Сделаем замену терминальных символов:

 IF à  a

  (  à  b

  )  à  c

  ;  à  d

ELSE à e

ЦБЗ à   f

 Б à  g

W à h

1. Z à abAcC [ eC ]

2. A à  B   |   B  <  B    |   B  >  B   |      B  =  B

3. B à  F   |   f

4. C à FbDcd

5. D à E  |  h

6. E à    F  |   f   |   h

7. F à    g { g | f }

Вывод : G[Z] - автоматная грамматика.

Выбор метода анализа

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

Диагностика и нейтрализация ошибок

Разработанный алгоритм относится к общеизвестному методу синтаксического разбора, предложенный Айресом.

Основная идея метода состоит в том, что по контексту без возврата отбрасываюся те символы, которые привели в тупиковую ситуацию и разбор продолжается.

          Для наглядности изобразим куст синтаксического разбора для входного языка:

Дано:

IF ( A < Bc  ) BULL ()  ;    

1. Z à abAcC [ eC ]

2. A à  B   |   B  <  B    |   B  >  B   |      B  =  B

3. B à  F   |   f

4. C à FbDcd

5. D à E  |  h

6. E à    F  |   f   |   h

7. F à    g { g | f }

                                Z