Сторінка
5

Обчислення виразів у програмуванні

9. Читання лексем виразу Вираз є послідовністю лексичних одиниць (лексем) чотирьох різновидів: сталі, імена (позначення функцій), знаки операцій та дужки. Виділення лексем із виразу називається його лексичним аналізом. Лексеми виділяються в ході побудови внутрішнього подання виразу багаторазовим розв'язанням задачі добування чергової лексеми виразу. Тут ми представимо розробку модуля, що забезпечує все необхідне для добування лексем. Створюючи цей модуль, ми повністю відділяємо обробку лексем виразу від їх добування. Якщо колись нам доведеться міняти добування лексем, ми внесемо зміни лише в цей модуль. 9.1. Алгоритм добування лексеми Розв'язання задачі добування чергової лексеми буде описано функцією getlx. За її виконання обчислюється ознака того, чи є ще лексема у вхідній послідовності символів, і за її наявності вона присвоюється параметру-змінній функції. Помістимо функцію getlx і допоміжні для неї засоби в модуль Glx. Алгоритм добування лексеми має такий загальний вигляд: відшукати перший символ лексеми; if відшукали then прочитати символи лексеми та створити її подання else зафіксувати відсутність лексеми. 9.2. Модуль розпізнавання лексем У цьому модулі треба означити все необхідне для читання лексем. За межами модуля використовуються тип st8 імен, типи лексем Tlx та їх різновидів Ttlx, а також функція getlx. Означення цих типів та заголовок функції мають бути в інтерфейсному розділі модуля. У розділі реалізації означимо необхідні сталі, а також масив Namf, що зберігає множину імен функцій. Означимо змінні Bcon, Bnam, Bops, Bpar та Blex для зберігання множин символів, якими починаються лексеми відповідних різновидів, та їх об'єднання. Ініціалізацію всіх цих змінних задає процедура glxinit, виклик якої записується в розділі ініціалізації модуля. Останньою в розділі реалізації записується основна функція getlx, а перед нею – допоміжні для неї підпрограми та інші означення. Отже, модуль Glx, записаний мовою Турбо Паскаль, має такий загальний вигляд:

Unit Glx ( input, output ); Interface type st8=string[8]; Ttlx = (con, nam, ops, par, err); Tlx = record case stl : Ttlx of con : (numb : real); nam : (name : st8 ); ops : (sig : char); par : (prt : char);

err : (wrlx : st8 ) end; function getlx ( var lx : Tlx ) : boolean; Implementation

const fnum = 2; {кількість імен функцій} var Namf : array [ 1 fnum ] of st8; Bcon, Bnam, Bops, Bpar, Blex : set of char; procedure glxinit; … end;

… { Допоміжні для getlx означення} function getlx; … end; Begin

glxinit End. Одразу наведемо процедуру ініціалізації: procedure glxinit; begin Bcon := [ '0' '9' ]; Bnam := [ 'a' 'z' ]; Bops := [ '+', '*', '-', '/' ]; Bpar := [ '(', ')' ]; Blex := Bcon + Bnam + Bops + Bpar; Namf[1] := 'sin'; Namf[2] := 'cos' end; 9.3. Функція getlx Будемо вважати, що вираз записано в тексті, між його лексемами можуть бути пропуски в довільній кількості, і що вираз може займати кілька рядків тексту. Інших уточнень поки що не робимо. Текст читається по одному символу, і нехай читання й повернення наступного символу тексту задає функція getc. Нехай останній прочитаний символ тексту, який ми називаємо поточним, зберігається в глобальній у модулі змінній tempc. Вона ініціалізується символом ' ' (пропуск), тобто перед виразом штучно додається пропуск. Добування лексеми починається з пошуку її першого символу у вхідній послідовності. Нехай пошук першого символу описується функцією getbglx. З її виклику повертається або перший символ лексеми, або, коли лексеми вичерпано, символьна стала chr(0), яку можна вважати "фіктивним символом". Іменування цієї сталої ім'ям finch додамо до означень модуля.

<D>	<L>	'+', '*', '-', '/'	'(', ')'	інший символ
con	nam	ops	par	err

Подальша обробка лексеми залежить від її різновиду й визначається її першим символом. Нехай <D> позначає цифру з діапазону '0' '9', а <L> – літеру з 'a' 'z'. Залежність різновиду від першого символу лексеми (за її наявності) подамо так: Щоб добути знак операції чи дужку, досить узяти поточний символ. Добування сталих та імен (елементів типу real і st8) опишемо функціями відповідно getcon і getnam. Побудуємо функції getcon і getnam так, щоб після виконання їх виклику поточним був символ, наступний за останнім символом добутої лексеми. У такому разі до обробки знаків операцій і дужок додамо указання переходу до наступного поточного символу tempc := getc. Імена, що не є іменами функцій із масиву Namf, будемо вважати помилковими лексемами. Якщо лексема подається змінною lx типу Tlx, то залежно від першого символу лексеми потрібно виконати такі дії: <D> ® lx.stl := con; lx.numb := getcon; <L> ® lx.name := getnam; if lx.name представлено в Namf then lx.stl := nam else lx.stl := err; '+', '*', '-', '/' ® lx.stl := ops; lx.sig := tempc; tempc := getc; '(', ')' ® lx.stl := par; lx.prt := tempc; tempc := getc; інше ® lx.stl := err; lx.wrlx := tempc; tempc := getc; В усіх випадках повертається значення true – ознака наявності лексеми. За символу finch повертається false. Наведена залежність є основою функції getlx: function getlx ( var lx : Tlx ) : boolean; begin getlx := true; tempc := getbglx; if tempc in Bcon then begin lx.stl := con; lx.numb := getcon end else if tempc in Bnam then begin lx.name := getnam; if isfn ( lx.name ) then lx.stl := nam else lx.stl := err end else if tempc in Bops then begin lx.stl := ops; lx.sig := tempc; tempc := getc end else if tempc in Bpar then begin lx.stl := par; lx.prt := tempc; tempc := getc end else if tempc = finch then getlx := false else begin lx.stl := err; lx.wrlx := tempc; tempc := getc end end; Функція isfn перевірки, чи представлено ім'я lx.name в масиві Namf, залишається для самостійної розробки. 9.4. Допоміжні підпрограми Алгоритм процедури getbglx дуже простий: поки поточний символ не потрапив у множину Blex перших символів лексем, викликається функція getc для одержання нового поточного символу. Якщо при цьому вираз вичерпується, то наступним поточним вважається "фіктивний символ" finch. function getbglx : char; begin while not ((tempc in Blex )or( tempc = finch ) ) do tempc := getc; getbglx := tempc end; Функція getcon задає читання символів сталої з образу та побудову за ними відповідного значення типу real. Нехай синтаксис сталої задається метавиразом <D> { <D> } [ '.' { <D> } ]. Розглянемо побудову значення типу real за сталою. Цифри до крапки задають цілу частину числа. Значення чергової цифри додається до результату обробки попередніх цифр, помноженого на 10. Перед обробкою першої цифри результатом є 0. Крапка пропускається, а значення цифр праворуч від неї множаться на відповідні від'ємні степені числа 10 і додаються до числа: function getcon : real; var v, d : real; begin v := 0; d := 1; repeat v := v*10 + ord(tempc) - ord('0'); tempc := getc; until not (tempc in Bcon); if tempc = '.' then tempc := getc; while tempc in Bcon do begin d := d/10; v := v + ( ord(tempc) - ord('0') )*d; tempc := getc end; {сталу прочитано; поточним є символ, наступний за її останнім} getcon := v end; Запишемо функцію getcon у інший спосіб, який реально застосовується в побудові підпрограм лексичного аналізу в системах програмування. Обробка чергового символу залежить від того, чи є він цифрою в цілій або дробовій частині сталої, крапкою або символом після сталої. Додамо змінну cp типу Tcp=(ip, fp, out), елементи якого позначають місця поточного символу tempc в цілій (ip) та дробовій (fp) частині або за межами сталої (out). Спочатку cp=ip. Залежність її наступного значення від попереднього та від поточного символу tc подамо таблицею, в якій стрілка ліворуч відмічає початкове значення ip (табл.20.1). Нехай змінна v зберігає результат обробки попередніх цифр, d – від'ємні степені числа 10 (спочатку v=0, d=1). Нехай num(<D>) позначає вираз ord(<D>)-ord('0'). Подамо обробку поточного символу tempc й змінювання значень cp таблицею 20.2. Відсутність присвоювань змінній cp у деяких клітинах табл. 20.2 означає, що її значення не змінюється. За наведеною таблицею функція getcon записується з уживанням оператора case майже механічно: function getcon : real; type Tcp = ( ip, fp, out ); var v, d : real; cp : Tcp; begin v := 0; d := 1; cp := ip; while cp <> out do case cp of ip : case tempc of '0' '9' : begin v := v*10 + ord(tempc) - ord('0'); tempc := getc end; '.' : begin cp := fp; tempc := getc end else cp := out end; fp : case tempc of '0' '9' : begin d := d/10; v := v + (ord(tempc) - ord('0'))*d; tempc := getc end else cp := out end end; { оператора case cp of та циклу while} getcon := v end Функція getnam записується аналогічно й залишається для самостійної розробки. 9.5. Читання символів Нарешті ми уточнимо, як читаються символи виразу з тексту, написавши функцію getc добування наступного символу. Її розробку почнемо з уточнення задання виразу. Нехай вираз записано в текстовому файлі, у кількох рядках, довжини яких не більше 80. Ознакою кінця виразу є кінець файла. Суміжні лексеми відокремлюються довільними послідовностями пропусків, можливо, порожніми. Скористаємося обмеженням на довжину рядків тексту та організуємо читання тексту не окремими символами, а рядками. Черговий рядок стає значенням змінної рядкового типу Str, яка називається образом вхідного рядка, або буфером. Саме з буфера символи по одному добуваються за викликів функції getc. Функцію getc разом із іншими необхідними означеннями помістимо в окремий модуль Inbuf. Створюючи цей модуль, ми повністю відокремлюємо обробку символів виразу від їх конкретного джерела – файла на диску, клавіатури чи ще чогось. Додамо указання використання модуля Inbuf до модуля Glx. Для роботи з буфером, тобто змінною buf типу Str, додамо змінні bufl, bufp та tempc, що зберігатимуть відповідно довжину буфера (кількість символів), позицію в ньому, якою закінчується оброблена частина виразу, та її останній, або поточний символ. Означимо ще сталу finch = chr(0), яка стає значенням поточного символу при закінченні виразу. Стала finch та змінна tempc експортуватимуться з модуля, і за його межами рядок "буде видно крізь віконце tempc". Перенесемо означення імен finch і tempc з модуля Glx до модуля Inbuf. Ініціалізацію змінних модуля задає процедура bufinit, виклик якої записано в розділі ініціалізації. Вона також забезпечує можливість задати ім'я файла, з якого треба читати вираз. Функція newln описує заповнення буфера новим вхідним рядком та повернення його першого символу. Модуль Inbuf має такий загальний вигляд: