|
Страница 35 из 37
Простая программа синтаксического разбора выражений В оставшейся части данной главы рассматриваются две програм-
мы синтаксического разбора. Первая осуществляет синтаксический
разбор и вычисление константных выражений. Это синтаксический
разбор самого простого вида. Второй синтаксический анализатор
принимает до 26 задаваемых пользователем переменных от А до Z.
Далее целиком приводится простая версия программы рекурсив-
ного нисходящего синтаксического разбора для целых выражений. Она
принимает те же самые глобальные данные, что и процедура
GetToken, показанная ранее.
{********** синтаксический анализатор выражений *************}
procedure Level2(var result: real); forward;
procedure Level3(var result: real); forward;
procedure Level4(var result: real); forward;
procedure Level5(var result: real); forvard;
procedure Level6(var result: real); forward;
procedure Primitve(var result: real); forward;
{это точка входа в синтаксический анализатор }
procedure GetExp(var result: real);
begin
GetToken;
if length(token)<>0 then
Level2(result)
else
Serror(3);
end; {GetExp}
{процесс + или - }
procedure Level2;
var
op: char;
hold: real;
begin
Level3(result);
op: = token[1];
while((op='+') or (op='-') do
begin
GetToken;
Level3(hold);
arith(op, result, hold);
op: = token[1]
end;
end; {Level2}
{процесс * или \ }
procedure Level3;
var
op: char;
hold: real;
begin
Level4(result);
op: = token[1];
while ((op '*') or (op='/')) do
begin
GetToken;
Level4(hold);
arith(op, result, hold);
op: = token[1];
end;
end; {Level3}
{процесс ^ (возведение в степень)}
procedure Level4;
var
hold: real;
begin
Level5(result);
if token[1]='^' then
begin
GetToken;
Level4(hold);
arith('^', result, hold); {exponents}
end;
end; {Level4}
{процесс унарного оператора}
procedure Level5;
var
op: char;
begin
op: = ' ';
if((TokType=DELIMITER) and ((token[1]='+') or
(token[1]='-')))
then begin {unary plus or minus}
op:= token[1];
GetToken;
end;
Level6(result);
if op='-' then result: = -result;
end; {Level5}
{процесс скобок }
procedure Level6;
begin
if(token[1]='(') and (TokType=DELIMITER) then
begin {Parenthesized expression}
GetToken;
Level2(result);
if token[1]<>')'then Serror(2);{скобки не сбалансированы}
GetToken;
end
else Primitive(result);
end; {Level6}
{ найти значение числа}
procedure Primitive;
begin
if TokType=DELIMITER then
val(token, result, code)
else Serror(1);
GetToken;
end.
Программа, как показано, может принимать операторы +,-,* и
/, а также возведение в степень (^), унарный минус и скобки. Она
имеет шесть уровней, а также функцию Primilive, которая возвраща-
ет значение целого числа. Команда foevard необходима, так как не-
которые из этих процедур взаимно рекурсивны, следовательно, не
возможно определить все процедуры до обращения к ним.
В дополнение к синтаксическому анализатору существует нес-
колько процедур для специальных целей: Serror, которая сообщает о
синтаксических ошибках, Pwr и Arith, которые выполняют различные
арифметические операции. Эти подпрограммы показаны далее:
{отображение сообщений об ошибках }
Procedure Serror(i: integer);
begin
case i of
1: WriteLn('синтаксическая ошибка ');
2: WriteLn('несбалансированные скобки');
3: WriteLn('выражение отсутствует ');
end;
end; {Serror}
{возведение в степень }
function Pwr(a, b: real): real;
var
t: integer;
temp: real;
begin
if a=0 then Pwr: = 1 else
begin
temp: = a;
for t: = trunc(b) cownto 2 do a: = a*temp;
Pwr: = a;
end;
end;
{данная функция выполняет заданные арифметические операции}
procedure Arith(op: char; var result, operand: real);
begin
case op of
'+': result: = result+operand;
'-': result: = result-operand;
'*': result: = result*operand;
'/': result: = result/operand;
'^': result: = result^operand;
end;
end; {Arith}
Как показано ранее, в двух глобальных переменных token и
TokType возвращаются очередная лексема и ее тип, а строка prog
содержит выражение.
Далее представлен синтаксический анализатор с процедурами
поддержки, а также простые программы, которые могут быть исполь-
зованы для демонстрации синтаксического анализатора.
{ Данная программа демонстрирует работу синтаксического
анализатора. Она не принимает переменных и поддерживает
числа только типа real (действительные)}
program parser;
type
str80 = string[80];
TType = (DELIMITER, VARIABLE, NUMBER);
var
token, prog: str80;
TokType: TType;
code, t: integer;
result: real;
{данная функция возвращает TRUE, если ch является буквой
алфавита}
function IsAlpha(ch: char): boolean;
begin
IsAlpha:= (UpCase(ch)>='A') and (UpCase(ch)<='Z');
end; {IsAlpha}
{данная функция возвращает TRUE, если ch является
символом новой строки, табуляции или пробелом }
function IsWhite(ch: char): boolean;
begin
IsWhite: = (ch=' ') or (ch=chr(9)) or (ch=chr(13));
end; {IsWhite}
{данная функция возвращает TRUE, если ch является
разделителем}
function IsDelim(ch: char): boolean;
begin
if pos(ch, ' +-/*%^=()S')<>0 then IsDelim: = TRUE
end; {IsDelim}
{данная функция возвращает TRUE, если ch - цифра от 0 до 9}
function IsDigit(ch: char): boolean;
begin
IsDigit: = (ch>='0') and (ch<='9');
end; {IsDigit}
{GotToken считывает следующую лексему из входного потока}
procedure GetToken;
var
temp: str80;
begin
token: = ''; {пустая строка }
while(IsWhite(prog[t])) do t:=t+1; {пропустить
предшествующие пробелы}
if prog[t]='S' then token: = 'S';
if pos(prog[t], '+-*/%^=()')<>0 then
begin
TokType: = DELIMITER;
token: = prog[t]; {является оператором }
t: = t+1;
end else if IsAlpha(prog[t]) then
begin
While(not IsDelim(prog[t])) do
begin
token: = concat(token, prog[t]); { построить лексемы }
t: = t+1;
end;
TokType: = VARIABLE;
end
else if IsDigit(prog[t]) then
begin
while(not IsDelim[t])) do
begin
token: = concat(token,prog[t]); { построить число }
t: = t+1;
TokType: = NUMBER;
end;
end;
end; {GetToken}
{отображение сообщений об ошибках }
Procedure Serror(i: integer);
begin
case i of
1: WriteLn('синтаксическая ошибка ');
2: WriteLn('несбалансированные скобки');
3: WriteLn('выражение отсутствует ');
end;
end; {Serror}
{возведение в степень }
function Pwr(a, b: real): real;
var
t: integer;
temp: real;
begin
if a=0 then Pwr: = 1 else
begin
temp: = a;
for t: = trunc(b) cownto 2 do a: = a*temp;
Pwr: = a;
end;
end;
{данная функция выполняет заданные арифметические операции}
procedure Arith(op: char; var result, operand: real);
begin
case op of
'+': result: = result+operand;
'-': result: = result-operand;
'*': result: = result*operand;
'/': result: = result/operand;
'^': result: = result^operand;
end;
end; {Arith}
{********** синтаксический анализатор выражений *************}
procedure Level2(var result: real); forward;
procedure Level3(var result: real); forward;
procedure Level4(var result: real); forward;
procedure Level5(var result: real); forward;
procedure Level6(var result: real); forward;
procedure Primitive(var result: real); forward;
{это точка входа в синтаксический анализатор }
procedure GetExp(var result: real);
begin
GetToken;
if Length(token)<>0 then
Level2(result)
else
Serror(3);
end; {GetExp}
{процесс + или - }
procedure Level2;
var
op: char;
hold: real;
begin
Level3(result);
op:= token[1];
while(op='+') or (op='-') do
begin
GetToken;
Level3(hold);
arith(op, result, hold);
op: = token[1];
end;
end; {Level2}
{процесс * или \ }
procedure Level3;
var
op: char;
hold: real;
begin
Level4(result);
op: = token[1];
while (op='*') or (op='/') do
begin
GetToken;
Level4(hold);
arith(op,result,hold);
op: = token[1];
end;
end; {Level3}
{процесс ^ (возведение в степень)}
procedure Level4;
var
hold: real;
begin
Level5(result);
if token[1]='^' then
begin
GetToken;
Level4(hold);
arith('^',result,hold); {exponents}
end;
end; {Level4}
{процесс унарного оператора}
procedure Level5;
var
op: char;
begin
op: = ' ';
if((TokType=DELIMITER) and ((token[1]='+') or
(token[1]='-')))
then begin
op: = token[1],
GetToken;
end;
Level6(result);
if op='-' then result: = -result;
end; {Level5}
{процесс скобок }
procedure Level6;
begin
if(token[1]='(') and (TokType=DELIMITER) then
begin {заключенное в скобки выражение }
GetToken;
Level2(result);
if token[1]<>')'then Serror(2);{несбалансированные
скобки}
GetToken;
end
else Primitive(result);
end; {Level6}
{ найти значение числа }
procedure Primitive;
begin
if TokType=NUMBER then
val(token, result, code)
else Serror(1);
GetToken;
end;
begin {nain}
repeat
t:=1; {инициализировать счетчик лексем }
Write('Введите выражение: ');
ReadLn(prog);
prog:=concat(prog, '$');
if(prog<>'quit$') then
begin
GetExp(result);
writeLn(result);
end;
until prog='quit$'
end.
Программа позволяет вам ввести численное выражение, для ко-
торого она вычислит ответ. Для выхода из программы напечатайте
QUIT.
Для понимания того, как синтаксический анализатор вычисляет
выражение, поработайте со следующим выражением, которое после
приема содержится в prog:
10-3*2
Когда вызывается GetExp (начальная процедура в синтакси-
ческом анализаторе), она берет первую лексему и, если она явля-
ется пустой, печатает сообщение no expression present (выражение
отсутствует) перед возвратом. Если лексема присутствует, то вызы-
вается level2 (level1 будет добавлена к синтаксическому анализа-
тору позднее, когда будет добавлен оператор назначения, а сейчас
она не нужна).
Лексема теперь содержит число 10. level2 вызывает level3, а
level3 вызывает level4, которая в свою очередь вызывает level5.
level5 проверяет, является ли лексема унарным оператором + или -;
в данном случае это не так и, поэтому, вызывается level6. level6
рекурсивно вызывает level2 в случае заключенного в скобки выраже-
ния или вызывает Primitive для нахождения целого значения. Нако-
нец, когда Primitive выполнится и значение 10 поместится в
reselt, процедура GetToken получит следующую лексему. Затем функ-
ции начнут возвращать управление назад по цепочке. Теперь лексема
- это оператор "-" и функции возвратятся до level2.
Следующий шаг очень важен. Так как лексемой является опера-
тор "-", она сохраняется и GetToken получает новую лексему 3;
нисходящая вниз цепочка начинается вновь. Снова вызывается
Primitive, целое число 3 возвращается в result и считывается лек-
сема *. В данном случае управление возвращается к Level3, где
считывается финальная лексема 2. В этой точке совершается первая
арифметическая операция умножения 2 на 3. Этот результат затем
возвращается к level2 и выполняется вычитание, которое дает ре-
зультат 4.
Хотя процесс сначала может показаться запутанным, вы должны
проработать другие примеры для самопроверки.
Вы могли бы использовать этот синтаксический анализатор, как
настольный калькулятор. Вы также могли бы использовать его в ба-
зах данных и других не сложных случаях. Прежде, чем можно было бы
применить его в языках и сложных калькуляторах, синтаксический
анализатор должен быть способен поддерживать переменные, которые
являются предметом следующего раздела.
|