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 писал(а):
Ну так решения с помощью автоматов крайне не наглядны в коде. Плюс обычные методы верификации программ здесь не работают. А модифицировать код практически невозможно, только создавать заново.

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

Вложения:
Кое-что о конечных автоматах.rar [35.84 КБ]
Скачиваний: 229
Автор:  Peter Almazov [ Пятница, 12 Февраль, 2010 14:48 ]
Заголовок сообщения:  Re: Этюд из книги "Построение компиляторов"
Сразу же наткнулся на отсутствие рисунков. Специально?
Автор:  Galkov [ Пятница, 12 Февраль, 2010 15:23 ]
Заголовок сообщения:  Re: Этюд из книги "Построение компиляторов"
1) Ну не ошибается тот, кто ничего не делает.
Тут, на мой взгляд, история совершенно аналогичная языкам программирования. Наиболее прозрачное (это Вирт такое слово употреблял) отражение в коды дает ассемблер. Но мы пытамся изложить свои мысли на ЯВУ.
Можем потом руками перевести это в АСМ. А можем написать программу, по имени компилятор - чтобы он не ошибался. Типа, если тебе компьютер имя, имя крепи делами своими.
Тут же ровно то же самое. В ЭТОЙ постановке задачи невозможно ошибиться:
Вложение:
Comment1.png
Comment1.png [ 11.59 КБ | Просмотров: 9319 ]

Далее - можно ручками. И даже можно (если есть привычка, и каждодневная тренировка) без ошибок. А можно и "инструмент" сварганить - чтобы НИКОГДА не ошибался.
Отмечу еще одно: рисуя патерн входа в 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/