2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3, 4, 5, 6  След.
 
 Re: Задача по ссылке от Munin
Сообщение23.02.2013, 00:40 


05/09/12
2587
Буквально сейчас мне в голову пришла одна идея, хочу ее проверить (все на той же 1С :-) ). Если получится, то алгоритм будет очень простой и лаконичный...

 Профиль  
                  
 
 Re: Задача по ссылке от Munin
Сообщение23.02.2013, 02:22 


05/09/12
2587
Ну вот и я наконец додумался как красиво реализовать этот алгоритм. Идея оказалась очень проста, зря я возился с рекурсией. Код ниже реализует только суть, без отработки ошибок и длинных имен переменных (это несложно добавить, но я хотел показать саму идею алгоритма). Выбрал синтаксис ASM, т.к. синтаксиса 1С тут конечно нет, хотя присутствуют различные экзотические языки :D
код: [ скачать ] [ спрятать ]
Используется синтаксис ASM
Функция ДатьРезультат(Знач ПереданаСтрока)
       
        СП = СоздатьОбъект("СписокЗначений");
        Уровень = 0;
        МаксУровень = Уровень;
        Для й = 1 По СтрДлина(ПереданаСтрока) Цикл
                ТекСимвол = Сред(ПереданаСтрока, й, 1);
               
                Если ТекСимвол = " " Тогда Продолжить
                ИначеЕсли ТекСимвол = "(" Тогда Уровень = Уровень + 1
                ИначеЕсли ТекСимвол = ")" Тогда Уровень = Уровень - 1
                ИначеЕсли (ТекСимвол = "+") или (ТекСимвол = "-") Тогда
                        СП.ДобавитьЗначение(ТекСимвол, "" + Уровень + "/" + 2);
                ИначеЕсли (ТекСимвол = "*") или (ТекСимвол = "/") Тогда
                        СП.ДобавитьЗначение(ТекСимвол, "" + Уровень + "/" + 1);
                Иначе
                        СП.ДобавитьЗначение(ТекСимвол);
                КонецЕсли;
                МаксУровень = Макс(Уровень, МаксУровень);
        КонецЦикла;
       
        Для сч_Уровень = 0 по МаксУровень Цикл
                Уровень = МаксУровень - сч_Уровень;
                Для ПриоритетОперации = 1 по 2 Цикл
                        Пока 1 = 1 Цикл
                                ПозОперации = 0;
                                Для сч_СП = 1 по СП.РазмерСписка() Цикл
                                        Представление = "";
                                        СП.ПолучитьЗначение(сч_СП, Представление);
                                        Если Представление = "" + Уровень + "/" + ПриоритетОперации Тогда
                                                ПозОперации = сч_СП;
                                                Прервать;
                                        КонецЕсли;
                                КонецЦикла;
                                Если ПозОперации = 0 Тогда Прервать КонецЕсли;
                               
                                Операция = СП.ПолучитьЗначение(ПозОперации);
                                Результат = "(" + СП.ПолучитьЗначение(ПозОперации - 1)                      + "," + СП.ПолучитьЗначение(ПозОперации + 1) + ")";
                                Если        Операция = "+" Тогда Результат = Врег(" ADD") + Результат;
                                ИначеЕсли      Операция = "-" Тогда Результат = Врег(" SUB") + Результат;
                                ИначеЕсли      Операция = "*" Тогда Результат = Врег(" MUL") + Результат;
                                ИначеЕсли      Операция = "/" Тогда Результат = Врег(" DIV") + Результат;
                                КонецЕсли;
                                СП.УстановитьЗначение(ПозОперации, Результат);
                                СП.УдалитьЗначение(ПозОперации + 1);
                                СП.УдалитьЗначение(ПозОперации - 1);
                        КонецЦикла; // по порядку операций данного уровня и приоритета
                КонецЦикла; // по приоритетам операций данного уровня
        КонецЦикла; // по уровням операций
       
        Возврат СП.ПолучитьЗначение(1);
КонецФункции
 

 Профиль  
                  
 
 Re: Задача по ссылке от Munin
Сообщение23.02.2013, 02:37 
Заслуженный участник
Аватара пользователя


06/10/08
6422
Ага, классический стековый автомат.

 Профиль  
                  
 
 Re: Задача по ссылке от Munin
Сообщение23.02.2013, 02:43 


05/09/12
2587
Xaositect, я впечатлен как вы сходу вникаете в мои процедуры на не близком вам языке и понимаете не только их логику и суть, а и тонкие места и возможные дыры. Я в вашем примере на Хаскелле за пару секунд не понял ничего абсолютно :-) Скажите на словах - у вас там такой же алгоритм по сути или нет?

 Профиль  
                  
 
 Re: Задача по ссылке от Munin
Сообщение23.02.2013, 02:59 
Заслуженный участник
Аватара пользователя


06/10/08
6422
_Ivana в сообщении #687170 писал(а):
Скажите на словах - у вас там такой же алгоритм по сути или нет?
Нет, там как как раз то, что Вы пытались реализовывать раньше - строка делится по операторам +,- потом каждая подстрока по операторам *,/, потом каждая подстрока должна быть либо буквой, либо скобкой. Автомат я хотел написать, но это скучнее :)
В моей программе мне не очень нравится конструкция
Код:
(reverse *** reverse) $ (map subparser *** map fst) $ splitOn ((flip elem operators) *** (==level) >>> uncurry (&&))
но это первое, что собралось в голове, и разделять ее на отдельные смысловые куски мне стало лень.

 Профиль  
                  
 
 Re: Задача по ссылке от Munin
Сообщение23.02.2013, 03:13 


05/09/12
2587
Спасибо вам. За активное участие в теме и указание на ошибки. Написав 2 работающих алгоритма, я могу немного расслабиться и считать эту задачу в первом приближении решенной :-)

 Профиль  
                  
 
 Re: Задача по ссылке от Munin
Сообщение23.02.2013, 11:23 
Заслуженный участник
Аватара пользователя


30/01/06
72407
Бывает два вида людей, берущихся разбирать алгебраические выражения: те, которые читали теорию синтаксического анализа, и те, которые не читали.

_Ivana
Скажите честно, вы из какой категории? Xaositect, явно, - уже после.

 Профиль  
                  
 
 Re: Задача по ссылке от Munin
Сообщение23.02.2013, 12:51 


05/09/12
2587
Munin, честно отвечаю на вопрос ЗУ говорю честно - я не читал теорию синтаксического анализа. Просто задачка показалась мне интересной, попробовал решить. Как и математические задачи из олимпиадных, просто праздный энтузиазм :-)
ЗЫ Кстати, предлагая эту задачку в соседней теме, вы заранее не интересовались, читал ли адресат предложения эту теорию :-)
ЗЗЫ конечно, вместо этого я мог бы присоединиться к холивару на тему "межвидовые различия кодеров и программистов", но это мне было бы менее интересно. Еще раз спасибо Xaositect что весьма содержательно поддержал эту тему наш диалог :-)

 Профиль  
                  
 
 Re: Задача по ссылке от Munin
Сообщение23.02.2013, 13:09 
Заслуженный участник
Аватара пользователя


30/01/06
72407
_Ivana в сообщении #687263 писал(а):
ЗЫ Кстати, предлагая эту задачку в соседней теме, вы заранее не интересовались, читал ли адресат предложения эту теорию

Ну, я её не предлагал, собственно, я указал на неё как на стандартную для олимпиад. И олимпиадники обычно эту теорию читали, а опытные могут писать синтаксические анализаторы с листа с закрытыми глазами.

Просто почитайте, это будет вам интересно.

И ещё один признак различий между теми и другими: первые обычно сразу садятся писать рекурсивные функции. Вторые садятся писать грамматику.

 Профиль  
                  
 
 Re: Задача по ссылке от Munin
Сообщение23.02.2013, 13:19 


05/09/12
2587
Munin в сообщении #687267 писал(а):
Просто почитайте, это будет вам интересно.
Скорее всего действительно будет интересно, особенно если материал будет способствующий. Вы можете предложить какую-нибудь хорошую книгу или ссылку или считаете что мне стоит поискать самостоятельно и читать первое попавшееся?

UPD нашел и скачал двухтомник Ахо и Ульмана и Автоматический синтаксический анализ Дж. Фостер.

 Профиль  
                  
 
 Re: Задача по ссылке от Munin
Сообщение23.02.2013, 13:58 
Аватара пользователя


31/10/08
1244
Цитата:
Скорее всего действительно будет интересно, особенно если материал будет способствующий. Вы можете предложить какую-нибудь хорошую книгу или ссылку или считаете что мне стоит поискать самостоятельно и читать первое попавшееся?

Создание компилятора это прикладная задача. Она собирает в себя несколько дисциплин.

1. Планирование архитектуры.
2. Теория формальных языков.
3. Теория структур данных.
4. Теория графов.
5. Теория автоматов.
и множество других.

Нет книжки в которой это всё собрано воедино. Есть книга дракона. Но честно она написана обо всём и ни о чём разом. Тут больше подходит wikipedia английская, так как там собрано достаточно много знаний.

PS. Для создания компилятора требуется небольшое число знаний.

 Профиль  
                  
 
 Re: Задача по ссылке от Munin
Сообщение23.02.2013, 15:27 
Заслуженный участник
Аватара пользователя


30/01/06
72407
_Ivana в сообщении #687269 писал(а):
Вы можете предложить какую-нибудь хорошую книгу

Ну, тут есть классические рекомендации, но я не буду пытаться конкурировать с профессионалами раздела "Программирование" :-) Ахо-Ульман - одна из них, помнится.

Pavia в сообщении #687274 писал(а):
Нет книжки в которой это всё собрано воедино.

Да, пожалуй, это целая библиотека книг. Но некоторые достаточно глубоко освещают разом такие вопросы, как front-end, back-end и семантику языка.

 Профиль  
                  
 
 Re: Задача по ссылке от Munin
Сообщение23.02.2013, 19:08 
Заслуженный участник


27/04/09
28128
Munin в сообщении #687295 писал(а):
Ахо-Ульман
Забыли третьего — Сети. :wink: После неё надо будет всё равно ещё читать про то новое, что появилось после — действительно, столько разностей в одну книгу не затолкнуть.

(Оффтоп)

_Ivana в сообщении #687165 писал(а):
Выбрал синтаксис ASM, т.к. синтаксиса 1С тут конечно нет, хотя присутствуют различные экзотические языки :D
Можно использовать [syntax] и без параметров. :-)

 Профиль  
                  
 
 Re: Задача по ссылке от Munin
Сообщение24.02.2013, 22:35 
Заслуженный участник


06/07/11
5627
кран.набрать.грамота
Вы меня прямо заразили, я сел и тоже написал решение этой задачи.
Заодно прикрутил ей пошаговый отладчик с визуализацией дерева операций.
Писал наспех, то есть кое-как.
Исходники проекта для Lazarus можно скачать тут.

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

 Профиль  
                  
 
 Re: Задача по ссылке от Munin
Сообщение24.02.2013, 22:41 


05/09/12
2587
Я сам сейчас пишу реализацию своего последнего алгоритма на С, может так больше народу заинтересуется и покритикует, сравнит )

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 89 ]  На страницу Пред.  1, 2, 3, 4, 5, 6  След.

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



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

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


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

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