Turbo Pascal Examples. Синтаксический анализатор.

Столь туманное объяснение пропробую прояснить на конкретном примере.

Пусть есть функция

F(x) = (x**3-5)*(x+5*(x-1))/(3*x+4)*x

Обозначим:

Часть1[x] = x**3-5;
Часть2[x] = x-1;
Часть3[x] = 3*x+4;

Тогда исходное выражение можно записать в виде:

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;
Часть2[x] = 1;
Часть3[x] = 10;
Часть4[x] = 7;
И F(x) = "3*7/10*x"

Как видно выражение для части 4 и для самой функции уже не попадают под прямое определение многочлена. Поэтому сам объект mnogochlen был также модифицирован так, чтобы он мог принимать соответствующие значения. В данном примере он способен распознавать функции представляющие из себя конечную сумму элементов, каждый из которых представляет из себя конечное произведение констант и переменныех х. Кроме того, допустима операция деления (косая черта) и возведение в степень для последнего сомножителя.

Теперь как работает алгоритм распознавания частей. Написана функция setExpressionParts, которая возвращает обработанную (часть) строки. "Обработанную" означает "не содержащую парных (отрывающей/закрывающей) скобок внутри которых не содержится больше никаких скобок". Функция рекурсивная то есть обращается сама к себе при необходимости. Алгоритм таков. Берем первыую открывающую скобку и ищем закрывающую к ней. Если такие скобки найдены, то записываем эту строку в массив под очередным индексом k, а на место найденного записываем строку @@k#. Если же до закрывающей нашлась еще одна открывающая, то отстаток строки от второй открывающей до конца передаем в качестве параметра той же функции.

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;