Мастера DELPHI (документация, исходники, скачать)

Основная («Начинающим»)/ Базы / WinAPI / Компоненты / Сети / Media / Игры / Corba и COM / KOL / FreePascal / .Net / Прочее / RSDN.ORG

« предыдущая ветвь | форум | следующая ветвь »

Синтаксический анализатор [D7, WinXP]

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

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

Юрий Зотов (2005-08-26 01:46:00) [2]
> 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 (2005-08-26 00:47:00) [3]
Может, плохо смотрел, но
Kisha © (25.08.05 3:18)
<формула>::=<цифра>| (<формула><знак><формула> )
В примере скобок не вижу, да и на цифру это не очень похоже...
Kisha © (25.08.05 3:18)
((5+3)*2)-1

Юрий Зотов (2005-08-25 21:12:00) [4]
> jack128 © (25.08.05 19:15) [30]

Может, плохо смотрел, но противоречий не увидел.

jack128 (2005-08-25 19:15:00) [5]
2 автор.
Ты в курсе что твой пример не подподает под тобой же приведенную грамматику?? Вот с её описания и нужно начинать. а потом уже о рекурсиях и польских записях думать...

student22 (2005-08-25 18:57:00) [6]
Недавно написал такую вещь по примеру из этой статьи.
http://rsdn.ru/article/alg/statemachine.xml

Юрий Зотов (2005-08-25 18:10:00) [7]
> TUser © (25.08.05 16:50) [27]

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

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

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

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

TUser (2005-08-25 16:50:00) [8]
> Юрий Зотов © (25.08.05 14:39) [11]

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

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

OldNaum (2005-08-25 16:12:00) [9]
ну ты, Кабан, даешь...

TStas (2005-08-25 15:39:00) [10]
>Юрий Зотов
За очередной хороший совет спасибо. Вот заодно и модуль проверил лишний раз, и теорию при случае почитаю.

Кабан (2005-08-25 15:33:00) [11]
6, конечно, 6
эти цифровые фильтры меня угробят :)

TStas (2005-08-25 15:32:00) [12]
>Alexander Panov
Я чего-то сам путаться стал. Так 6 все-таки?:)

Кабан (2005-08-25 15:29:00) [13]
сори, прошу прощения, совсем за работался, уже глюки пошли :)

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

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

Кабан (2005-08-25 15:27:00) [15]
2 TStas
оригинально... я вижу вы не шутите, естественно -6

alex_*** (2005-08-25 15:26:00) [16]
в смысле 6 будет :) это я к [16]

alex_*** (2005-08-25 15:25:00) [17]
а разве нет?

TStas (2005-08-25 15:24:00) [18]
>Кабан
А сколько? Разве -6?

Кабан (2005-08-25 15:14:00) [19]
а разве -2*(-3) = 6? :)

TStas (2005-08-25 14:59:00) [20]
>Юрий Зотов
-2*(-3) = 6 //Скопировано мышкой
Понятно, что он не образец, но пока не нашел в нем глюков

Страницы: 1 2 >

Наверх

	« предыдущая ветвь \| форум \| следующая ветвь »