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


 

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

54861. Створення електронних підручників 46.5 KB
  Стрімкий процес інформатизації шкіл на основі сучасних компютерів що поступають в навчальні заклади країни відкриває в освіті шлях електронним підручникам. Сучасні методи представлення інформації в компютерах містять в собі не тільки текст малюнки графіку креслення але й звукові та відео фрагменти що забезпечує наочність підручника. Окремі аспекти електронного підручника досліджувались у роботах А. Вони мають такі загальні ознаки а саме: – навчальний матеріал висловлюється з певної області знань та освітлюється на сучасному рівні...
54862. Мультиказковий феєрверк 321.5 KB
  Протилежні числа. Координатний промінь Тема модуля: Додатні та від’ємні числа. Протилежні числа.
54863. Слово. Значение слова 1.76 MB
  Значение слова. Фундаментом знаний является материал заложенный в первом классе где дети в доступной форме познакомились со словами предметами признаками предметов действиями словами которые служат для связи слов в предложении заменяя данные понятия на слова-художники слова работяги слова узелки.
54864. Градусна сітка Землі. Географічні координати 129.5 KB
  Мета: поглиблення і систематизація знань про географічні координати; вдосконалення практичних навичок і вмінь працювати з географічною картою; розвиток логічного мислення. Географічні координати – це адреса точки Г Пн. Які міста мають координати: 56 пн.
54865. Додавання і віднімання раціональних чисел 145.5 KB
  Сума двох від’ємних чисел це число. Сума двох протилежних чисел дорівнює. Знак для позначення суми чисел плюс.
54866. Княжа Русь-Україна. Підсумково-узагальнюючий урок 66.5 KB
  Сьогодні у нас підсумковоузагальнюючий урок з теми Княжа РусьУкраїна. В процесі гри Історичне лото закріпемо поняття з теми: князь князівство дружина віче полюддя релігія християнство Київська Русь Руська Правда ярлик хан орда язичнизтво бояри. Я створов перший збірник законів що отримав назву Руська Правда.
54867. Теорема Піфагора 578.5 KB
  Що називається соs гострого кута прямокутного трикутника Косинусом гострого кута прямокутного трикутника називається відношення прилеглого катета до гіпотенузи. 6 Знайдіть чому дорівнює соsА соsА = відношенню прилеглого катета АС до гіпотенузи АВ. Знайдіть чому дорівнює соsВ соsВ= відношенню прилеглого катета до гіпо тенузи. 7 Скажіть чи залежить значення соs кута від розмірів трикутника ні.
54868. Теорема Піфагора. Свято однієї теореми 5.94 MB
  Свято однієї теореми Знову теорема Піфагора Так. Теорема Піфагора Мета. Чому Можливо втрачені знання або їх глибина Можливо треба задуматися: а що ми залишимо майбутнім поколінням Цей урок присвяченій одній єдиній теоремі Піфагора доведенням якої займалися і займаються математики всіх країн.