OberonCore
https://forum.oberoncore.ru/

Удаление пр.рекурсии в определении синтаксиса языка.
https://forum.oberoncore.ru/viewtopic.php?f=61&t=1304
Страница 1 из 1

Автор:  Wlad [ Воскресенье, 11 Январь, 2009 11:35 ]
Заголовок сообщения:  Удаление пр.рекурсии в определении синтаксиса языка.

Кто-нить занимался данным вопросом?
Ссылок - море. Кто-нибудь! Дайте удобоваримую ссылку на теоретические работы по преобразованию грамматик с целью выведения из определения языка зацикленных определений... Пусть и с геометрическим ростом количества правил! Мне теорию понять железно надо. Принцип. И иллюстрацию какую простейшую...

ЗЫ ФЯ не предлагать! Я б и сам рад, но строгое ограничение заказчика на использование только Си а асма...

Автор:  Александр Ильин [ Воскресенье, 11 Январь, 2009 11:43 ]
Заголовок сообщения:  Re: Удаление пр.рекурсии в определении синтаксиса языка.

Такое ощущение, что в названии темы сокращению подверглось самое ключевое слово.

Автор:  Wlad [ Воскресенье, 11 Январь, 2009 12:36 ]
Заголовок сообщения:  Re: Удаление пр.рекурсии в определении синтаксиса языка.

Александр Ильин писал(а):
Такое ощущение, что в названии темы сокращению подверглось самое ключевое слово.

Вы правы, дорогой товарищ! Это - фильтр. Кто понимает - поймёт и, при желании, отзовётся. Остальные - ходят мимо...

Автор:  Илья Ермаков [ Воскресенье, 11 Январь, 2009 13:27 ]
Заголовок сообщения:  Re: Удаление пр.рекурсии в определении синтаксиса языка.

В Dragon Book Ахо-Ульмана смотрели?

Из более теоретических работ можно посмотреть Хопкрофт, Мотвани, Ульман "Введение в теорию автоматов, языков и вычислений". (http://natahaus.ifolder.ru/354087) Вот эта ещё книжка есть - Рейуорд, Смит "Теория формальных языков": http://natahaus.ifolder.ru/307174.

Посмотрел у себя несколько работ по теории языков - там вопрос преобразования грамматик обойдён стороной :(

Автор:  Александр Ильин [ Воскресенье, 11 Январь, 2009 14:10 ]
Заголовок сообщения:  Re: Удаление пр.рекурсии в определении синтаксиса языка.

Владимир Лось писал(а):
Вы правы, дорогой товарищ! Это - фильтр. Кто понимает - поймёт и, при желании, отзовётся. Остальные - ходят мимо...
Понятно. Тех, кто просто интересуется синтаксисом и терминологией, посылают... мимо. Как-то не очень вежливо для публичного пространства.

Автор:  Geniepro [ Понедельник, 12 Январь, 2009 10:30 ]
Заголовок сообщения:  Re: Удаление пр.рекурсии в определении синтаксиса языка.

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

Владимир Лось писал(а):
Дайте удобоваримую ссылку на теоретические работы по преобразованию грамматик с целью выведения из определения языка зацикленных определений...
Как-то читал книгу по построению компиляторов, и, как я понял, преобразование грамматик в общем случае опять же невозможно...

Вы бы описали подробнее, какую грамматику используете, что за язык (или семейство языков?)...
Левую рекурсию Вы, я так понял, уже свели к правой, теперь от правой осталось избавиться?

Владимир Лось писал(а):
ЗЫ ФЯ не предлагать! Я б и сам рад, но строгое ограничение заказчика на использование только Си а асма...
А в чём проблема? Прототип по-любому лучше на высокоуровневом языке делать, а если на рефал-0 потом перейдёте, то на си странслируете тулзой Ильи... :lol: Не всё ли равно, на чём будет модель, лишь бы заказчик получил удобоваримый сишный код...

Вообще, даже интересно стало: что за задача, и почему такое жёсткое ограничение -- Си+асм...

Автор:  Wlad [ Понедельник, 12 Январь, 2009 12:19 ]
Заголовок сообщения:  Re: Удаление пр.рекурсии в определении синтаксиса языка.

Geniepro писал(а):
Вообще, даже интересно стало: что за задача, и почему такое жёсткое ограничение -- Си+асм...

"Дураков работа любит - я без дела не останусь..." (с) Мой старшина
Да всё те же ограничения - ну люблю я встроенные (и автономныя) системы... :lol: :wink:
Но всё дело в том, что задания на систему могут отдаваться в виде скриптов. А скрипт-язык не готовый взяли с реализацией, а свой ваяли... Автор-реализатор в середине проекта ушёл, а мне тянуть... А там всё это вручную, "прямым анализом" строк "парсилось"...
Пока задания элементарные были - всё "сглатывалось", а теперь народ привык, понравилось и ужЕ пытается выражения по-сложнее строить... И... - всё, затыки-ссс... Фдрук оказалось, что там не просто сравнение подстрок с образцами нужно... :roll: :D

Автор:  Рэйлвэй Каген [ Понедельник, 12 Январь, 2009 13:11 ]
Заголовок сообщения:  Re: Удаление пр.рекурсии в определении синтаксиса языка.

см.раздел Связь между диаграммами Вирта и праволинейными грамматиками. Преобразование правой рекурсии в итерацию.

Автор:  Илья Ермаков [ Понедельник, 12 Январь, 2009 13:47 ]
Заголовок сообщения:  Re: Удаление пр.рекурсии в определении синтаксиса языка.

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

Автор:  Илья Ермаков [ Понедельник, 12 Январь, 2009 14:02 ]
Заголовок сообщения:  Re: Удаление пр.рекурсии в определении синтаксиса языка.

Владимир, а и правда - посмотрите Рефал-0, может, подойдёт )
Концевая рекурсия у меня разворачивается в обычный цикл, динамической памяти не требуется - по-моему, самое то для микроконтроллеров.

Автор:  Рэйлвэй Каген [ Понедельник, 12 Январь, 2009 18:49 ]
Заголовок сообщения:  Re: Удаление пр.рекурсии в определении синтаксиса языка.

Илья Ермаков писал(а):
..Там речь о устранении рекурсии из регулярного языка
Ага, там приведены примеры реализации для регулярных языков. Интересно, что в конце работы предложен механизм "динамически порождаемых конечных автоматов" - для преодоления семантического разрыва между формальной грамматикой и входным алфавитом автомата. Подход в некоторой степени перекликается с Вашим активным синтаксическим деревом, но безусловно проигрывает по проработанности и не имеет реализации.

Указанный цикл лекций удалось переформатировать в пдфник:
Вложение:


p.s. 0xFF: У того же автора нашлось описание ОО параллельного языка, датированное 1992 годом.. Ну очень "оберонисто" :)

Автор:  Илья Ермаков [ Понедельник, 12 Январь, 2009 20:11 ]
Заголовок сообщения:  Re: Удаление пр.рекурсии в определении синтаксиса языка.

Да, проф. Легалов (Красноярск) занимался Модулой и Оберонами, хотя и относится к ним в итоге весьма сдержанно, если не ошибаюсь. В параллельном программировании он имеет серьёзные наработки.

За форматированный вариант спасибо ) Материал интересный.

Автор:  Axcel [ Понедельник, 12 Январь, 2009 23:09 ]
Заголовок сообщения:  Re: Удаление пр.рекурсии в определении синтаксиса языка.

Рефал 0 классная штука, настоятельно рекомендую. Кстати Илья, СПАСИБО.

Автор:  Wlad [ Понедельник, 12 Январь, 2009 23:12 ]
Заголовок сообщения:  Re: Удаление пр.рекурсии в определении синтаксиса языка.

Илья Ермаков писал(а):
Владимир, а и правда - посмотрите Рефал-0, может, подойдёт )
Концевая рекурсия у меня разворачивается в обычный цикл, динамической памяти не требуется - по-моему, самое то для микроконтроллеров.

Спасибо!
Теперь ещё ссылочкой киньтесь для полной сатисфакции и будет всем нам щастя! :)

Автор:  Илья Ермаков [ Понедельник, 12 Январь, 2009 23:14 ]
Заголовок сообщения:  Re: Удаление пр.рекурсии в определении синтаксиса языка.

Axcel, рад слышать добрые отзывы :)

Владимир,
вот подсистема для ББ:
http://metasystems.ru/products.php?page=rocot
а вот консольный транслятор:
http://metasystems.ru/products.php?page=refal0

Начать в любом случае нужно с чтения PDF-документа - там вверху ссылка на обоих страницах.

Автор:  Wlad [ Понедельник, 12 Январь, 2009 23:32 ]
Заголовок сообщения:  Re: Удаление пр.рекурсии в определении синтаксиса языка.

ПБ!

Автор:  igor [ Вторник, 13 Январь, 2009 10:31 ]
Заголовок сообщения:  Re: Удаление пр.рекурсии в определении синтаксиса языка.

Рэйлвэй Каген писал(а):
Вложение:
_ Легалов А.И. Основы разработки трансляторов.pdf
Прикольное заявление автора на странице 61:
Цитата:
я не считаю языками программирования те из них, в которых отсутствует GOTO.

Автор:  Сергей Оборотов [ Среда, 14 Январь, 2009 18:22 ]
Заголовок сообщения:  Re: Удаление пр.рекурсии в определении синтаксиса языка.

Игорь Лоскутов писал(а):
Прикольное заявление автора на странице 61:
Как курьёз:
А.Л. писал(а):
Следует специально отметить, что, начиная с q-грамматики, далее постоянно приходиться доказывать принадлежность грамматики к заданному классу, чтобы затем использовать необходимые процедуры построения автомата.
Программа проверки правописания бессильна, покольку не может поставить правильное ударение.

Страница 1 из 1 Часовой пояс: UTC + 3 часа
Powered by phpBB® Forum Software © phpBB Group
https://www.phpbb.com/