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

← →
Kisha © (2005-08-25 03:18) [0]

Дана формула:
<формула>::=<цифра>|(<формула><знак><формула>)
<цифра>- 0..9
<знак> - +,-,*
| - "логическое "или"
Требуется написать рекурсивную процедуру(функцию), которая вычислила бы результат данной формулы.
Например: ((5+3)*2)-1 = 15
Никак ничего в голову не приходит: как это организовать рекурсией?

← →
Fay © (2005-08-25 03:23) [1]

2 Kisha © (25.08.05 3:18)
Назовите, пожалуйста, ключевое слово вопроса
a) написать
b) рекурсивную
c) требуется
d) другое...

← →
Юрий Зотов © (2005-08-25 05:21) [2]

http://www.delphikingdom.com/asp/viewitem.asp?catalogid=10

← →
TStas © (2005-08-25 13:32) [3]

Я написал однажды модуль, который выполняет выражения со скобками. Полный текст приводить не буду, скажу идею саму. Просматривается исходная строка. Она в ней ищутся цифры и знаки действий. Найденные куски строки записываются с TList, элементы которого представляют собой или число, или знак действия или выражение со скобками.
list[9]:="2";
list[10]:="+";
list[11]:="10";
затем просматриваются все нечетные элементы списка, т.е. не знаки. Если это просто строка с числом, то выполняется IntToStr от нее, если выражениее со скобками, рекурсия. Получаем
list[9]:=2;
list[10]:="+";
list[11]:=10;

Написаны функция, которые могут выполнять простейшие выражения вида 2+3, например. Затем полученный TList просматривается в соответствии с приоритетом операторов, Вами установленным.

Если попадается, напрмимер
list[9]:=2;
list[10]:="+";
list[11]:=10;
понятно, что указатели на строки там находятся, вызывается функция подсчета выражения и стираются два элемента листа, получится
list[2]:=12;

Могу привести и весь модуль, но разбиретесь ли Вы в чужом коде.
Смысл такой конструкции в оптимизации, строка с исходными выражениями не просматривается по несколько раз и нет преобразования IntToStr - StrToINt. ИМХО это наиболее прямой способ

← →
Чапаев © (2005-08-25 13:39) [4]

Перевести в обратную польскую запись для начала...

ЗЫ. Учти, что в такой постановке задачи не учитывается приоритет операциё.

← →
Alexander Panov © (2005-08-25 13:51) [5]

Кроме вышеизложенного почитай про конечные автоматы.

← →
TStas © (2005-08-25 13:57) [6]

Вот сам модуль, там есть коментарии. Приоритет операций он учитывает, конечно, возведение в степень выполняет справа налево, деления в немнет, так как написан он для целых чисел.
http://stas258.narod.ru/frame.download/simpleEvalUnit.pas

← →
TStas © (2005-08-25 14:00) [7]

Неправильно ссылку написал, вот:
http://stas258.narod.ru/frame/download/simpleEvalUnit.pas

← →
TStas © (2005-08-25 14:01) [8]

>Чапаев ©
>Перевести в обратную польскую запись для начала...
А что такое польская запись?

← →
Officeman (2005-08-25 14:04) [9]

хм. кому нужен расчёт целых чисел? имхо неподходит!
идея я тя прикольная, но не додуманная.

кажется готовые компоненты есть. мне встречались кажется на сайте "сумасшедших бобров"

да и самому можно написать.

http://www.delphikingdom.com/asp/viewitem.asp?catalogid=10
хорошая статья

← →
TStas © (2005-08-25 14:06) [10]

Когда я писал этот модуль, мне нужны были иеммо целые числа, но без проблем они заменяются на числа с плавающей точкой и тогда добавляется деление. Модуль привел просто как пример. Вопрос вкедь был, как это сделать

← →
Юрий Зотов © (2005-08-25 14:39) [11]

> TStas © (25.08.05 13:32) [3]

Проверьте, как Ваш модуль сработает, например, на таком выражении:
-2*(-3)
Думаю, тут же и убедитесь, что поделка - она поделка и есть.

Существует теория компиляторов, где такие вещи давным-давно отработаны - вот ею и надо пользоваться (см. ссылку на статью). Польская запись - это оттуда, но в данном случае можно обойтись и без нее.

← →
Zeqfreed © (2005-08-25 14:40) [12]

Пожалуй и я поделюсь своими изысканиями в области разбора математических выражений =)

http://zeqfreed.k66.ru/files/math_parser_src.rar
(исходник класса с примером использования, 5 Кб)

http://zeqfreed.k66.ru/files/math_parser_bin.rar
(exe"шник примера использования, 192 Кб)

За основу кода был взят исходник парсера выражений из книги Герберта Шилдта "Полный справочник по C#". Насколько я помню, там нельзя было использовать ф-ции, в свою версию я добавил возможность использования ф-ций в выражениях.

← →
TUser © (2005-08-25 14:42) [13]

Вот код, который точно решает поставленную задачу, а заодно демонстрирует недостатки приведенной грамматики (если, конечно, задача состоит в вычислении значений произвольных арифметических выражений).

program R; {$apptype console} uses SysUtils; type TToken = (tkNum, tkEqu); function ReadExpression (const Input: string; ExpType: TToken; var Position: integer): integer; procedure Error; begin raise Exception.Create("IllegalExpression"); halt; end; function ReadNum: integer; begin result:=ord(Input[Position])-ord("0"); if (result < 0) or (result > 9) then Error; inc (Position); end; var a, b: integer; c: char; begin if Position >= length(Input) then Error; if ExpType = tkNum then result:=ReadNum else begin if Input[Position] <> "(" then result:=ReadExpression(Input,tkNum,Position) else begin Inc (Position); a:=ReadExpression(Input,tkEqu,Position); c:=Input[Position]; inc (Position); b:=ReadExpression(Input,tkEqu,Position); if Input[Position] <> ")" then Error; inc (Position); case c of "+": result:= a+b; "-": result:= a-b; "*": result:= a*b; end; end; end; end; var i: integer; begin i:=1; writeln (inttostr(ReadExpression("(5*(1+2))",tkEqu,i))); writeln (inttostr(ReadExpression("5*(1+2)",tkEqu,i))) end.

PS. Такую задачу лучше решать не с помощью рекурсий, али же автоматов, а с помощью алгоритма Дейкстры, который есть, например, на сайте http://algolist.manual.ru

← →
TUser © (2005-08-25 14:57) [14]

Ошибка

var i: integer; begin i:=1; writeln (inttostr(ReadExpression("(5*(1+2))",tkEqu,i))); i:=1; writeln (inttostr(ReadExpression("5*(1+2)",tkEqu,i))) end.

← →
TStas © (2005-08-25 14:59) [15]

>Юрий Зотов
-2*(-3) = 6 //Скопировано мышкой
Понятно, что он не образец, но пока не нашел в нем глюков

← →
Кабан (2005-08-25 15:14) [16]

а разве -2*(-3) = 6? :)

← →
TStas © (2005-08-25 15:24) [17]

>Кабан
А сколько? Разве -6?

← →
alex_*** (2005-08-25 15:25) [18]

а разве нет?

← →
alex_*** (2005-08-25 15:26) [19]

в смысле 6 будет :) это я к [16]

← →
Кабан (2005-08-25 15:27) [20]

2 TStas
оригинально... я вижу вы не шутите, естественно -6

← →
Alexander Panov © (2005-08-25 15:28) [21]

Кабан (25.08.05 15:27) [20]
оригинально... я вижу вы не шутите, естественно -6

В школу - арифметику изучать.

← →
Кабан (2005-08-25 15:29) [22]

сори, прошу прощения, совсем за работался, уже глюки пошли :)

← →
TStas © (2005-08-25 15:32) [23]

>Alexander Panov
Я чего-то сам путаться стал. Так 6 все-таки?:)

← →
Кабан (2005-08-25 15:33) [24]

6, конечно, 6
эти цифровые фильтры меня угробят :)

>Юрий Зотов
За очередной хороший совет спасибо. Вот заодно и модуль проверил лишний раз, и теорию при случае почитаю.

ну ты, Кабан, даешь...

> Юрий Зотов © (25.08.05 14:39) [11]

Приведенная грамматика допускает только числа 0-9. Так что - никаких отрицательных чисел.

А польская записть тут, имхо, проще и понятнее, а задачу решает. Т.е. - лучше.

> TUser © (25.08.05 16:50) [27]

> А польская записть тут, имхо, проще и понятнее

Чтобы не спорить впустую, давайте приведем здесь два кода. Вы решите задачу с польской записью, а я - без нее. Вот и увидим, что получится проще и понятнее.

Постановку задачи возьмем из сабжа. Точно в том виде, как она там описана.

Прошу понять меня правильно - это не предложение помериться ведерками, а предложение выяснить, в каких случаях какой подход лучше и/или проще. Я намерен показать, что в таких простых задачах, как строчный калькулятор, можно производить вычисления прямо в ходе парсинга, без предварительного перевода выражения в польскую запись. В таком варианте из калькулятора исключается часть кода - что, видимо, должно его и упростить, и ускорить.

← →
student22 (2005-08-25 18:57) [29]

Недавно написал такую вещь по примеру из этой статьи.
http://rsdn.ru/article/alg/statemachine.xml

2 автор.
Ты в курсе что твой пример не подподает под тобой же приведенную грамматику?? Вот с её описания и нужно начинать. а потом уже о рекурсиях и польских записях думать...

Может, плохо смотрел, но
Kisha © (25.08.05 3:18)
<формула>::=<цифра>|(<формула><знак><формула>)
В примере скобок не вижу, да и на цифру это не очень похоже...
Kisha © (25.08.05 3:18)
((5+3)*2)-1

> jack128 © (26.08.05 00:47) [32]

> В примере скобок не вижу, да и на цифру это не очень похоже...

Жень, ты че? Это же рекурсивное определение. Или я не врубился и ты имел в виду что-то другое?

Давай распишем последовательность состояний конечного автомата. Первая колонка - только что считанный входной символ, вторая - состояние автомата (Ф означает "формула", цифра при ней означает уровень вложенности формулы), третья колонка - формально возможные следующие символы, не нарушающие синтаксиса (eof - символ конца входного потока; формально он возможен после цифры или закрывающей скобки, поскольку, согласно синтаксису, только ими может заканчиваться формула).
( Ф1 цифра, ( ( Ф2 цифра, ( 5 Ф3 знак, ), eof + Ф2 цифра, ( 3 Ф3 знак, ), eof ) Ф2 знак, ), eof * Ф1 цифра, ( 2 Ф2 знак, ), eof ) Ф1 знак, ), eof - Ф0 цифра, ( 1 Ф1 знак, ), eof eof Ф0
Как видишь, в выражении нет ни одного символа, недопустимого в текущем состоянии автомата, поэтому цепочка им не отвергается. Со вложенными подвыражениями тоже все в порядке - в конце цепочки автомат выходит на нулевой уровень вложенности.

jack128 © (26.08.05 00:47) [32]
Женька, вроде номано все. Я сначала подумал, что ты про правую часть выражения говоришь = 15, а потом догадался, что этим автор хотел сказать, что нужно вычислить результат.

Синтаксический анализатор Найти похожие ветки