OberonCore https://forum.oberoncore.ru/ |
|
Этюд из книги "Построение компиляторов" https://forum.oberoncore.ru/viewtopic.php?f=82&t=2233 |
Страница 3 из 4 |
Автор: | Виктор О [ Среда, 20 Январь, 2010 12:46 ] |
Заголовок сообщения: | Re: Этюд из книги "Построение компиляторов" |
Сергей Губанов писал(а): Вчера вечером на работе наткнулся на следующий код: Этот анекдотический пример навевает всякие педологические эманации. 1. Здесь смешаны 2 метода: "дешевый" и "эффективный": а) "дешевый" в смысле усилий - использовать регулярное выражение, задача решается в 1 строчку; б) "эффективный" в смысле экономии тактов/байтов - написать выборку подстроки самостоятельно. 2. Хочется представить, как это было. А было так: студент спросил, как выбрать из строки нужную подстроку. Получил ответ: представь строку как последовательность символов и проверь каждый. Тогда он спросил у другого человека, как определить, что в строке число? Ему ответили: используй регулярное выражение, а число есть "^[0-9]+$". И ему было невдомек, что даже в регулярном выражении он сделал 3 учебных ошибки. 3. К вопросу о необходимости изучения низкоуровневых средств - студента явно не научили пользоваться таковыми. А вот, если бы его сначала, до использования строковых функций научили манипулировать байтовыми последовательностями, потом показали строковые функции, потом регулярные выражения... Или наоборот, научили работать с регулярными выражениями, только с ними, но как следует. |
Автор: | Евгений Темиргалеев [ Пятница, 12 Февраль, 2010 10:19 ] |
Заголовок сообщения: | Re: Этюд из книги "Построение компиляторов" |
Итого, три автоматичка ошиблись, двое не заметили... viewtopic.php?p=40339#p40339 viewtopic.php?p=42381#p42381 viewtopic.php?p=42473#p42473 Нет ли тут морали об излишней сложности метода решения? Плюс очередной пример errare humanum est к обоснованию чуйства "в таком месте код трогать без большой реальной нужды как-то ... стрёмно" |
Автор: | Peter Almazov [ Пятница, 12 Февраль, 2010 14:09 ] |
Заголовок сообщения: | Re: Этюд из книги "Построение компиляторов" |
Ну так решения с помощью автоматов крайне не наглядны в коде. Плюс обычные методы верификации программ здесь не работают. А модифицировать код практически невозможно, только создавать заново. |
Автор: | Валерий Лаптев [ Пятница, 12 Февраль, 2010 14:31 ] | ||
Заголовок сообщения: | Re: Этюд из книги "Построение компиляторов" | ||
Peter Almazov писал(а): Ну так решения с помощью автоматов крайне не наглядны в коде. Плюс обычные методы верификации программ здесь не работают. А модифицировать код практически невозможно, только создавать заново. Еще как возможно... ![]() Вот вам текст из моей книжки. Там реализация конечного автомата в трех видах представлена. Один из видов реализации - прекрасно изменяется без переделки уже созданного. ![]() Программы на С++, но вы, надеюсь, разберетесь.
|
Автор: | Peter Almazov [ Пятница, 12 Февраль, 2010 14:48 ] |
Заголовок сообщения: | Re: Этюд из книги "Построение компиляторов" |
Сразу же наткнулся на отсутствие рисунков. Специально? |
Автор: | Galkov [ Пятница, 12 Февраль, 2010 15:23 ] |
Заголовок сообщения: | Re: Этюд из книги "Построение компиляторов" |
1) Ну не ошибается тот, кто ничего не делает. Тут, на мой взгляд, история совершенно аналогичная языкам программирования. Наиболее прозрачное (это Вирт такое слово употреблял) отражение в коды дает ассемблер. Но мы пытамся изложить свои мысли на ЯВУ. Можем потом руками перевести это в АСМ. А можем написать программу, по имени компилятор - чтобы он не ошибался. Типа, если тебе компьютер имя, имя крепи делами своими. Тут же ровно то же самое. В ЭТОЙ постановке задачи невозможно ошибиться: Вложение: Comment1.png [ 11.59 КБ | Просмотров: 18813 ] Далее - можно ручками. И даже можно (если есть привычка, и каждодневная тренировка) без ошибок. А можно и "инструмент" сварганить - чтобы НИКОГДА не ошибался. Отмечу еще одно: рисуя патерн входа в Comment, я совершенно не заморачивался, а есть ли выше патерны, начинающиеся с левой скобки. Есть наверное, но их объединение - это "преждевременная оптимизация". Ничего не напоминает ??? ![]() 2) Стартовый код от Вирта мне не показался очень прозрачным. ![]() Всю башку себе сломал, пока пробился через него. Знаю ведь, что там нет ошибок, а внутренней уверенности все равно нет. 3) Валерий, а чего за книжка ![]() |
Автор: | Peter Almazov [ Пятница, 12 Февраль, 2010 15:45 ] |
Заголовок сообщения: | Re: Этюд из книги "Построение компиляторов" |
Здесь корень проблемы в том, что не отделена лексика от синтаксического анализатора. Все в куче. Если их разделить, то все получается очень просто, и главное, надежно. Парсер должен разобрать вот это: com = cbeg {char|com} cend. Сканер получается относительно большим по объему viewtopic.php?p=40336#p40336 , но код там очень простой, только занудный. |
Автор: | Валерий Лаптев [ Пятница, 12 Февраль, 2010 17:02 ] |
Заголовок сообщения: | Re: Этюд из книги "Построение компиляторов" |
Galkov писал(а): 3) Валерий, а чего за книжка ![]() Да я тут по системному ПО писал для своего 3 курса. Там джентльментский набор: виртуальная машина и ее интерпретатор, ассемблер и транслятор (для нее же), загрузчик и виды загружаемого модуля. Линкер и объектные модули, библиотекарь, мейкер, отладчик, профайлер. Но чего-то книжка пишется уже долго, и я ее отложил. А по конечным автоматам в связи с трансляцией числовых констант в ассемблере уже давно написал - вот там в файле и изложено. |
Автор: | Rifat [ Вторник, 06 Апрель, 2010 11:06 ] |
Заголовок сообщения: | Re: Этюд из книги "Построение компиляторов" |
У меня несколько отличный, чем в начале топика, вопрос, но также про книжку построение компиляторов и также про листинг приведенного там сканера 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 ] |
Заголовок сообщения: | Re: Этюд из книги "Построение компиляторов" |
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. |
Автор: | Rifat [ Вторник, 06 Апрель, 2010 11:27 ] |
Заголовок сообщения: | Re: Этюд из книги "Построение компиляторов" |
Да, согласен, вопрос в другом. Текущее состояние: 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 ] |
Заголовок сообщения: | Re: Этюд из книги "Построение компиляторов" |
Rifat писал(а): Условие ~R.eot & (ch <= " ") = TRUE следовательно выполняется Texts.Read(R, ch), теперь ch = "." и R.eot = TRUE, условие ~R.eot & (ch <= " ") = FALSE, цикл завершается. Нет. Теперь ch = "." и R.eot = FALSE. TRUE он станет в следующий раз, когда мы попытаемся прочитать за концом текста. |
Автор: | Rifat [ Вторник, 06 Апрель, 2010 11:37 ] |
Заголовок сообщения: | Re: Этюд из книги "Построение компиляторов" |
Спасибо, теперь понятно. |
Автор: | Rifat [ Вторник, 06 Апрель, 2010 11:46 ] |
Заголовок сообщения: | Re: Этюд из книги "Построение компиляторов" |
Может кто-нибудь знает, каким будет инвариант цикла для? WHILE ~R.eot & (ch <= " ") DO Texts.Read(R, ch) END; |
Автор: | Valery Solovey [ Вторник, 06 Апрель, 2010 12:24 ] |
Заголовок сообщения: | Re: Этюд из книги "Построение компиляторов" |
Предусловие: имеется текст, и все символы до текущего прочитаны. Инвариант: все символы до текущего прочитаны. Постусловие: текст закончился или встретился непробельный символ. |
Автор: | Peter Almazov [ Вторник, 06 Апрель, 2010 12:31 ] |
Заголовок сообщения: | Re: Этюд из книги "Построение компиляторов" |
Постусловие правильное, остальное неверно. Хотя, нет, и постусловие неправильное. |
Автор: | Rifat [ Вторник, 06 Апрель, 2010 14:26 ] |
Заголовок сообщения: | Re: Этюд из книги "Построение компиляторов" |
Первое, хотелось бы, что бы кто-нибудь все-таки написал инвариант цикла. Второе, понимаю, что первое апреля уже прошло, но все же, небольшая шуточка (в которой есть доля правды). Сканер 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 ] |
Заголовок сообщения: | Re: Этюд из книги "Построение компиляторов" |
Rifat писал(а): Кто может предложить способ обработки комментариев, которые не будет использовать рекурсию или стек, и который соответственно нельзя будет уронить описанным мной способом? Кх кх.. а Вы тему сначала-то читали?Там и этот viewtopic.php?p=45625#p45625 вопрос уже поднимался, и тот что Вы теперь подняли. |
Автор: | Rifat [ Вторник, 06 Апрель, 2010 14:43 ] |
Заголовок сообщения: | Re: Этюд из книги "Построение компиляторов" |
Тему я читал давно, сейчас еще раз перечитал, про то, что про eot там обсуждалось, сейчас нашел. Извиняюсь, что задал вопрос еще раз. А про то, что комменты рекурсивно обрабатываются и возможно переполнение стека, я к сожалению, не нашел, возможно проглядел. Вообще в теме по большей части обсуждается как можно красивее написать внутренности процедуры comment и как лучше сделать обработку вложенных комментариев. У меня же не вложенные комментарии, а подряд идущие, друг за другом, внутренности процедуры comment в данном случае меня не интересует. А интересует конструкция: comment; Get(sym); |
Автор: | Valery Solovey [ Вторник, 06 Апрель, 2010 21:57 ] |
Заголовок сообщения: | Re: Этюд из книги "Построение компиляторов" |
Peter Almazov писал(а): Постусловие правильное, остальное неверно. Хотя, нет, и постусловие неправильное. Ваш вариант |
Страница 3 из 4 | Часовой пояс: UTC + 3 часа |
Powered by phpBB® Forum Software © phpBB Group https://www.phpbb.com/ |