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


 

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

77287. О СОЗДАНИИ СРЕДЫ РАЗРАБОТКИ СИСТЕМ НАУЧНОЙ ВИЗУАЛИЗАЦИИ 33 KB
  При визуализации той или иной сущности специфическими являются выбор конкретного двух или трехмерного геометрического представления абстрактного объекта и разработка алгоритма построения этого представления на основе данных производимых вычислительной программой. Можно выделить три класса систем визуализации. Наконец к третьему классу относятся специализированные системы визуализации созданные специально для данного исследовательского проекта или даже конкретного пользователя.
77289. ON DEVELOPING ENVIRONMENT FOR CONTRUCTING SYSTEMS OF SCIENTIFIC VISUALIZATION 29 KB
  One cn distinguish three clsses of visuliztion systems. The first one consists of universl systems which include set of lgorithms for constructing wide rnge of typl representtions. For exmple wellknown systems PrView nd VS belong re of this kind.
77290. ENVIRONMENT FOR CONSTRUCTING SYSTEMS OF SCIENTIFIC VISUALIZATION 32 KB
  Ekterinburg The tlk dels with scientific visulistion system which is elborted by the uthors. One of the problems of trditionl visuliztion systems is tht some set of trnsformtion lgorithms is strictly prescribed nd cnnot be chnged. yer go the uthors presented this system lredy.
77291. Развитие программных средств научной визуализации 72.5 KB
  В связи с этим в арсенале визуализации создано множество программных средств. Но что делать если исследуемое явление настолько новое что нет готовых программ визуализирующих его Можно все же попытаться выразить визуальные сущности в терминах готовых систем визуализации. Можно создать программу для визуализации с нуля.
77292. Human-aware content elements as a base for website backend interfaces 24.5 KB
  This is especilly importnt for hosted CMS services becuse there is no personl trining provided for the user. For exmple to dd vcncy on site user often should perform the following steps: crete pge crete nd formt vcncy description dd links to tht pge from min menu nd dd nnounce to compnys news. So user wstes his time nd even my leve the service. t the beginning of site cretion process user is sked for his compny type: rel estte cr rentl DVD store etc.
77293. ВИЗУАЛИЗАЦИЯ ТРАССЫ ВЫПОЛНЕНИЯ ПАРАЛЛЕЛЬНЫХ ПРОГРАММ 32.5 KB
  В литературе можно найти самые разные подходы к визуализации трасс выполнения параллельных программ. В докладе мы приведем как обзор существующих решений так и предложения по новым подходам к разработке средств визуализации трасс. Поэтому приемы хорошо помогавшие при визуализации данных лет двадцать назад например использование Visul Informtion Seeking Mntr ldquo;Overview first zoom nd filter then detilsondemndrdquo; не срабатывают. Активно используются методы визуализации трассы выполнения на базе разнообразных метафор...
77294. ВИЗУАЛЬНАЯ ПОДДЕРЖКА РАСПАРАЛЛЕЛИВАНИЯ ПОСЛЕДОВАТЕЛЬНОГО КОДА 26.5 KB
  Представляется что создание вспомогательных визуальных сред поддержки распараллеливания программ сможет облегчить работу специалистов и увеличить эффективность и надежность распараллеливания. Нами разработан макет средств визуальной поддержки распараллеливания в двух вариантах параллелизма на основе общей памяти и параллелизма на основе передачи сообщений с использованием библиотек OpenMP и MPI соответственно. Предполагается что пользователь по ходу анализа и обработки текста вносит изменения в текст последовательной программы для ее...
77295. Конструктор специализированных систем визуализации 1.13 MB
  Статья посвящена разрабатываемой авторами системы научной визуализации. Схема процесса визуализации Средства научной визуализации разделяются на три класса: Универсальные системы которые включают широкий набор алгоритмов построения различных типовых представлений. Например это известные системы PrView и VS. Универсальноспециализированные системы ориентированные на визуализацию объектов определенного типа.