дерево синтаксического анализа

[ADRenaLIN]

подскажите, плиз...
есть выражения
1. $y=\frac{4*x-x^2}{4}$, $x_0=2$
2. $y=x*arcsin(\frac{1}{x})+ln(x+\sqrt{x^2-1})$, $x>0$
3. $x=7,76$, $y=x^{\frac{1}{3}}$
нужно построить деревья синтаксического анализа...
для первого случая я построила дерево, но без учета $x_0=2$ (не нашла в теории как это делается)
1. опишу, что у меня получилось в первом случае...
(теорию смотрела здесь http://www.intuit.ru/department/pl/plpa ... mage.11.15)
(/|.|.)
(-|.|.) (4|nil|nil)
(*|.|.) (*|.|.)
(4|nil|nil) (x|nil|nil) (x|nil|nil) (x|nil|nil)
не знаю как учесть условие $x_0=2$
2. во втором случае запуталась с условием $x>0$ и с операциями $arcsin(\frac{1}{x})$ и $ln(x+\sqrt{x^2-1})$
получила пока
(+|.|.)
(*|.|.) (?|?|?)
(x|nil|nil) (?|?|?)
подскажите пожалуйста...

[Toucan]

Перемещено в Computer Science

[ADRenaLIN]

Toucan в сообщении #331819 писал(а):

Перемещено в Computer Science

интересно... задание по дискретной математике так-то

[ADRenaLIN]

совсем никто не разбирается в этой теме?

[yk2ru]

ADRenaLIN в сообщении #331918 писал(а):

совсем никто не разбирается в этой теме?

Слишком специфичная тема, нужно общаться наверное там, где собирается народ пишущий такие вещи, компиляторы и т.п.

[Pavia]

Как по мне компиляторы тема сложная. Уже не первый день(год) изучаю, но постоянно, а периодично, наплывами.
Как то она мне не трудно дается.
Теорию почерпни тут.
http://www.intuit.ru/department/sa/comp ... dev_7.html

Используй свертку. А для "," и "=" применяй левую ассоциативность.

y=(4*x-x^2)/4,x0=2

Вначале пройдемся лексическим анализатором получим.
id1=(num1*id2-id2^num2)/num3,id3=num2
заносим в стек
id1=(num1*id2
Существут такая граматика выполняем свертку.
id1=(term

(*,.,.)
(num1,nil,nil)(id1,nil,nil)

id1=(term-id2^num2 выполняем свертку
id1=(term-exp
(*,.,.) (^,.,.)
(num1,nil,nil)(id1,nil,nil) (id2,nil,nil)(num2,nil,nil)
id1=(term-exp снова свертка
id=(expr
(-,.,.)
(*,.,.) (^,.,.)
(num1,nil,nil)(id1,nil,nil) (id2,nil,nil)(num2,nil,nil)
заносим скобку в стек
id=(expr) и выполняем светку
id=factor
('()',nil,.)
('-',.,.)
('*',.,.) ('^',.,.)
(num1,nil,nil)(id1,nil,nil) (id2,nil,nil)(num2,nil,nil)

заносим скобку в стек /
id=factor/num3 снова свертка.
id=term
('/',.,.)
('()',nil,.) (num3,nil,nil)
('-',.,.)
('*',.,.) ('^',.,.)
(num1,nil,nil)(id1,nil,nil) (id2,nil,nil)(num2,nil,nil)

снова сввертка id=term в Stmt.
Stmt
('=',.,.)
('/',.,.)
('()',nil,.) (num3,nil,nil)
('-',.,.)
('*',.,.) ('^',.,.)
(num1,nil,nil)(id1,nil,nil) (id2,nil,nil)(num2,nil,nil)
заносим ',' в стек
Stmt,
сново заносим d в стек.
Stmt,id3
тут надо быть по оккуратние что у нас с громатикой. Если такой нет то заносим дальше.
Stmt,id3=num3 делаем сверку и еще одну свертку
('запятая',.,.)
('=',.,.) ('=',.,.)
('/',.,.)
('()',nil,.) (num3,nil,nil)
('-',.,.)
('*',.,.) ('^',.,.)
(num1,nil,nil)(id1,nil,nil) (id2,nil,nil)(num2,nil,nil)
И там справа не поместилоcь
(id3,nil,nil)
(num2,nil,nil)

Часть операций опущенно, а то и так долго.

[ADRenaLIN]

Pavia в сообщении #332005 писал(а):

('запятая',.,.)
('=',.,.) ('=',.,.)
('/',.,.)
('()',nil,.) (num3,nil,nil)
('-',.,.)
('*',.,.) ('^',.,.)
(num1,nil,nil)(id1,nil,nil) (id2,nil,nil)(num2,nil,nil)
И там справа не поместилоcь
(id3,nil,nil)
(num2,nil,nil)

я поняла, как учесть $x_0=2$
а как правильно записать, например, $y=e^x+\sqrt{1+x}$? или $y=1+ln(2+e^x)$
интересуют операции $e^x$, $\sqrt{1+x}$, $ln(2+e^x)$
просто в теории про эти операции не нашла :(
буду премного благодарна

[creative]

Только собираюсь изучать эту тему (для себя). Точно знаю, что Вашу задачу можно решить используя конечные автоматы:

http://www.rsdn.ru/article/alg/statemachine.xml

Так же посмотрите книжки по конечным автоматам.

Ещё рекомендую книжку "Хопкрофт, Джон, Мотвани, Раджив, Ульман, Джеффри, Д. Введение в теорию автоматов, языков и вычислений = Introduction to Automata Theory, Languages, and Computation". Её можно скачать. Начните со страниц 128 и 197, а далее разберётесь.

[Pavia]

Цитата:

http://www.rsdn.ru/article/alg/statemachine.xml

Только тут походу описан Лексический анализатор, а не Синтаксический. У статьи неправильно название

[creative]

В любом случае в книжке про которую я написал есть ответ.

[ADRenaLIN]

не могу найти данную книгу, у нас даже в библиотеке ее нет

[creative]

ADRenaLIN в сообщении #332068 писал(а):

не могу найти данную книгу, у нас даже в библиотеке ее нет

http://depositfiles.com/ru/files/0qz58qwc8

Легко ищется по названию книги или автору со словом djvu.

Сразу скажу, что с кникой надо разбираться, так сходу не получится. Ещё посмотрите паралельно про автоматное программирование:

http://ru.wikipedia.org/wiki/%D0%90%D0% ... 0%B8%D0%B5

В конце литература есть по Вашему вопросу.

[arseniiv]

ADRenaLIN в сообщении #332007 писал(а):

интересуют операции $e^x$, $\sqrt{1+x}$, $ln(2+e^x)$

Операции $\exp,\,\ln,\,\sqrt\text{ }$ унарные же! Значит, от них отходит одна ветка вниз, а другая nil.
Кстати, а такая запись скобками общепринята? (Я просто не знаю.) Может, удобнее писать как-нибудь так:

(ln (+ 2 (exp x nil)) nil)
ln(+(2 exp(x nil)) nil)

?

Кстати, $x^2$ можно представлять не только как (* x x), но и как (^ x 2).

-- Ср авг 25, 2010 01:04:49 --

Упс, в старую тему залез.