68837

Лексичний аналіз

Лекция

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

На даному етапі у вхідній програмі виділяються лексеми і формуються таблиці різних класів лексем. Типові класи лексем - це ідентифікатори, константи, ключові слова мови програмування. У результаті роботи лексичного аналізатора програма перетворюється у послідовність лексем.

Украинкский

2014-09-26

101.5 KB

1 чел.

Лекція 7

Лексичний аналіз

На даному  етапі  у  вхідній  програмі  виділяються  лексеми  і  формуються таблиці різних класів лексем. Типові класи  лексем  -  це  ідентифікатори, константи, ключові слова мови програмування.  У результаті роботи лексичного аналізатора програма перетворюється  у  послідовність лексем.

Для виділення лексем  використовуються  граматики,  що  описують  окремі класи  лексем.  Згідно  з  цими  граматиками   у   вхідній  послідовності літер, що використані для написання вхідної  програми,  знаходять підпослідовності, що виводяться у тій чи іншій  граматиці.  Виявляється,  що  на  етапі  лексичного  аналізу  можна   обмежитись  регулярними граматиками.

Розглянемо приклад  виділення  дійсних  чисел,  які  описуються  регулярним виразом 

( + | - | )d*.dd* (e ( + | - |  )dd*| ),

де  d - цифра. Даний вираз показує, що дійсне  число  складається  з  декількох компонент, розташованих у поданому порядку: 1) можливий  знак; 2) послідовність цифр, що може бути  і  пустою; 3) десяткова  точка; 4) непуста  послідовність  цифр; 5) можливий  порядок,  що  складається з  а) символа  е,   б)  можливого  знака,   в)  непустої  послідовності  цифр. Наведеному регулярному виразу відповідає  граматика з продукціями 

1. S    +R | -R | dR | .P

                                                    2. R   dR | .P

                                                    3. P   dF | d

                                                    4. F   dF | eA | d

                                                    5. A +N | -N | dN | d

                                                    6. N dN | d 

Для  того,  щоб  написати  програму, яка виділяє дійсні константи,  побудуємо спочатку автомат, що представляє мову дійсних чисел. Означивши функцію переходів так, як це робилось при доведенні теореми 6.3, одержимо автомат, показаний на рис.7.1.

                                                                      d 

                                      d

                  + - d                                  d

                 d                                 

                                                             d

                                                                       e

  d              + - d              d          d

              d

Рис.7.1. Недетермінований автомат, що приймає дійсні числа.

                                                                                 d

                        d

                 + - d                                  d

                                                 e

                                                                               d

                   + -               d

                             d

На  поданому рисунку біля ребер  показані  відповідні вхідні літери, і τ = T. Стан  π    не показаний, щоб не ускладнювати  рисунок.  Його  врахування при написанні програми не викликає труднощів. Одержаний  автомат недетермінований. Для того, щоб  перейти  до  еквівалентного  детермінованого автомату, треба виконати перетворення таке,  як  при  доведенні  теореми  5.1. У даному разі  одержуємо  детермінований  автомат після об’єднання станів  F  і  T, а  також   N  і  T   (рис.7.2).

Рис.7.2. Детермінований автомат, що приймає дійсні числа.

Одержаний  граф  автомату  можна   розглядати   як   блок-схему  алгоритму   виділення   дійсного   числа. Кожний крок цього алгоритму відповідає переходу  автомату  з  одного  стану  у  інший, коли  на  вхід  приходить відповідний  символ  вхідного алфавіту. Програма, що реалізує цей алгоритм мовою Object Pascal, може  мати  такий  вигляд 

unit Main;

interface

uses

 Windows, Messages, SysUtils, Classes, Graphics, Controls, Forms, Dialogs,

 StdCtrls, Buttons;

type

 TForm1 = class(TForm)

   BitBtn1: TBitBtn;

   BitBtn2: TBitBtn;

   Edit1: TEdit;

   Edit2: TEdit;

   Label1: TLabel;

   Label2: TLabel;

   BitBtn3: TBitBtn;

   procedure BitBtn1Click(Sender: TObject);

   procedure BitBtn3Click(Sender: TObject);

 private

   { Private declarations }

 public

   { Public declarations }

 end;

var

 Form1: TForm1;

implementation

{$R *.DFM}

procedure TForm1.BitBtn1Click(Sender: TObject);

var

   ch:char;

   buffer: string[100];

   k: integer;

   i:(s,r,p,q,b,a,n);

 function digit(ch:char):boolean;

   begin

       if (ord(ch)>47)and(ord(ch)<58)then digit := true else digit := false

   end;

 function sign(ch:char):boolean;

   begin

     if (ch = '+') or (ch = '-') then sign := true else sign := false

   end;

begin

  i := s;

  buffer := Edit1.Text;

  k := 1;

 ch := buffer[k];

 while k <= Length(buffer)  do

   begin

      case i of

        s: if sign(ch) or digit(ch) then i := r

                                   else if ch = '.' then i := p else break;

        r: if ch = '.' then i := p else if not digit(ch) then break;

        p: if digit(ch) then i := q else break;

        q: if ch = 'e' then i:= a else if not digit(ch) then

            begin

                i := s;

                break;

             end;

        a: if sign(ch) then i := n else if digit(ch) then i := b else break;

        b: if not digit(ch) then

           begin

               i := s;

               break;

           end;

        n: if digit(ch) then i := b else break;

     end; {закінчення case}

     k := k+1;

     ch := buffer[k];

   end; {закінчення while}

  if (i = q) or (i = b) then Edit2.Text := 'Рядок належить мові '

  else Edit2.Text := ' Рядок не належить мові'

end;

procedure TForm1.BitBtn3Click(Sender: TObject);

begin

   Edit1.Text := '';

   Edit2.Text := '';

end;

end.

Формування таблиць

На етапі лексичного аналізу  ідентифікатори  та константи,  що мають  довільну  довжину,  замінюються  кодами  фіксованої довжини. Ключові слова також  замінюються деяким стандартним уявленням. Наприклад, слова мови  програмування  можуть  замінюватись  цілими  числами, ідентифікатори - буквою   “і”   та  наступним  за  нею  цілим  числом, константи - буквою  “с”  з наступним числом і т.д. Оскільки ці  цілі числа обмежені розрядністю обчислювальної машини, очевидно,  що  кількість  ідентифікаторів  та  констант  у  програмі   не   повинна  перебільшувати деякого числа.

Кожного  разу,  коли  у  програмі  при послідовному читанні з’являється  деякий  ідентифікатор, кажуть, що має місце його реалізація. Реалізація ідентифікатора при означенні типу відповідної  змінної  називається  визначальною.  Інші   реалізації   називаються  прикладними.

При  обробці  вхідної  програми  лексичним  аналізатором  кожна  реалізація ідентифікатора замінюється відповідним кодом. Це означає, що лексичний аналізатор повинен створювати таблицю ідентифікаторів, що визначає відповідність між кодом і ідентифікатором. При обробці  визначальної  реалізації   ідентифікатору   перевіряється, чи не міститься  вже  цей  ідентифікатор у таблиці. Якщо ні,   таблиця  поповнюється, в іншому разі діагностується помилка. Обробка прикладної реалізації включає пошук  ідентифікатора  у  таблиці  для  визначення його типу.

                        

                        121

                        122

Рис.7.3. Спискова структура таблиці ідентифікаторів.

Для зберігання таблиці ідентифікаторів у пам’яті машини потрібна структура  даних,  що  дозволяє  включення  ідентифікаторів  довільної довжини. Очевидне рішення - застосування списка, кожний елемент якого відповідає букві  ідентифікатора.  Наприклад,  таблиця  ідентифікаторів може мати структуру, умовно зображену на рис.7.3.

На рисунку стрілочки відповідають зв’язкам за покажчиками,  а  перекреслений  квадрат - нульовому покажчику.

Для опису такої таблиці у мові Object Pascal можна використати записи

    type

       ptr = ^sym;

       sym = record

            lit : char;

            ref : ptr

       end;

       tabid = array[1 .. n] of ptr;

У такій таблиці кодом ідентифікатору є індекс  масиву  tabid, а значення  ідентифікатору зберігається у вигляді списку. Велика кількість покажчиків у цій структурі  призводить  до  зайвих  витрат  пам’яті. Але, якщо мова програмування, якою пишеться компілятор, має  рядкові змінні, то покажчики не потрібні. Зменшити  витрати  пам’яті для  зберігання    таблиці  ідентифікаторів можна  також   за   рахунок   використання   (якщо   дозволяє   мова  програмування)    гнучкого    масиву. Гнучкий масив  -  це  масив,  довжину  якого  можна  змінювати під час прогону.

Аналогічна таблиця потрібна і для констант.  Деякі  компілятори  перевіряють довжину констант і обчислюють їх  у  процесі  лексичного  аналізу. Однак, допустима довжина константи залежить  від  об’єктної  машини. Тому перевагу можна віддати такому рішенню,  коли  на  етапі  лексичного  аналізу  у  таблиці  зберігаються  константи   довільної  довжини.

На відміну від ідентифікаторів код константи складається з двох  частин: номеру  Х  відповідного індексу таблиці констант та типу   Т  константи, тобто має вигляд  ХТ. Такий код передається як на  стадію  синтаксичного аналізу, так і генерації коду, де тільки і виявляється  залежність від машини.

Додаткові аспекти лексичного аналізу

Лексичний аналізатор, крім формування  лексем,  може  включати  у  вхідну програму додаткову інформацію та вилучати з неї  деякі  рядки  літер. Прикладом додаткової інформації є номери рядків програми, що використовуються при  діагностиці  помилок.   До інформації, що вилучається, належать коментарі. Крім того, деякі  алгоритмічні  мови  дозволяють включати у текст програми спеціальні вказівки, наприклад, на використання при компіляції оптимізації за часом  виконання  або на застосування певного способу виправлення помилок. Такі  вказівки  називають прагматичними зауваженнями; вони  можуть  відноситись  до  однієї фази компіляції або до декількох. Якщо прагматичні зауваження  мають відношення тільки до лексичного аналізу, то  вони  вилучаються  на цій стадії.

На жаль, більшість мов програмування при  послідовному  читанні  тексту вхідної програми, не дозволяє виділяти лексеми. Наприклад, у Фортрані при обробці рядка

DO 7 I = 1,5

з’ясувати, що перші дві літери утворюють ключове слово, можна тільки  після того, як прочитана  кома.  Таке  ускладнення  виникає  завдяки  тому, що у Фортрані проміжки не мають змістовного значення.

Схожа ситуація виникає у Алголі-68, де дозволяється означення операцій. У цій  мові  дві  послідовні  літери   “<”   та   “=”   можуть  сприйматись як символ  "менше або дорівнює", а також як  два  різних  символи, коли їм передує ключове слово   ор.  У  останньому  випадку  літера  “<”  означає позначення операції, а після знаку  “=”  вказується  зміст операції.

Таким чином можна сказати, що значення деяких вхідних  символів  залежить від значеннях інших (попередніх, чи наступних), тобто має місце контекстна залежність, що істотно ускладнює розробку лексичних аналізаторів. При відсутності такої залежності лексичний  аналізатор  можно створювати автоматично на основі формального опису синтаксису.  Треба також зауважити, що навіть  у тих  випадках,  коли  лексичний  аналіз виявляється досить простим, він потребує більше половини часу роботи компілятора. Це пояснюється, головним  чином, літерним характером обробки вхідної інформації. Лексичний аналізатор послідовно символ за символом проглядає вхідний текст. Він, можна сказати, нібито сканує вхід. Тому лексичні аналізатори називають також сканерами.

Приклад сканеру

Розглянемо сканер простої мови для запису арифметичних виразів,  що  можуть  містити крім ідентифікаторів цілі константи. Регулярний вираз, що описує послідовність лексем, має вигляд 

lex =(“  |eol|(l(l|d)*|dd*| + | - | * | = )( “  |eol))* eof,

де  “ “ – символ проміжку; eol - символ кінця рядку; l - буква латинського алфавіту; d – цифра; eof - символ кінця файлу. 

                     “ eol

                                            “ “ eol                           

        eof                         “ “ eol   

                                “ “ eol                      l d

                                  l

                        + - * =

       “ “ eol    + - * =                                             

                                    l                l                   

 + - * =              

                            + - * =                           d 

                             

  d                          d

Рис.7.4. Автомат, що приймає лексеми у арифметичних виразах.

Сканер послідовно читає з вхідного файлу символи,  починаючи  з  першого і закінчуючи останнім - ознакою кінця файлу. Перший символ, що не є проміжком або ознакою кінця  рядка,  визначає  тип  лексеми: буква відповідає ідентифікатору, цифра -  константі,  знак  операції  або  "=" - спеціальному слову вхідної мови.

Автомат, що приймає подану мову, показано на рис.7.4. З початкового стану  S  автомат під дією вхідного символу, що є  буква, цифра або знак операції потрапляє у стан, який відповідає обробці певної  лексеми. Після того, як виділення  лексеми  закінчено, відбувається корекція відповідної таблиці, і автомат, можливо, переходить у новий стан.

Ескіз процедури, що реалізує цей автомат, наведений нижче.

procedure scanner;

type

 ptr = ^sym;

 sym = record

   lit:char;

   ref:ptr

 end;

 tab = array[1..n] of ptr;

 tipl = (id, c, plus, minus, mult, equal);

 lex = record

   classlex: tipl;

   code: integer

 end;

var

 ch:char;

 fin:TextFile;

 fout:file of lex;

 l:lex;

 tid,tc:tab;

begin

 AssignFile (fin,'a:vh.prg'); reset(fin);

 AssignFile (fout,'a:lex.prg'); rewrite(fout);

 while not eof(fin) do

   begin

     while not Eoln(fin) do

       begin

         read (fin,ch);

         if not (ch = ' ') then

           begin

             if ch in ['a'..'z'] then ident(l, tid)

             else if ch in ['0'..'9'] then constant(l, tc)

             else if not (ch in ['+','-','*','=']) then error

             else if ch = '+' then l.classlex := plus

             else if ch = '-' then l.classlex := minus

             else if ch = '*' then l.classlex := mult

             else if ch = '=' then l.classlex := equal;

             write(fout,l)

           end;

       end;

   end;

end {scanner};

Вхідна програма знаходиться  у  текстовому  файлі   vh.prg   на  диску   а:.  Вихідна  програма  у   вигляді   послідовності   лексем  записується у вихідний файл  lex.prg  на тому ж диску.  При  читанні  проміжки  та  символи  кінця  рядка  сприймаються  як  ознака кінця лексеми. Для обробки ідентифікаторів, констант та   помилок  застосовуються процедури  ident, constant   та  error  відповідно.  

Процедури ident та constant не тільки заносять у  поле   сlasslex  відповідне  значення,  але  і  визначають  код  лексеми.  Для  цього  проглядається таблиця ідентифікаторів (tid) або констант (tс). Якщо значення, що обробляється, знаходиться у таблиці, то відповідний код (номер індексу масиву)  заноситься  у  поле code. У протилежному випадку у таблицю заноситься новий  елемент з кодом,  що дорівнює кількості елементів у збільшеній таблиці. Останнє значення заноситься у поле code лексеми. Детально   робота з таблицями розглядається далі у окремій лекції.


 

А также другие работы, которые могут Вас заинтересовать

37758. Програмування в Java 172 KB
  Поздоровляю вас зі вступом в ряди програмістів на Java — розроблювачів технології початку XXI століття. Всі уроки ви повинні прочитувати вдома, а на лекції і лабораторних роботах ви повинні звітуватися за виконані завдання. Перше серйозне завдання ви знайдете в кінці Уроку 2. Всі завдання індивідуальні, щоб одержати залік в кінці семестру їх треба обовязково виконати
37759. ВЫБОР РАЦИОНАЛЬНОЙ ДЛИНЫ ПАКЕТА СЕТИ ЭВМ 2.41 MB
  2 Теоретическая часть Для сообщений передаваемых в сети ЭВМ длина пакета выбирается постоянной. Длина пакета не может быть слишком малой поскольку при фиксированной длине служебной части заголовка пакета снижается доля информации сообщения передаваемая в одном пакете. При большой длине пакета и заданной достоверности передачи данных в канале связи повышается вероятность передачи пакета с ошибкой и следовательно частота повторной передачи пакета что снижает эффективность сети ЭВМ а также возрастает доля потерь памяти изза...
37760. ОТРАВЛЯЮЩИЕ ВЕЩЕСТВА РАЗДРАЖАЮЩЕГО ДЕЙСТВИЯ. КЛИННИКА, ДИАГНОСТИКА, ЛЕЧЕНИЕ 70.5 KB
  Уже в первой мировой войне почти все воюющие страны применяет различные ОВ, избирательно действующие на окончания чувствительных нервов в верхних дыхательных путях с последующей реакцией организма в виде слезотечения, кашля, рвоты, затрудненного, дыхания и т.д
37761. Исследование разветвленной линейной электрической цепи постоянного тока 109.5 KB
  Цель работы Экспериментальная проверка законов Кирхгофа и основных свойств линейных цепей постоянного тока. Экспериментальная часть Схема установки R1 = 100 Ом R2 = 50 Ом R3 = 25 Ом Е1 = 75 В E2 = 10 В Проверка законов Кирхгофа Измерено Вычислено I1 I2 I3 Ik 009 016 0065 0005 I1 I2 I3 = 0.065 А Вывод: Экспериментально были проверены законы Кирхгофа. Выставив необходимые значения сопротивлений и проведя необходимые измерения и...
37762. Измерение вязкости жидкости по методу падающего шарика 45.5 KB
  Измерение температуры жидкости t= 0C Расчет искомой величины. Расчет плотности материала шариков 2. Расчет вязкости жидкости Расчет границы погрешностей. Расчет границы абсолютной погрешности результата измерения плотности материала шариков Расчет границы относительной погрешности результата измерения вязкости жидкости Расчет границы абсолютной погрешности результата измерений плотности Окончательный результат: вязкость жидкости при температуре t= 0C.
37763. Методы противодействия радиоэлектронным закладным устройствам, предназначенным для снятия конфиденциальной информации 48.88 KB
  Цели и учебные вопросы Цели лабораторной работы: ознакомление с возможностями комплекса Крона НМ и программного обеспечения Филин Ультра; получение практических навыков: по проведению радиомониторинга в контролируемой зоне по обнаружению поиску и блокированию радиозакладных устройств Учебные вопросы: классификация поисковых устройств для проведения радиомониторинга см. Место: лаборатория Технические средства обеспечения безопасности Используемые технические средства: автоматизированный комплекс обнаружения электронных...
37764. Безпека SMTP і спам 760.04 KB
  У результаті цього спам став практично нерозв'язною проблемою так як було неможливо визначити хто насправді є відправником повідомлення фактично можна відправити лист від імені будьякої людини. DT CRLF Вказує на початок повідомлення. Для завершення повідомлення вказується CRLF . Повідомлення доставляються клієнтові за протоколом POP а надсилаються як і раніше за допомогою SMTP.
37765. Робота з діалоговими компонентами 2.09 MB
  Виконавши лабораторну роботу, я освоїв роботу програм з такими діалоговими компонентами як OpenDialog та SaveDialog для зв’язку з файлами (їх створення, збереження або відкриття вже існуючих), PrinterSetupDialog для налагодження підключених принтерів для друку, FindDialog та ReplaceDialog для пошуку та заміни тексту. Також закріпив навички роботи з компонентами середовища Delphi TMemo та TMainMenu, зрозумів основні принципи створення текстового редактора.