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;
whilenot 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 задає перелічуваний тип, то вираз setof T означає множинний тип. Елементами його носія є підмножини носія типу T. Наприклад, носій типу setof Boolean складається з 4-х множин бульових значень: [], [false], [true], [false, true]; носій типу setof 'a'..'z' – з 226 підмножин малих латинських літер. Тип T називається базовим для типу setofT.
В історії розвитку мови Паскаль склалося так, що носій базового типу не може мати більше 256 елементів. Наприклад, вираз setof 1..512 недопустимий. У внутрішньому зображенні множини кожному елементу носія базового типу відповідає 1 біт і дані множинних типів займають не більше 256/8 = 32 байтів.
Найпростішими виразами типу множинає сталі, тобто списки виразів і діапазонів базового типу в квадратних дужках []. Інші вирази будуються з однотипних множинних сталих і змінних та знаків бінарних операцій '+', '*', '-', що позначають відповідно об'єднання, перетин і різницю множин.
Приклад. Нехай за дії означення var v : setof 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.
Булів вираз вигляду einS, де тип виразу e є базовим для множинного типу виразу S, задає перевірку належності значення e множині S.
Вирази типу множина можна присвоювати змінним того ж самого типу.
Приклад 20.4. Нехай діє означення типів рядків Str і множин символів SS = setof 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.
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 : setof 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'. Залежність різновиду від першого символу лексеми (за її наявності) подамо так: