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 потом перейдёте, то на си странслируете тулзой Ильи... Не всё ли равно, на чём будет модель, лишь бы заказчик получил удобоваримый сишный код... Вообще, даже интересно стало: что за задача, и почему такое жёсткое ограничение -- Си+асм... |
Автор: | Wlad [ Понедельник, 12 Январь, 2009 12:19 ] |
Заголовок сообщения: | Re: Удаление пр.рекурсии в определении синтаксиса языка. |
Geniepro писал(а): Вообще, даже интересно стало: что за задача, и почему такое жёсткое ограничение -- Си+асм... "Дураков работа любит - я без дела не останусь..." (с) Мой старшина Да всё те же ограничения - ну люблю я встроенные (и автономныя) системы... Но всё дело в том, что задания на систему могут отдаваться в виде скриптов. А скрипт-язык не готовый взяли с реализацией, а свой ваяли... Автор-реализатор в середине проекта ушёл, а мне тянуть... А там всё это вручную, "прямым анализом" строк "парсилось"... Пока задания элементарные были - всё "сглатывалось", а теперь народ привык, понравилось и ужЕ пытается выражения по-сложнее строить... И... - всё, затыки-ссс... Фдрук оказалось, что там не просто сравнение подстрок с образцами нужно... |
Автор: | Рэйлвэй Каген [ Понедельник, 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 Цитата: я не считаю языками программирования те из них, в которых отсутствует GOTO.
|
Автор: | Сергей Оборотов [ Среда, 14 Январь, 2009 18:22 ] |
Заголовок сообщения: | Re: Удаление пр.рекурсии в определении синтаксиса языка. |
Игорь Лоскутов писал(а): Прикольное заявление автора на странице 61: Как курьёз:А.Л. писал(а): Следует специально отметить, что, начиная с q-грамматики, далее постоянно приходиться доказывать принадлежность грамматики к заданному классу, чтобы затем использовать необходимые процедуры построения автомата. Программа проверки правописания бессильна, покольку не может поставить правильное ударение.
|
Страница 1 из 1 | Часовой пояс: UTC + 3 часа |
Powered by phpBB® Forum Software © phpBB Group https://www.phpbb.com/ |