HOME ПРИМЕРЫ THANKS НОВИЧКАМ ДОКИ LINKS JavaScript Mail |
|
|
Turbo Pascal Examples. Синтаксический анализатор. |
Графика: В прошлом примере был разобран случай простейшего синтаксического анализатора реализующий разбор многочлена от одной переменной х представляющего конечную сумму элементов вида a*x**n. В приведенном ниже примере сделан шаг к усложнению функции, которая может быть преобразована из строкового представления в вид пригодный для выполнения вычислений при заданном значинии переменной х. Если обозначить за М многочлен одной переменной рассмотренный в прошлом примере, то здесь допустимы любые арифметические выражения с многочленами заключенными в скобки. То есть может быть вычислено выражение вида: В = M0*(M1 +(M2)*(M3))/(M4 + (M6)/(M7)) Алгоритм вычислений таков. Столь туманное объяснение пропробую прояснить на конкретном примере. Пусть есть функция F(x) = (x**3-5)*(x+5*(x-1))/(3*x+4)*x Обозначим:
Часть1[x] = x**3-5; Тогда исходное выражение можно записать в виде: F(x) = Часть1[x]*(x+5*Часть2[x])/Часть3[x]*x Можно еще обозначить: Часть4[x] = x+5*Часть2[x]; Тогда функция будет представлена записью не содержащей скобок, чего, собственно, мы и добиваемся: F(x) = Часть1[x]*Часть4[x]/Часть3[x]*x Как видно, чтобы вычислить первые три части, можно передать строковое представление фукции объекту mnogochlen и воспользовшись его функцией value вычислить значения частей для каждого конкретного х. А после того как вычислены первые три части в выражении для части 4 можно подставить числовое значение выраженное в виде строки и полученную строку опять прогнать через объект многочлен. Например для х=3 часть 4 будет иметь вид: "x+5*2". И последним для этого примера шагом будет вычисление всей функции, которая для каждого конкретного х при вычисленных частях будет представлять строковое представление вида многочлен. Например для x=2
Часть1[x] = 3; Как видно выражение для части 4 и для самой функции уже не попадают под прямое определение многочлена. Поэтому сам объект mnogochlen был также модифицирован так, чтобы он мог принимать соответствующие значения. В данном примере он способен распознавать функции представляющие из себя конечную сумму элементов, каждый из которых представляет из себя конечное произведение констант и переменныех х. Кроме того, допустима операция деления (косая черта) и возведение в степень для последнего сомножителя. Теперь как работает алгоритм распознавания частей. Написана функция setExpressionParts, которая возвращает обработанную (часть) строки. "Обработанную" означает "не содержащую парных (отрывающей/закрывающей) скобок внутри которых не содержится больше никаких скобок". Функция рекурсивная то есть обращается сама к себе при необходимости. Алгоритм таков. Берем первыую открывающую скобку и ищем закрывающую к ней. Если такие скобки найдены, то записываем эту строку в массив под очередным индексом k, а на место найденного записываем строку @@k#. Если же до закрывающей нашлась еще одна открывающая, то отстаток строки от второй открывающей до конца передаем в качестве параметра той же функции.
|
Например, для функции F(x) рассмотренной выше будут выполнены следующие шаги:
Для работы со строками написаны вспомогательные процедуры: Также написана процедура xPowerN вычисления степенной функции x N Смотри также комментарии в самой программе. |
{$M 64384,0,655360} const maxN = 20; arrStrN = 40; type component = object { a component of mnogochlen: an*x**n} a:real; n:integer; function value(x:real):real; procedure setComponent(aVal:real;nVal:integer); end; mnogochlen = object n:byte; c:array[1..maxN] of component; procedure init(s1:string); function value(x:real):real; end; expression = object n: byte; { число частей } expS, { массив частей (строки) } expSwork: array[1..maxN] of string; { рабочий массив частей для расчетов } expV: array[1..maxN] of real; { числовой массив частей } procedure init(s:string); function setExpressionParts(s:string;var partNo:byte):string; function value(x:real):real; end; str_arr = array [1..arrStrN] of string; {*****************************************} function xPowerN(x:real;n:integer):real; { Возвращает х в степени n } const eps = 1e-8; { полагаем число нулем, если меньше eps } var z:shortint; r:real; begin if n=0 then xPowerN := 1 { любое число в нулевой степени = 1 } else if abs(x)<eps then xPowerN := 0 { 0 в любой положительной степени = 0 } else begin r := exp(n*ln(abs(x))); z := 1; if (x<0) then z := -1; if n mod 2 = 0 then xPowerN := r { четная степень всегда положительна } else xPowerN := z * r { нечетная сохраняет знак } end; end; {*****************************************} function component.value(x:real):real; { Вычисление значения одной компоненты при заданном х } begin value:=a*xPowerN(x,n); end; procedure component.setComponent(aVal:real;nVal:integer); begin a:=aVal; n:=nVal; end; function mnogochlen.value(x:real):real; { Вычисление значения многочлена при заданном х } var s:real; i:byte; begin s:=0; for i:=1 to n do s:=s+c[i].value(x); value:=s; end; {*****************************************} { String functions } function explode(sep,s:string;var a:str_arr):integer; { Разбить строку s на кусочки подстрокой sep и записать результат в строковый массив str_arr. Сама функция вернет число кусочков Например: explode('mp','This is an simple example',a) вернет число 3, и строки в массиве a: a[1]='This is an si'; a[2]='le exa'; a[3]='le'; explode(' ','This is an simple example',a) - вернет 5 и отдельные слова в массиве a 'This','is','an','simple','example' } var L:byte absolute s; i,n,k,d:byte; begin n:=0; for i:=1 to arrStrN do a[i]:=''; k:=Pos(sep,s); d:=length(sep)-1; while (L*k>0) do begin inc(n); a[n]:=copy(s,1,k-1); delete(s,1,k+d); k:=Pos(sep,s); end; inc(n); a[n]:=s; explode:=n; end; function strReplace(findWhat,replaceTo,inString:string):string; { В строке inString заменить все вхождения подстроки findWhat на подстроку replaceTo } var sa:str_arr; n,i:byte; res:string; begin n:=explode(findWhat,inString,sa); res:=sa[1]; for i:=2 to n do res:=res+replaceTo+sa[i]; strReplace:=res; end; function strReplaceFirst(findWhat,replaceTo,inString:string):string; var k:byte; s:string; begin k:=Pos(findWhat,inString); if (k>0) then begin Delete(inString,k,length(findWhat)); Insert(replaceTo,inString,k); end; strReplaceFirst:=inString; end; function strReplaceN(findWhat,replaceTo,inString:string; nFirstTimes:byte):string; { В строке inString заменить nFirstTimes первых вхождений подстроки findWhat на подстроку replaceTo } var sa:str_arr; n,i:byte; res:string; begin n:=explode(findWhat,inString,sa); res:=sa[1]; for i:=2 to n do if (i-1<=nFirstTimes) then res:=res+replaceTo+sa[i] else res:=res+findWhat+sa[i]; strReplaceN:=res; end; function strToInt(s:string):integer; { Преобразовать строку к целому числу. } var i, code: Integer; begin val(s, i, code); if code <> 0 then begin WriteLn('strToInt. Error at position: ', code, ' in line ', s, '. Program halted'); halt end else strToInt := i; end; function strToReal(s:string):real; { Преобразовать строку к вещественному числу. } var code: Integer; r: real; begin s:=strReplaceFirst('EM','E-',s); s:=strReplaceFirst('EP','E+',s); val(s, r, code); if code <> 0 then begin WriteLn('strToReal. Error at position: ', code, ' in line ', s, '. Program halted'); halt end else strToReal := r; end; function realToString(r:real):string; var s: string[20]; begin Str(r:14:8, s); realToString:=s; end; {*****************************************} procedure mnogochlen.init(s1:string); { Данная процедура принимает в качестве параметра строковое представление функции переменной х, представляющей из себя многочлен с некоторыми расширениями. После выполнения параметры объекта mnogochlen оказыаются заполненными и можно вызвать метод value(x) для вычисления значения функции при конкретном х } var i,j,j2,nParts,t1,t2,t3:byte; b,sc,dl:str_arr; xPower,s2:string; xPowerInt,minus:integer; begin for i:=1 to maxN do c[i].setComponent(0,0); s1:=strReplace(' ','',s1); { Убираем все пробелы } s1:=strReplace('E+','EP',s1); { Временно заменили символы плюс и минус выражающие степень цифрового занчения вещественных переменных 1.00E+01 } s1:=strReplace('E-','EM',s1); s1:=strReplace('*-','*M',s1); { данная временная замена нужна для предотвращения последующей замены этого минуса на +- и добавления еще одного слагаемого. Пример 5+x*-3 } s1:=strReplace('/-','/M',s1); { или 5*8/-x } { Далее мы будем разбивать строку на части содержащие слагаемые. Заменим знаки '-' на '+-', чтобы заменить вычитание на прибавление отрицательного слагаемого. Первый минус, если он есть, заменять не надо, иначе появится "пустое" слагаемое } if (s1[1]='-') then s1:='-'+strReplace('-','+-',copy(s1,2,255)) else s1:=strReplace('-','+-',s1); { возвращаем обратно знаки *- и /- } s1:=strReplace('*M','*-',s1); s1:=strReplace('/M','/-',s1); nParts:=explode('+',s1,b); { Разбили на слагаемые } n:=nParts; for i:=1 to nParts do begin { Здесь возможна ситуация, когда множитель в слагаемом появляется с отрицательным знаком: 2*-x*4*-x. Выносим все минусы множителей вперед } s2:=b[i]; j:=pos('-',s2); minus:=1; while j>0 do begin minus:=-minus; Delete(s2,j,1); j:=pos('-',s2); end; if (minus<0) then s2:='-1*'+s2; s2:=strReplace('**','^^',s2); { Разбиваем на множители } t2:=explode('*',s2,sc); { Проверим есть ли в каком-либо из множителей знак деления } j:=1; while (j<=t2) do if (pos('/',sc[j])>0) then begin t3:=explode('/',sc[j],dl); { В данном множителе sc[j] найдено t3-1 делителей и одно делимое. Каждый делитель запишем как множитель в минус первой степени. Это значит у нас в исходном массиве прибавилось t3-1 множителей. Сдвинем оставшиеся в массиве sc справа множители на t3-1 позиции вправо } for j2 := t2 downto j+1 do sc[j2+t3-1]:=sc[j2]; { Теперь на освободившееся после сдвига места вписываем найденные делители } sc[j]:=dl[1]; { делимое } for j2:=2 to t3 do sc[j+j2-1]:=dl[j2]+'^^-1'; { делители } j:=j+t3; t2:=t2+t3-1; { увеличили количество множителей t2 } end else j:=j+1; c[i].setComponent(1,0); for j:=1 to t2 do begin { проверяем имеет ли множитель показатель степени } t1:=explode('^^',sc[j],dl); if (dl[2]='') then xPowerInt:=0 else xPowerInt:=strToInt(dl[2]); if t1<2 then { показателя степени нет. Значит данный множитель либо 'x' либо константа } if (sc[j]='x') then inc(c[i].n) else c[i].a := c[i].a * strToReal(sc[j]) else { явно задана степень. Данный множитель либо степень х либо степень константы } if (dl[1]='x') then inc(c[i].n,xPowerInt) else c[i].a := c[i].a * xPowerN(strToReal(dl[1]),xPowerInt) end; end; end; {*****************************************} function expression.setExpressionParts(s:string;var partNo:byte):string; { Функция разбирает выражение заданное строкой s на части. } var openBracketK1,openBracketK2,closeBracketK,t:byte; st,internalPart,partNoSt:string; begin openBracketK1 := Pos('(',s); while (openBracketK1 <>0) do begin { временно убираем все закрывающие скобки, которые стоят до открывающей } t:=Pos(')',s); while (t<openBracketK1) do begin s:=strReplaceFirst(')',']',s); t:=Pos(')',s); end; st := copy(s,openBracketK1+1,255); { часть исходной строки от первой открывающей скобки до конца } openBracketK2 := Pos('(',st); { следующая открывающая скобка } if (openBracketK2>0) then openBracketK2:=openBracketK2 + openBracketK1; { позиция второй откры вающей скобки в исходной строке s } closeBracketK := Pos(')',s); if ((openBracketK2>closeBracketK) or (openBracketK2=0)) then { вторая открывающая скобка стоит за первой закрывающей или нет больше открывающих скобок } begin { найдена отдельная часть в скобках. Выделяем ее и записываем в массив частей. На ее место в исходной строке записываем указатель на данную часть в виде строки @@N#, где N целое число. Пример @@4#. } inc(partNo); Str(partNo,partNoSt); internalPart:=copy(s,openBracketK1+1,closeBracketK-openBracketK1-1); s:=strReplaceFirst('('+internalPart+')','@@'+partNoSt+'#',s); expS[partNo]:=internalPart; end else { первая скобка не закрылась, а вторая уже открылась. Значит внутри есть еще одна часть, подлежащая обработке } begin st:=copy(s,openBracketK2,255); { кусок от второй скобки до конца } st:=setExpressionParts(st,partNo); { обрабатываем этот кусок } s:=copy(s,1,openBracketK2-1)+st; { соединяем обработанный кусок с началом строки } end; openBracketK1 := Pos('(',s); end; { while } s:=strReplace(']',')',s); setExpressionParts:=s; end; procedure expression.init(s:string); var i:byte; begin n := 0; for i:=1 to maxN do begin expS[i]:=''; expV[i]:=0; end; s := setExpressionParts(s,n); inc(n); expS[n]:=s; end; function expression.value(x:real):real; var mng:mnogochlen; i,k,t:byte; r:real; compNo:string; begin for i:=1 to n do begin expSwork[i]:=expS[i]; k := pos('@@',expSwork[i]); while (k>0) do begin t:=pos('#',expSwork[i]); compNo:=copy(expSwork[i],k+2,t-k-2); r:=expV[strToInt(compNo)]; expSwork[i]:=strReplaceFirst('@@'+compNo+'#',realToString(r),expSwork[i]); k := pos('@@',expSwork[i]); end; mng.init(expSwork[i]); expV[i]:=mng.value(x); end; value := expV[n]; end; var s1,xPower:string; nParts:integer; mn:mnogochlen; ex:expression; i,part:byte; x,y:real; function F(x:real):real; { Для проверки } begin F:=3+5*4*3/2/4*12/x/x*x*2/2/3+8*2.1*3*x+4.54*x-x*3*x*x*x+6.5*x*x-2.6*x*x*x*x; end; function F2(x:real):real; { Для проверки } begin F2:=(x*x*x-5)*(x+5*(x-1))/(3*x+4)*x; end; begin { MAIN } { F(x) } for i:=1 to 43 do writeln; s1:='3+5*4*3/2/4*12/x/x*x*2/2/3+8*2.1*3*x+4.54*x-x*3*x**3+6.5*x**2-2.6*x**4'; writeln('F(x)=',s1); mn.init(s1); randomize; x:=5-random(1000)/100; writeln(' x=',x:8:3,' F(x)=',mn.value(x):8:3, ' Check: ',F(x):8:3); s1:='(x**3-5)*(x+5*(x-1))/(3*x+4)*x'; writeln('F2(x)=',s1); ex.init(s1); for i:=1 to 15 do begin x:=5-random(1000)/100; y:=ex.value(x); writeln(' x=',x:8:3,' F2(x)=',y:8:3, ' Check: ',F2(x):8:3); end; end.             |
HOME |