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 лексеми. Детально   робота з таблицями розглядається далі у окремій лекції.


 

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

22583. Механізм збудження рецепторів 24 KB
  до первинночутливих відносяться тканинні рецептори пропріорецептори терморецептори і нюхові клітини. Первинночутливі рецептори є універсальним типом рецепторних елементів у безхребетних. Вторинночутл є зоровий слуховий вестибулярний рецептори.
22584. Принцип кодування інформації в нервовій системі 26 KB
  На рівні рецепторів відбувається важливі етапи переробки інформації: отримання прийом сигналів трансформація цих різнорідних по своїй природі сигналів в єдиний по своїй природі процес – нервовий імпульс. Ця автономність дає змогу організму що володіє спеціальними механізмами відбору запамятовування збереження і відтворення інформації знову звертатись до зафіксоваої а памяті інформації відновлювати минулі подіїзовнішнього світу у вигляді нервових імпульсів і знову практично в будь який відрізок часу використати в переробці нову...
22585. Види памяті 32 KB
  Види памяті Пам'ять це здатність нервової системи зберігати у зако дованому вигляді інформацію яка при певних умовах може бути виведена з цієї системи відтворена. За тривалістю збереження інформації розрізняють безпосередній відбиток сенсорної інформації іконічну короткочасну секундигодини і довготривалу дні й роки пам'ять. Крім того у людини виділяють первинну вторинну і третинну пам'ять. Цей вид памяті має різні параметри у кожної людини змінюється протягом життя індивіда і залежить від функціонального стану організму.
22586. Кримінальне покарання. Поняття та ознаки 42.88 KB
  Поняття та ознаки Кримінальне покарання є необхідним засобом охорони держави суспільства і безпеки особи від злочинів. У боротьбі зі злочинністю кримінальне покарання має кілька функцій. Подруге реальне виконання кримінального покарання впровадження конкретних правообмежувальних процедур до винних осіб чинить сильний вплив як на самого винного так і на його оточення.
22587. Права та обовязки батьків і дітей 41.21 KB
  Це визначається на підставі Свідоцтва про шлюб і документа закладу охорони здоров'я про народження дружиною дитини. Дружина і чоловік мають право подати до державного органу реєстрації актів цивільного стану спільну заяву про невизнання чоловіка батьком дитини. Якщо мати та батько дитини не перебувають у шлюбі між собою походження дитини від матері визначається на підставі документа закладу охорони здоров'я про народження нею дитини а від батька за заявою матері та батька дитини або за заявою чоловіка який вважає себе батьком дитини або...
22588. Співучасть у злочині 32.16 KB
  Підставою відповідальності тут є той самий склад злочину але вчинюваний у співучасті. Об'єктивні ознаки співучасті виражені у такому формулюванні: злочин вчинений кількома двома або більше суб'єктами злочину спільно. Виконавцем співвиконавцем вважається особа яка безпосередньо або шляхом використання інших осіб що не є суб'єктами злочину вчинила конкретний злочин ч.
22589. Робочий час і його види 34.41 KB
  Згідно з діючим законодавством можна виділити такі види робочого часу: нормальна тривалість робочого часу; скорочений робочий час; неповний робочий час; нормований і ненормований робочий час; надурочний робочий час; нічний робочий час. 50 Кодексу законів про працю України нормальна тривалість робочого часу працівників не може перевищувати 40 годин на тиждень. Але підприємства і організації при укладанні колективного Договору можуть встановлювати меншу норму тривалості робочого часу тобто менше 40 годин на тиждень.
22590. Екологічні права і обовязки громадян 18.98 KB
  Громадяни мають право брати участь в обговоренні проектів законодавчих актів матеріалів щодо розміщення будівництва і реконструкції об'єктів які можуть негативно впливати на стан навколишнього природного середовища та внесення пропозицій до державних та господарських органів установ та організацій з цих питань. Кожен громадянин України має право на участь у розробці та здійсненні заходів щодо охорони навколишнього природного середовища раціонального і комплексного використання природних ресурсів. Громадяни можуть об'єднуватися у...
22591. Адміністративні правовідносини 57 KB
  Основні ознаки адміністративних правовідносин: вони виникають на основі адміністративноправових норм; характеризуються наявністю сторін що іменуються суб'єктами адміністративного права; за змістом включають в себе адміністративні права владного характеру і юридичні обов'язки; є видом суспільних відносин державних органів фізичних або юридичних осіборганізацій і спільностей; здійснення суб'єктивних прав або додержання юридичних обов'язків у правовідносинах контролюється і забезпечується державою; Групувати адміністративні правовідносини...