Сторінка
4
then writeln( llxval( Llx ) ) end. Розробка функцій ipllx і llxval розкривається в наступних двох підрозділах. 20.6. Уточнення алгоритму побудови ЗПЗ Напишемо функцію ipllx читання та побудови ЗПЗ виразу, з якої повертається ознака відсутності помилок у виразі. Зробимо уточнення постановки задачі: будемо вважати, що вхідні вирази не містять імен змінних, а елементарними позначеннями операндів є лише числові сталі. Читання чергової лексеми виразу задається функцією getlx із модуля Glx, в якому також означено типи Tlx і Ttlx лексем та їхніх різновидів. Вважатимемо, що модуль Sllx містить усе необхідне для роботи з послідовністю та магазином лексем, які подаються змінними типів Sqlx і Stlx відповідно. Ініціалізація порожніх послідовності та магазина задається процедурами із заголовками відповідно procedure initl( var Llx : Sqlx ); procedure inits( var Slx : Stlx ); запис лексеми в магазин – процедурою із заголовком procedure push( var Slx : Stlx; lx : Tlx ); вилучення лексеми з магазина та повернення її типу – функцією function pop( var Slx : Stlx; var lx : Tlx) : Ttlx; добування лексеми з верхівки магазина без вилучення та повернення її типу – функцією function gett(Slx : Stlx; var lx : Tlx ) : Ttlx; додавання лексеми в кінець списку – procedure put( var Llx : Sqlx; lx : Tlx ). Крім того, функція prior задає обчислення пріоритетів лексем. Читання чергової лексеми задається в модулі Glx функцією getlx, заголовок якої function getlx(var lx : Tlx) : boolean; з її виклику повертається ознака наявності чергової лексеми та сама лексема за допомогою параметра-змінної. Розроблювана функція ipllx матиме одну особливість. Після того, як вираз прочитано, в магазині ще можуть залишитися знаки операцій; за алгоритмом вони записуються у вихідну послідовність. У цій функції весь вхідний вираз штучно "береться в дужки". Перед його читанням у магазин записується відкриваюча дужка, що відмічає його дно. В кінці магазин лексем обробляється так, ніби на вході з'явилася закриваюча дужка, тобто всі знаки до відкриваючої дужки виштовхуються та копіюються у вихідну послідовність. function ipllx ( var Llx : Sqlx ) : boolean; var Slx : Stlx; lx, lx1 : Tlx; lt : Ttlx; ok : boolean; begin initl( Llx ); inits( Slx ); ok := true;
lx.stl := par; lx.prt := '(';
push( Slx, lx); while (getlx( lx ) and ok) do case lx.stl of con : put(Llx, lx); par : case lx.prt of '(' : push( Slx, lx); ')' : while pop(Slx, lx1) <> par do put( Llx, lx1); end; ops : begin lt := gett( Slx, lx1); while ( lt = nam ) or ( ( lt = ops ) and (prior(lx1.sig) >= prior(lx.sig) ) do begin lt := pop( Slx, lx1); put( Llx, lx1); lt := gett( Slx, lx1) end; push( Slx, lx) end; nam : push( Slx, lx) else ok := false end; {case та while} if ok then while pop( Slx, lx1) <> par do put(Llx, lx1); ipllx := ok end; Ця підпрограма має суттєвий недолік. Справа в тім, що вона не задає структурного, або синтаксичного, аналізу вхідного ланцюжка символів. Наприклад, недопустима вхідна послідовність лексем "1 2 3 + *" буде прочитана та оброблена як інфіксний вираз, за ним буде створено ЗПЗ "1 2 3 * +", а далі обчислено значення 7, що не має ніякого змісту. Поняття, необхідні для аналізу структури виразів, розглядаються в розділі 21.
7. Уточнення алгоритму обчислення виразу Напишемо функцію llxval обчислення значення виразу за його ЗПЗ, що подається послідовністю лексем. У цій функції використовуються засоби з модуля SLlx: - функція перевірки вичерпання послідовності лексем із заголовком function isemllx ( Llx : Sqlx ) : boolean; -процедура добування й вилучення першого елемента послідовності лексем із заголовком procedure get ( var Llx : Sqlx; var lx : Tlx ). Крім того, використовуються підпрограми обробки магазина лексем, про які сказано в попередньому підрозділі. function llxval ( var Llx : Sqlx ) : real;
var Slx : Stlx; lx, lx1, lx2 : Tlx; ok : boolean; begin inits( Slx ); ok := true; while not isemllx( Llx ) and ok do begin get( Llx, lx); case lx.stl of con : push( Slx, lx ); ops : begin pop( Slx, lx2 ); pop( Slx, lx1 ); case lx.sig of '+' : lx1.numb := lx1.numb + lx2.numb; '-' : lx1.numb := lx1.numb - lx2.numb; '*' : lx1.numb := lx1.numb * lx2.numb; '/' : if lx2.numb <> 0 then lx1.numb := lx1.numb / lx2.numb else ok := false end; if ok then push( Slx, lx1 ) end; nam : begin pop( Slx, lx1 ); if lx.name = 'sin' then lx1.numb := sin( lx1.numb ) else if lx.name = 'cos' then lx1.numb := cos( lx1.numb ); push( Slx, lx1 ) end end { case lx.stl } end; { while } if ok then begin pop( Slx, lx1); llxval := lx1.numb end else begin
writeln( '***zerodivide***' ); llxval := 0 end end;
8. Множини в мові Паскаль У підпрограмах розроблюваного модуля читання лексем доведеться мати справу з множинами символів. Подання та обробку множин символів та значень інших перелічуваних типів у мові Паскаль зручно задавати з використанням спеціальних типів множин. Стала-множина задається в дужках [] переліком елементів або діапазонів. Наприклад, множина чисел {1, 2, 3, 5} подається як [1, 2, 3, 5] або [1 3, 5], порожня множина Æ – як [], множина символів {'a', 'i', 'j', 'k', 'l', 'm', 'n'} – як ['a', 'i' 'n']. Якщо T задає перелічуваний тип, то вираз set of T означає множинний тип. Елементами його носія є підмножини носія типу T. Наприклад, носій типу set of Boolean складається з 4-х множин бульових значень: [], [false], [true], [false, true]; носій типу set of 'a' 'z' – з 226 підмножин малих латинських літер. Тип T називається базовим для типу set of T. В історії розвитку мови Паскаль склалося так, що носій базового типу не може мати більше 256 елементів. Наприклад, вираз set of 1 512 недопустимий. У внутрішньому зображенні множини кожному елементу носія базового типу відповідає 1 біт і дані множинних типів займають не більше 256/8 = 32 байтів. Найпростішими виразами типу множина є сталі, тобто списки виразів і діапазонів базового типу в квадратних дужках []. Інші вирази будуються з однотипних множинних сталих і змінних та знаків бінарних операцій '+', '*', '-', що позначають відповідно об'єднання, перетин і різницю множин. Приклад. Нехай за дії означення var v : set of 0 9 виконано оператор присвоювання v:=[1 3]. Тоді вираз v+[2 4] має значення [1 4], v*[2 4] – значення [2 3], v-[2 4] – значення [1].ç Бульові вирази вигляду S1 = S2 (S1 <> S2) задають перевірку на рівність (нерівність) значень однотипних множинних виразів S1 і S2. Аналогічно вирази S1 <= S2 (S1 >= S2) задають перевірку включення S1 у S2 (S2 в S1). Наприклад, значеннями виразів [1 3]=[1, 2, 3] та [1, 2]<=[1 3] є true, а виразів [1]>=[1 2] та [1, 2]<>[2, 1] – false. Булів вираз вигляду e in S, де тип виразу e є базовим для множинного типу виразу S, задає перевірку належності значення e множині S. Вирази типу множина можна присвоювати змінним того ж самого типу. Приклад 20.4. Нехай діє означення типів рядків Str і множин символів SS = set of char. Тоді: 1) процедура Symset задає побудову множини SS символів рядка A: procedure Symset ( A : Str; var S : SS ); var i : integer; begin S := []; for i:= 1 to length(A) do S := S + [ A[i] ] end; 2) функція EqSS задає перевірку рівності множин символів двох рядків: function EqSS ( A, B : Str ) : boolean; var S1, S2 : SS; begin Symset (A, S1); Symset (B, S2); EqSS := (S1 = S2) end; 3) функція SettoStr задає побудову рядка з символів-елементів множини в порядку їхнього кодування: function SettoStr ( S : SS) : Str; var A : Str; c : char; begin A := ''; for c := chr(0) to chr(255) do if c in S then A := A + c; SettoStr := A end.
Завантажити реферат