22938

Синтаксичний аналіз виразів

Лекция

Информатика, кибернетика и программирование

Мова в певному алфавіті основному символів це слова записані за певними синтаксичними правилами. Синтаксичні правила подаються формулами БекусаНаура БНФ вигляду : ::= де позначає синтаксичне поняття а послідовність символів розширеного алфавіту. Вираз [] означає що послідовність символів входить або не входить в конструкцію. Синтаксичний аналізатор це програма що для заданої послідовності символів основного алфавіту розпізнає чи побудована вона у відповідності з синтаксичними правилами для даного поняття.

Русский

2013-08-04

31 KB

1 чел.

ЛАБОРАТОРНА РОБОТА  6

 

ТЕМА:  Синтаксичний аналіз виразів.

Мова в певному алфавіті (основному) символів – це слова, записані за певними синтаксичними правилами. Синтаксичні правила подаються формулами Бекуса-Наура (БНФ) вигляду :  <…> ::= ,  де  <…> - позначає синтаксичне поняття, а  - послідовність символів розширеного алфавіту. Розширений алфавіт – це основний  алфавіт, доповнений  синтаксичними поняттями та метасимволами - ‘|’, ‘[‘, ‘]’, ‘{‘, ‘}’, ‘(‘, ‘)’.  Метасимвол ‘|’ розділяє  альтернативні варіанти поняття. Вираз […] означає,  що послідовність символів входить або не входить  в конструкцію. Вираз {…} – що конструкція може повторюватись довільну кількість  раз (n>=0).  Кожному поняттю відповідає певна індуктивно визначена сукупність синтаксично правильних  слів в основному алфавіті. Означені синтаксичні правила у вигляді формул є не що іншим, як лінійною формою вже згадуваних СД Н.Вірта.  Синтаксичний аналізатор - це програма, що для заданої  послідовності символів основного алфавіту розпізнає, чи побудована вона  у відповідності з синтаксичними правилами для даного поняття. Говорять, що БНФ допускає  LА(1)-аналіз, якщо в кожній її формулі альтернативи  правої  частини розпочинаються з попарно різних символів основного алфавіту. Програма LА(1)-аналізатор  складається з сукупності рекурсивних функцій, що відповідають кожному  синтаксичному правилу і які викликають  одна одну у відповідності до правих частин своїх формул.

  

ЗАВДАННЯ

Побудувати синтаксичний аналізатор  для   поняття <хороший>:

<хороший> :: = x | [<хороший>{+<хороший>}]

Вхідна послідовність символів  вводиться з клавіатури. Основний алфавіт складають чотири символи: x , [], + .  БНФ складається з одного синтаксичного правила.  «Хорошими»  є , нпр., слова :   x (база індукції),  [x], [x+x]  і т.д. (за індуктивним переходом).  «Нехорошими» cловами - xx, [],  x+x  тощо.

/* LA(1)- аналізатор для поняття  <хороший> */

#include <stdio.h>

char ch; /* для читання символів  вхідного слова */

beautiful()

/* УВАГА! Перед викликом аналізатора  змінна ch  завжди містить  черговий  символ вхідного слова  !!! */

{ if (ch == ‘[‘) { ch=getchar();  beautiful();

                          while (ch==’+’) { ch=getchar();  beautiful();}

                            if  (ch != ‘]‘) { Err(1); /* обробка  помилкової ситуації :“Відсутня дужка ‘]’ ” */

                                                     

                                                     exit(1);} 

                                /* Заключна дужка ‘]’  є  і це означає, що   прочитано правильний варіант  альтернативи  */

                                  ch=getchar();  

                          } else  if (ch == ‘x‘)  ch=getchar();

                                                  else { Err(2); /* обробка  помилкової ситуації : Очікування  х  */

}

main ()

{  ch= getchar();

   beautiful();

   if (ch == EOF) printf (“Yes”)  

    else  Err(3); /* обробка  помилкової ситуації : Зайві символи в кінці слова   */

}

Еrr( int i)

{  switch (i) {

                          case 1:  printf (”\n Помилкова ситуація 1  ----   відсутня дужка ‘]’ “); break;

                          case 2:  printf (”\n Помилкова ситуація 2  ----   очікування  х’ ” ); break;

                          case 3:  printf (”\n Помилкова ситуація 3  ----    зайві символи в кінці слова “); break;

                      }

    exit(1);

}