Задача по ссылке от Munin

[_Ivana]

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

[_Ivana]

Ну вот и я наконец додумался как красиво реализовать этот алгоритм. Идея оказалась очень проста, зря я возился с рекурсией. Код ниже реализует только суть, без отработки ошибок и длинных имен переменных (это несложно добавить, но я хотел показать саму идею алгоритма). Выбрал синтаксис ASM, т.к. синтаксиса 1С тут конечно нет, хотя присутствуют различные экзотические языки

Используется синтаксис 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);
КонецФункции
 

[Xaositect]

Ага, классический стековый автомат.

[_Ivana]

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

[Xaositect]

_Ivana в сообщении #687170 писал(а):

Скажите на словах - у вас там такой же алгоритм по сути или нет?

Нет, там как как раз то, что Вы пытались реализовывать раньше - строка делится по операторам +,- потом каждая подстрока по операторам *,/, потом каждая подстрока должна быть либо буквой, либо скобкой. Автомат я хотел написать, но это скучнее :)
В моей программе мне не очень нравится конструкция

(reverse *** reverse) $ (map subparser *** map fst) $ splitOn ((flip elem operators) *** (==level) >>> uncurry (&&))

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

[_Ivana]

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

[Munin]

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

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

[_Ivana]

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

[Munin]

_Ivana в сообщении #687263 писал(а):

ЗЫ Кстати, предлагая эту задачку в соседней теме, вы заранее не интересовались, читал ли адресат предложения эту теорию

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

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

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

[_Ivana]

Munin в сообщении #687267 писал(а):

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

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

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

[Pavia]

Цитата:

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

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

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

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

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

[Munin]

_Ivana в сообщении #687269 писал(а):

Вы можете предложить какую-нибудь хорошую книгу

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

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

Нет книжки в которой это всё собрано воедино.

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

[arseniiv]

Munin в сообщении #687295 писал(а):

Ахо-Ульман

Забыли третьего — Сети. После неё надо будет всё равно ещё читать про то новое, что появилось после — действительно, столько разностей в одну книгу не затолкнуть.

(Оффтоп)

_Ivana в сообщении #687165 писал(а):

Выбрал синтаксис ASM, т.к. синтаксиса 1С тут конечно нет, хотя присутствуют различные экзотические языки

Можно использовать [syntax] и без параметров.

[rockclimber]

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

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

[_Ivana]

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