2014 dxdy logo

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

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




 
 дерево синтаксического анализа
Сообщение16.06.2010, 08:00 
подскажите, плиз...
есть выражения
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 
Аватара пользователя
 i  Перемещено в Computer Science

 
 
 
 Re: дерево синтаксического анализа
Сообщение16.06.2010, 12:51 
Toucan в сообщении #331819 писал(а):
 i  Перемещено в Computer Science

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

 
 
 
 Re: дерево синтаксического анализа
Сообщение16.06.2010, 15:31 
совсем никто не разбирается в этой теме?

 
 
 
 Re: дерево синтаксического анализа
Сообщение16.06.2010, 16:54 
ADRenaLIN в сообщении #331918 писал(а):
совсем никто не разбирается в этой теме?

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

 
 
 
 Re: дерево синтаксического анализа
Сообщение16.06.2010, 20:05 
Аватара пользователя
Как по мне компиляторы тема сложная. Уже не первый день(год) изучаю, но постоянно, а периодично, наплывами.
Как то она мне не трудно дается.
Теорию почерпни тут.
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 
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 
Аватара пользователя
Только собираюсь изучать эту тему (для себя). Точно знаю, что Вашу задачу можно решить используя конечные автоматы:

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

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

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

 
 
 
 Re: дерево синтаксического анализа
Сообщение16.06.2010, 21:28 
Аватара пользователя
Цитата:
http://www.rsdn.ru/article/alg/statemachine.xml
Только тут походу описан Лексический анализатор, а не Синтаксический. У статьи неправильно название :-(

 
 
 
 Re: дерево синтаксического анализа
Сообщение16.06.2010, 22:08 
Аватара пользователя
В любом случае в книжке про которую я написал есть ответ.

 
 
 
 Re: дерево синтаксического анализа
Сообщение17.06.2010, 05:18 
не могу найти данную книгу, у нас даже в библиотеке ее нет

 
 
 
 Re: дерево синтаксического анализа
Сообщение17.06.2010, 17:49 
Аватара пользователя
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 
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 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group