HOME ПРИМЕРЫ THANKS НОВИЧКАМ ДОКИ LINKS JavaScript Mail


 
 

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

Графика:
Построение графика функции
Прыгающий по экрану мячик.
Качание маятника.
Вложенные цветные круги.
Броуновское движение. Использование объектов.
Матрицы и массивы:
Сортировка элементов массива.
Удаление одинаковых элементов.
Простой пример на поворот матрицы.
Сортировка методом Шелла. +функции измерения временных интервалов.
Проверка выпуклости многоугольника.
Перемоножение матриц
Вычисление определителя матрицы. Рекурсия.
Нахождение обратной матрицы.
Задача об автостоянке.
Рекурсия. Подземелье сокровищ.
Численные методы:
Задачка на определение угла между стрелками часов.
Проверка на принадлежность точки многоугольнику.
Нахождение точки пересечения двух отрезков на плоскости.
Сортировка методом Шелла. +функции измерения временных интервалов.
Сортировка методом "пузырька". Пример на динамические структуры данных. Связанные списки.
Нахождение корня функции методом половинного деления.
Вычисление арккосинуса
Нахождение суммы цифр натурального числа.
Работа с фалами:
Рекурсивное сканирование директорий.
Работа со строками:
Работа со словами в предложении с разделителями.
Простейший синтаксический анализатор для распознавания и вычисления многчлена.
Синтаксический анализатор для распознавания и вычисления многчлена.
Работа со строками: смена кодировки, удаление тегов из HTML текста, обработка
Переименование файлов из кириллицы в латиницу.
Выдача контекстной подсказки.
Частотный словарь символов.
Подсчет повторяющихся символов в строке.
Ссылочные переменные:
Моделирование стека.
Пасьянс "Косынка".
Игры:
Пасьянс "Косынка".
Игра "Питон"
Игра "Анацефал". Пример использования объектов.
Игра "Минное поле"
Большие проекты:
Электронная картотека (без исходника)


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


В прошлом примере был разобран случай простейшего синтаксического анализатора реализующий разбор многочлена от одной переменной х представляющего конечную сумму элементов вида a*x**n. В приведенном ниже примере сделан шаг к усложнению функции, которая может быть преобразована из строкового представления в вид пригодный для выполнения вычислений при заданном значинии переменной х. Если обозначить за М многочлен одной переменной рассмотренный в прошлом примере, то здесь допустимы любые арифметические выражения с многочленами заключенными в скобки. То есть может быть вычислено выражение вида:

В = M0*(M1 +(M2)*(M3))/(M4 + (M6)/(M7))

Алгоритм вычислений таков.

  • Разбиваем исходное строковое выражение на части, каждая из которых содержит строковое представление функции х вида "многочлен". Записываем эти части в строковый массив.
  • Для вычисления каждой из таких частей используем объект mnogochlen из прошлого примера.

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

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

    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;


  • Например, для функции F(x) рассмотренной выше будут выполнены следующие шаги:

    Номер обращения
    (глубина рекурсии)
    Строка s Найденное
    число
    частей
    Массив expS
    1 (x**3-5)*(x+5*(x-1))/(3*x+4)*x 0 ()
    1 @@1#*(x+5*(x-1))/(3*x+4)*x 1 ('x**3-5')
    2 (x-1))/(3*x+4)*x 1 ('x**3-5')
    2 @@2#)/(3*x+4)*x 2 ('x**3-5','x-1')
    2 @@2#]/@@3#*x 3 ('x**3-5','x-1','3*x+4')
    1 @@1#*(x+5*@@2#)/@@3#*x 3 ('x**3-5','x-1','3*x+4')
    1 @@1#*@@4#/@@3#*x 4 ('x**3-5','x-1','3*x+4','x+5*@@2#')



    Для работы со строками написаны вспомогательные процедуры:
  • explode - Разбить строку s на кусочки заданной подстрокой sep и записать результат в массив
  • strReplace - контекстный поиск и замена в строке
  • strReplaceFirst - контекстный поиск и замена первого вхождения подстроки в строке
  • strToInt и strToReal - преобразовать строку в число
    Также написана процедура 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