2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 дерево синтаксического анализа
Сообщение16.06.2010, 08:00 


26/04/10
116
подскажите, плиз...
есть выражения
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) (?|?|?)
подскажите пожалуйста...

 Профиль  
                  
 
 Re: дерево синтаксического анализа
Сообщение16.06.2010, 11:00 
Админ форума
Аватара пользователя


19/03/10
8952
 i  Перемещено в Computer Science

 Профиль  
                  
 
 Re: дерево синтаксического анализа
Сообщение16.06.2010, 12:51 


26/04/10
116
Toucan в сообщении #331819 писал(а):
 i  Перемещено в Computer Science

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

 Профиль  
                  
 
 Re: дерево синтаксического анализа
Сообщение16.06.2010, 15:31 


26/04/10
116
совсем никто не разбирается в этой теме?

 Профиль  
                  
 
 Re: дерево синтаксического анализа
Сообщение16.06.2010, 16:54 


03/10/06
826
ADRenaLIN в сообщении #331918 писал(а):
совсем никто не разбирается в этой теме?

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

 Профиль  
                  
 
 Re: дерево синтаксического анализа
Сообщение16.06.2010, 20:05 
Аватара пользователя


31/10/08
1244
Как по мне компиляторы тема сложная. Уже не первый день(год) изучаю, но постоянно, а периодично, наплывами.
Как то она мне не трудно дается.
Теорию почерпни тут.
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)

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

 Профиль  
                  
 
 Re: дерево синтаксического анализа
Сообщение16.06.2010, 20:25 


26/04/10
116
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$ :D
а как правильно записать, например, $y=e^x+\sqrt{1+x}$? или $y=1+ln(2+e^x)$
интересуют операции $e^x$, $\sqrt{1+x}$, $ln(2+e^x)$
просто в теории про эти операции не нашла :(
буду премного благодарна :roll:

 Профиль  
                  
 
 Re: дерево синтаксического анализа
Сообщение16.06.2010, 20:59 
Аватара пользователя


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

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

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

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

 Профиль  
                  
 
 Re: дерево синтаксического анализа
Сообщение16.06.2010, 21:28 
Аватара пользователя


31/10/08
1244
Цитата:
http://www.rsdn.ru/article/alg/statemachine.xml
Только тут походу описан Лексический анализатор, а не Синтаксический. У статьи неправильно название :-(

 Профиль  
                  
 
 Re: дерево синтаксического анализа
Сообщение16.06.2010, 22:08 
Аватара пользователя


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

 Профиль  
                  
 
 Re: дерево синтаксического анализа
Сообщение17.06.2010, 05:18 


26/04/10
116
не могу найти данную книгу, у нас даже в библиотеке ее нет

 Профиль  
                  
 
 Re: дерево синтаксического анализа
Сообщение17.06.2010, 17:49 
Аватара пользователя


01/04/10
910
ADRenaLIN в сообщении #332068 писал(а):
не могу найти данную книгу, у нас даже в библиотеке ее нет


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

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

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

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

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

 Профиль  
                  
 
 Re: дерево синтаксического анализа
Сообщение24.08.2010, 22:04 
Заслуженный участник


27/04/09
28128
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 --

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 13 ] 

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group