OberonCore

Библиотека  Wiki  Форум  BlackBox  Компоненты  Проекты
Текущее время: Вторник, 19 Март, 2024 14:10

Часовой пояс: UTC + 3 часа




Начать новую тему Ответить на тему  [ Сообщений: 62 ]  На страницу Пред.  1, 2, 3, 4  След.
Автор Сообщение
СообщениеДобавлено: Среда, 20 Январь, 2010 12:46 

Зарегистрирован: Среда, 30 Сентябрь, 2009 14:45
Сообщения: 147
Сергей Губанов писал(а):
Вчера вечером на работе наткнулся на следующий код:

Этот анекдотический пример навевает всякие педологические эманации.

1. Здесь смешаны 2 метода: "дешевый" и "эффективный":
а) "дешевый" в смысле усилий - использовать регулярное выражение, задача решается в 1 строчку;
б) "эффективный" в смысле экономии тактов/байтов - написать выборку подстроки самостоятельно.

2. Хочется представить, как это было. А было так: студент спросил, как выбрать из строки нужную подстроку. Получил ответ: представь строку как последовательность символов и проверь каждый. Тогда он спросил у другого человека, как определить, что в строке число? Ему ответили: используй регулярное выражение, а число есть "^[0-9]+$". И ему было невдомек, что даже в регулярном выражении он сделал 3 учебных ошибки.

3. К вопросу о необходимости изучения низкоуровневых средств - студента явно не научили пользоваться таковыми.
А вот, если бы его сначала, до использования строковых функций научили манипулировать байтовыми последовательностями, потом показали строковые функции, потом регулярные выражения... Или наоборот, научили работать с регулярными выражениями, только с ними, но как следует.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Пятница, 12 Февраль, 2010 10:19 
Модератор
Аватара пользователя

Зарегистрирован: Среда, 16 Ноябрь, 2005 00:53
Сообщения: 4625
Откуда: Россия, Орёл
Итого, три автоматичка ошиблись, двое не заметили...

viewtopic.php?p=40339#p40339
viewtopic.php?p=42381#p42381
viewtopic.php?p=42473#p42473

Нет ли тут морали об излишней сложности метода решения?

Плюс очередной пример errare humanum est к обоснованию чуйства "в таком месте код трогать без большой реальной нужды как-то ... стрёмно"


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Пятница, 12 Февраль, 2010 14:09 

Зарегистрирован: Пятница, 24 Апрель, 2009 16:28
Сообщения: 563
Откуда: Москва
Ну так решения с помощью автоматов крайне не наглядны в коде. Плюс обычные методы верификации программ здесь не работают. А модифицировать код практически невозможно, только создавать заново.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Пятница, 12 Февраль, 2010 14:31 

Зарегистрирован: Суббота, 07 Март, 2009 15:39
Сообщения: 3261
Откуда: Астрахань
Peter Almazov писал(а):
Ну так решения с помощью автоматов крайне не наглядны в коде. Плюс обычные методы верификации программ здесь не работают. А модифицировать код практически невозможно, только создавать заново.

Еще как возможно... :)
Вот вам текст из моей книжки. Там реализация конечного автомата в трех видах представлена.
Один из видов реализации - прекрасно изменяется без переделки уже созданного. :)
Программы на С++, но вы, надеюсь, разберетесь.


Вложения:
Кое-что о конечных автоматах.rar [35.84 КБ]
Скачиваний: 459
Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Пятница, 12 Февраль, 2010 14:48 

Зарегистрирован: Пятница, 24 Апрель, 2009 16:28
Сообщения: 563
Откуда: Москва
Сразу же наткнулся на отсутствие рисунков. Специально?


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Пятница, 12 Февраль, 2010 15:23 

Зарегистрирован: Вторник, 11 Август, 2009 11:44
Сообщения: 516
Откуда: Бердск
1) Ну не ошибается тот, кто ничего не делает.
Тут, на мой взгляд, история совершенно аналогичная языкам программирования. Наиболее прозрачное (это Вирт такое слово употреблял) отражение в коды дает ассемблер. Но мы пытамся изложить свои мысли на ЯВУ.
Можем потом руками перевести это в АСМ. А можем написать программу, по имени компилятор - чтобы он не ошибался. Типа, если тебе компьютер имя, имя крепи делами своими.
Тут же ровно то же самое. В ЭТОЙ постановке задачи невозможно ошибиться:
Вложение:
Comment1.png
Comment1.png [ 11.59 КБ | Просмотров: 14284 ]

Далее - можно ручками. И даже можно (если есть привычка, и каждодневная тренировка) без ошибок. А можно и "инструмент" сварганить - чтобы НИКОГДА не ошибался.
Отмечу еще одно: рисуя патерн входа в Comment, я совершенно не заморачивался, а есть ли выше патерны, начинающиеся с левой скобки. Есть наверное, но их объединение - это "преждевременная оптимизация". Ничего не напоминает ??? :)

2) Стартовый код от Вирта мне не показался очень прозрачным. :)
Всю башку себе сломал, пока пробился через него. Знаю ведь, что там нет ошибок, а внутренней уверенности все равно нет.

3) Валерий, а чего за книжка :?:


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Пятница, 12 Февраль, 2010 15:45 

Зарегистрирован: Пятница, 24 Апрель, 2009 16:28
Сообщения: 563
Откуда: Москва
Здесь корень проблемы в том, что не отделена лексика от синтаксического анализатора. Все в куче. Если их разделить, то все получается очень просто, и главное, надежно. Парсер должен разобрать вот это:
com = cbeg {char|com} cend.
Сканер получается относительно большим по объему viewtopic.php?p=40336#p40336 , но код там очень простой, только занудный.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Пятница, 12 Февраль, 2010 17:02 

Зарегистрирован: Суббота, 07 Март, 2009 15:39
Сообщения: 3261
Откуда: Астрахань
Galkov писал(а):
3) Валерий, а чего за книжка :?:

Да я тут по системному ПО писал для своего 3 курса. Там джентльментский набор: виртуальная машина и ее интерпретатор, ассемблер и транслятор (для нее же), загрузчик и виды загружаемого модуля. Линкер и объектные модули, библиотекарь, мейкер, отладчик, профайлер.
Но чего-то книжка пишется уже долго, и я ее отложил.
А по конечным автоматам в связи с трансляцией числовых констант в ассемблере уже давно написал - вот там в файле и изложено.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Вторник, 06 Апрель, 2010 11:06 

Зарегистрирован: Пятница, 13 Март, 2009 16:36
Сообщения: 987
Откуда: Казань
У меня несколько отличный, чем в начале топика, вопрос, но также про книжку построение компиляторов и также про листинг приведенного там сканера Oberon-0.
Там есть такие строки:
Код:
PROCEDURE Get*(VAR sym: INTEGER);
...
BEGIN
  WHILE ~R.eot & (ch <= " ") DO Texts.Read(R, ch) END;
  IF R.eot THEN sym := eof
  ELSE
    CASE ch OF
    ...
    | ".": Texts.Read(R, ch); sym := period
    ...
    END;
  END;
END Get;

Если последний символ в сканируемом файле - точка (например, "END MyModule."), то после прочтения этого символа R.eot станет TRUE и процедура Get вернет eof, а не period.

У меня есть два предположения:
1) подразумевается, что после точки должен быть еще как минимум 1 символ.
2) я что-то не так понимаю.

Update:
Пример, который я привел, не очень удачный, так как если сканер прочитает MyModule, то он прочитает и точку и при следующем заходе в Get, цикл WHILE выполняться не будет.
Вот более удачный пример "END MyModule ." (между MyModule и точкой есть пробел)


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Вторник, 06 Апрель, 2010 11:20 
Модератор
Аватара пользователя

Зарегистрирован: Среда, 16 Ноябрь, 2005 00:53
Сообщения: 4625
Откуда: Россия, Орёл
Refat писал(а):
то после прочтения этого символа R.eot станет TRUE
R.eot станет TRUE после чтения, когда ридер уже в конце текста
Цитата:
TYPE Reader
ABSTRACT
A rider to read characters and embedded views from a text.

eot: BOOLEAN
Last read was tried at the end of the text.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Вторник, 06 Апрель, 2010 11:27 

Зарегистрирован: Пятница, 13 Март, 2009 16:36
Сообщения: 987
Откуда: Казань
Да, согласен, вопрос в другом.
Текущее состояние: ch = " "
WHILE ~R.eot & (ch <= " ") DO Texts.Read(R, ch) END;
IF R.eot THEN sym := eof
Условие ~R.eot & (ch <= " ") = TRUE следовательно выполняется Texts.Read(R, ch),
теперь ch = "." и R.eot = TRUE, условие ~R.eot & (ch <= " ") = FALSE, цикл завершается.
Следующее условие IF R.eot THEN sym := eof срабатывает и функция возвращает eof, хотя должна period, так как ch="."


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Вторник, 06 Апрель, 2010 11:32 

Зарегистрирован: Суббота, 26 Ноябрь, 2005 10:37
Сообщения: 875
Откуда: Россия, Владивосток
Rifat писал(а):
Условие ~R.eot & (ch <= " ") = TRUE следовательно выполняется Texts.Read(R, ch),
теперь ch = "." и R.eot = TRUE, условие ~R.eot & (ch <= " ") = FALSE, цикл завершается.

Нет. Теперь ch = "." и R.eot = FALSE. TRUE он станет в следующий раз, когда мы попытаемся прочитать за концом текста.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Вторник, 06 Апрель, 2010 11:37 

Зарегистрирован: Пятница, 13 Март, 2009 16:36
Сообщения: 987
Откуда: Казань
Спасибо, теперь понятно.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Вторник, 06 Апрель, 2010 11:46 

Зарегистрирован: Пятница, 13 Март, 2009 16:36
Сообщения: 987
Откуда: Казань
Может кто-нибудь знает, каким будет инвариант цикла для?
WHILE ~R.eot & (ch <= " ") DO Texts.Read(R, ch) END;


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Вторник, 06 Апрель, 2010 12:24 

Зарегистрирован: Понедельник, 30 Июль, 2007 10:53
Сообщения: 1538
Откуда: Беларусь, Минск
Предусловие: имеется текст, и все символы до текущего прочитаны.
Инвариант: все символы до текущего прочитаны.
Постусловие: текст закончился или встретился непробельный символ.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Вторник, 06 Апрель, 2010 12:31 

Зарегистрирован: Пятница, 24 Апрель, 2009 16:28
Сообщения: 563
Откуда: Москва
Постусловие правильное, остальное неверно.
Хотя, нет, и постусловие неправильное.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Вторник, 06 Апрель, 2010 14:26 

Зарегистрирован: Пятница, 13 Март, 2009 16:36
Сообщения: 987
Откуда: Казань
Первое, хотелось бы, что бы кто-нибудь все-таки написал инвариант цикла.

Второе, понимаю, что первое апреля уже прошло, но все же, небольшая шуточка (в которой есть доля правды).
Сканер Oberon-0 распознает комментарии следующим образом:
Код:
| "(": Texts.Read(R, ch);
  IF ch = "*" THEN comment; Get(sym) ELSE sym := lparen END

Здесь использована рекурсия. У меня возникла мысль если сканеры BlackBox 1.6 и сканер Oberon-0 похожи, то нельзя ли уронить компилятор в BlackBox-е.
Я написал небольшой тестовый примерчик: рекурсию, которая никогда не заканчивается, и которая время от времени печатает какой уровень вложенности достигнут. Определил, что примерно после 173000-й вложенности возникает stack overflow.
Затем написал такой примерчик:
MODULE TestTest;
(**)(**)...(**) - 200000 раз
END TestTest.
При попытке компилировать возникает stack overflow. (Конец шутки)

Кто может предложить способ обработки комментариев, которые не будет использовать рекурсию или стек, и который соответственно нельзя будет уронить описанным мной способом?


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Вторник, 06 Апрель, 2010 14:31 
Модератор
Аватара пользователя

Зарегистрирован: Среда, 16 Ноябрь, 2005 00:53
Сообщения: 4625
Откуда: Россия, Орёл
Rifat писал(а):
Кто может предложить способ обработки комментариев, которые не будет использовать рекурсию или стек, и который соответственно нельзя будет уронить описанным мной способом?
Кх кх.. а Вы тему сначала-то читали?

Там и этот viewtopic.php?p=45625#p45625 вопрос уже поднимался, и тот что Вы теперь подняли.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Вторник, 06 Апрель, 2010 14:43 

Зарегистрирован: Пятница, 13 Март, 2009 16:36
Сообщения: 987
Откуда: Казань
Тему я читал давно, сейчас еще раз перечитал, про то, что про eot там обсуждалось, сейчас нашел. Извиняюсь, что задал вопрос еще раз.
А про то, что комменты рекурсивно обрабатываются и возможно переполнение стека, я к сожалению, не нашел, возможно проглядел.
Вообще в теме по большей части обсуждается как можно красивее написать внутренности процедуры comment и как лучше сделать обработку вложенных комментариев.
У меня же не вложенные комментарии, а подряд идущие, друг за другом, внутренности процедуры comment в данном случае меня не интересует. А интересует конструкция:
comment;
Get(sym);


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Вторник, 06 Апрель, 2010 21:57 

Зарегистрирован: Понедельник, 30 Июль, 2007 10:53
Сообщения: 1538
Откуда: Беларусь, Минск
Peter Almazov писал(а):
Постусловие правильное, остальное неверно.
Хотя, нет, и постусловие неправильное.

Ваш вариант


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

Часовой пояс: UTC + 3 часа


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

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


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

Найти:
cron
Вся информация, размещаемая участниками на конференции (тексты сообщений, вложения и пр.) © 2005-2024, участники конференции «OberonCore», если специально не оговорено иное.
Администрация не несет ответственности за мнения, стиль и достоверность высказываний участников, равно как и за безопасность материалов, предоставляемых участниками во вложениях.
Без разрешения участников и ссылки на конференцию «OberonCore» любое воспроизведение и/или копирование высказываний полностью и/или по частям запрещено.
Powered by phpBB® Forum Software © phpBB Group
Русская поддержка phpBB