OberonCore https://forum.oberoncore.ru/ |
|
Этюд из книги "Построение компиляторов" https://forum.oberoncore.ru/viewtopic.php?f=82&t=2233 |
Страница 1 из 4 |
Автор: | Peter Almazov [ Суббота, 16 Январь, 2010 15:03 ] | ||
Заголовок сообщения: | Этюд из книги "Построение компиляторов" | ||
В тексте сканера OSS у Вирта есть, мягко говоря, не самый образцовый кусок. Вот он: Код: PROCEDURE comment; (Это вариант с CD для BB, из которого выброшен IF, увеличивающий номер строки, т. к. этого куска нет и у Вирта)BEGIN R.ReadChar(ch); LOOP LOOP WHILE ch = "(" DO R.ReadChar(ch); IF ch = "*" THEN comment END END; IF ch = "*" THEN R.ReadChar(ch); EXIT END; IF R.eot THEN EXIT END; R.ReadChar(ch) END; IF ch = ")" THEN R.ReadChar(ch); EXIT END; IF R.eot THEN Mark("комментарий не завершен"); EXIT END END END comment; Критиковать изощренную конструкцию из LOOPов и EXITов не вижу смысла, и так все ясно. Отмечу только, что в куске теоретически возможно чтение из файла после того, как будет истинно R.eot. На практике никакой ошибки не возникает, т. к. там оказывается 0X. Но как-то это неаккуратно. Задача переписать этот кусок "как надо" - отличный этюд для программирования. Маленький, относительно трудный (Вирт – не решил), и не надуманный, а 100% взятый из практики. Предлагаю всем, кто считает, что может профессионально писать надежные и понятные программы, решить этот этюд. Приверженцам идей Дейкстры - доказать делом свою приверженность. Любителям Дракона - проверить его [не]пригодность для решения этой задачи. Особенно интересными были бы результаты от любителей Дейкстры и Дракона одновременно (Илья, привет!). Свой вариант решения прилагаю в виде архива. Он запаролен, чтобы никак не повлиять на другие решения. Потом будет интересно их сравнить.
|
Автор: | Peter Almazov [ Суббота, 16 Январь, 2010 15:03 ] |
Заголовок сообщения: | Re: Этюд из книги "Построение компиляторов" |
Пароль: Loop_Exit_2010 Вот текст для удобства: Код: PROCEDURE comment; Т.к. исходные предпосылки, на основании которых делалось решение, оказались неверны, то оно представляет только историческую ценность.CONST char=0; eot=1; cbeg=2; cend=3; (* типы csym *) VAR ch2: CHAR; ch2hasVal: BOOLEAN; csym: INTEGER; (* минисканер, меняет: ch, csym, ch2hasVal, состояние R *) PROCEDURE getSym; BEGIN csym:=char; IF ch2hasVal THEN ch:=ch2; ch2hasVal:=FALSE; ELSIF R.eot THEN csym:= eot; ELSE R.ReadChar(ch); END; IF csym = char THEN IF ch= "(" THEN IF ~R.eot THEN R.ReadChar(ch2); IF ch2="*" THEN csym:=cbeg; ELSE ch2hasVal:=TRUE; END; END; ELSIF ch= "*" THEN IF ~R.eot THEN R.ReadChar(ch2); IF ch2=")" THEN csym:=cend; ELSE ch2hasVal:=TRUE; END; END; END; END; END getSym; PROCEDURE com(Level:INTEGER); (* минипарсер *) BEGIN getSym; (* инвариант цикла: от старта комментария до текущей позиции * вложенные комментарии обработаны, остальное пропущено *) WHILE (csym # eot) & (csym # cend) DO IF csym = cbeg THEN com(Level+1); ELSE getSym; END; END; IF csym = cend THEN IF Level=0 THEN R.ReadChar(ch); ELSE getSym; END; ELSE Mark("комментарий не завершен"); END; END com; BEGIN ch2hasVal:=FALSE; com(0); END comment; А именно, неверны предположения, что 1. R.eot "заглядывает вперед". 2. При R.eot=истина недопустимо чтение из файла. Я был зациклен на правильном построении циклов, и вариант с автоматом не рассматривал (а должен был бы!!!). Суть рассуждений сводится к следующему: грамматику комментариев можно описать так (обозначения те же, что и в программе): com = cbeg {char|com} cend. Здесь com – нетерминальный символ, остальные терминальные. Т.к. комментарии нужно пропускать, получается "язык в языке". Для языка комментариев определен свой минипарсер и минисканер. Для разбора используется метод рекурсивного спуска. Т.е., весь огород городился вот для этого цикла: Код: WHILE (csym # eot) & (csym # cend) DO Сейчас вижу, что лучше бы записать так:IF csym = cbeg THEN com; ELSE getSym; END; END; Код: WHILE (csym = char) OR (csym = cbeg) DO Готовый кандидат на цикл Дейкстры.IF csym = cbeg THEN com; ELSE getSym; END; END; Переменная Level там на фиг не нужна. Однако, пришлось ее ввести, чтобы корректно переключиться с минисканера, который заглядывает вперед на один символ, на обычное посимвольное чтение. Вот этот кусок мне больше всего не нравится. --------------------------- Вывод: для пропуска комментариев следует использовать конечный автомат, как это сделал Евгений. |
Автор: | Info21 [ Суббота, 16 Январь, 2010 17:08 ] | ||
Заголовок сообщения: | Re: Этюд из книги "Построение компиляторов" | ||
Проход по комментариям я уже где-то исправлял (кажется, в старых тулзовинах для поддержки олимпиад в старых школьных конфигурациях ББ). Подсказывать не буду. Идея технически простая, но не сразу зашоренным очам видная. Пример на самом деле, что называется, парадигматический и давно включен в мой курс. А на Вирта наезжать не надо -- ему простительно. Почему -- я объяснял в предисловии к "Алгоритмам". На всякий случай прилагаю свою подсказку, тоже запароленную. (Интересно, зачем 4 раза без пароля скачивали Пароль -- paraliter. В смысле по логике цикла его "бегунком" является пара литер, что и следует реализовать для полной очевидности.)
|
Автор: | Евгений Темиргалеев [ Суббота, 16 Январь, 2010 18:11 ] |
Заголовок сообщения: | Re: Этюд из книги "Построение компиляторов" |
Peter Almazov писал(а): Отмечу только, что в куске теоретически возможно чтение из файла после того, как будет истинно R.eot. На практике никакой ошибки не возникает, т. к. там оказывается 0X. Но как-то это неаккуратно. Не согласен. Не знаю как в системе Оберон сделаны читатели. Но для ББ это документированное поведение.TextModels docu писал(а): PROCEDURE (rd: Reader) Read
NEW, ABSTRACT Read the next element of the text. Post [описание постусловий в секции кода чтобы видеть отступы] Код: ~rd.eot rd.Pos() = rd'.Pos() + 1, rd.attr # NIL, rd.attr.init rd.view # NIL maskChar IN Prefs(view).opts, ch = Prefs(view).mask rd.char = ch ~(maskChar IN Prefs(view).opts) rd.char = viewcode rd.eot rd.Pos() = rd'.Pos(), rd.attr = NIL, rd.char = 0X, rd.view = NIL |
Автор: | Евгений Темиргалеев [ Суббота, 16 Январь, 2010 19:17 ] |
Заголовок сообщения: | Re: Этюд из книги "Построение компиляторов" |
Код: (* Вызывается когда "(" и "*" уже прочитано *) Это решение с ошибкой. См: viewtopic.php?p=42367#p42367
level := 1; (* 0 пропуск литер 1 считана ( ожидается * 2 считана * ожидается ) *) state := 0; WHILE ~R.eot & (level > 0) DO R.ReadChar(ch); CASE state OF | 0: IF ch = "(" THEN state := 1 ELSIF ch = "*" THEN state := 2 (* ELSE state := 0 *) END | 1: IF ch = "*" THEN INC(level) END; state := 0 | 2: IF ch = ")" THEN DEC(level) END; state := 0 END END; IF R.eot THEN Mark("комментарий не завершен") ELSE R.ReadChar(ch) END |
Автор: | Евгений Темиргалеев [ Суббота, 16 Январь, 2010 19:22 ] |
Заголовок сообщения: | Re: Этюд из книги "Построение компиляторов" |
Если текст заканчивается комментарием, виден вывод 0X. Реальный сканер в Comment выставляет ошибку разбора, от которого пляшет внешняя процедура. Код: MODULE Comment_test;
IMPORT In := i21sysIn, Log; PROCEDURE Get (OUT ch: CHAR); BEGIN In.Char(ch); IF ~In.done THEN ch := 0X END END Get; PROCEDURE Eot (): BOOLEAN; BEGIN RETURN ~In.done END Eot; PROCEDURE Echo (ch: CHAR); BEGIN IF ch = 0DX THEN Log.Ln ELSIF ch = 09X THEN Log.Tab ELSE Log.Char(ch) END END Echo; PROCEDURE Test*; VAR ch: CHAR; PROCEDURE Comment; VAR level, state: INTEGER; BEGIN level := 1; state := 0; WHILE ~Eot() & (level > 0) DO Get(ch); CASE state OF | 0: IF ch = "(" THEN state := 1 ELSIF ch = "*" THEN state := 2 (* ELSE state := 0 *) END | 1: IF ch = "*" THEN INC(level) END; state := 0 | 2: IF ch = ")" THEN DEC(level) END; state := 0 END END; IF Eot() THEN Log.String("комментарий не завершен"); Log.Ln ELSE Get(ch) END END Comment; BEGIN (* Test *) In.Open; Get(ch); WHILE ~Eot() DO IF ch = "(" THEN Get(ch); IF ch = "*" THEN Comment ELSE Echo("(") END END; Echo(ch); Get(ch) END END Test; END Comment_test. |
Автор: | Сергей Губанов [ Суббота, 16 Январь, 2010 21:39 ] |
Заголовок сообщения: | Re: Этюд из книги "Построение компиляторов" |
Код: ЧАСТЬ КомпиляторСканирование; ПОДКЛЮЧИТЬ литеры := КомпиляторЛитеры, символы := КомпиляторСимволы, Считывание := КомпиляторСчитывание, ... ТИПЫ Сканер* = ЗАПИСЬ считыватель: Считывание.Считыватель; литера: ЛИТЕРА16 КОНЕЦ; Орфограмма* = ЗАПИСЬ символ*: ЦЕЛОЕ32; ... КОНЕЦ; .... ПРОЦЕДУРА пропустить_комментарий (ЧЗ с: Сканер); ПЕРЕМЕННЫЕ вложенность: ЦЕЛОЕ32; НАЧАЛО СТРАХОВКА(с.литера = литеры.звёздочка); вложенность := 1; считать_литеру(с); ПОВТОРЯТЬ ЕСЛИ с.литера = литеры.звёздочка ТОГДА считать_литеру(с); ЕСЛИ с.литера = литеры.правая_круглая_скобка ТОГДА УМЕНЬШИТЬ(вложенность); считать_литеру(с) КОНЕЦ АЕСЛИ с.литера = литеры.левая_круглая_скобка ТОГДА считать_литеру(с); ЕСЛИ с.литера = литеры.звёздочка ТОГДА УВЕЛИЧИТЬ(вложенность); считать_литеру(с) КОНЕЦ ИНАЧЕ считать_литеру(с) КОНЕЦ ПРЕКРАТИТЬ (вложенность = 0) ИЛИ (с.литера = литеры.ноль); ЕСЛИ с.литера = литеры.ноль ТОГДА ошибка("незавершёный комментарий"); ОСТАНОВ(1) КОНЕЦ КОНЕЦ пропустить_комментарий; ... ПРОЦЕДУРА Сканировать (ЧЗ с: Сканер; З ф: Орфограмма); НАЧАЛО пропустить_пробелы(с); ЕСЛИ литеры.это_буква(с.литера) ТОГДА считать_слово(с, ф) АЕСЛИ литеры.это_цифра(с.литера) ТОГДА считать_число(с, ф) АЕСЛИ с.литера = литеры.левая_круглая_скобка ТОГДА считать_литеру(с); ЕСЛИ с.литера # литеры.звёздочка ТОГДА ф.символ := символы.левая_круглая_скобка ИНАЧЕ пропустить_комментарий(с); Сканировать(с, ф) КОНЕЦ АЕСЛИ с.литера = ... У моего сканера конец текста сигнализируется нулевой литерой: сканер.литера = литеры.ноль |
Автор: | Peter Almazov [ Суббота, 16 Январь, 2010 22:09 ] |
Заголовок сообщения: | Re: Этюд из книги "Построение компиляторов" |
2 Евгений Темиргалеев: все честно сделано, только перед концом нужно проверять не R.eot, а level=0. Конец файла после комментария - не криминал. |
Автор: | Сергей Губанов [ Суббота, 16 Январь, 2010 22:47 ] |
Заголовок сообщения: | Re: Этюд из книги "Построение компиляторов" |
Peter Almazov писал(а): нужно проверять не R.eot, а level=0 Точно! У меня тоже надо исправить.
|
Автор: | Peter Almazov [ Суббота, 16 Январь, 2010 22:59 ] |
Заголовок сообщения: | Re: Этюд из книги "Построение компиляторов" |
2 Сергей Губанов: сейчас читаю Ваш текст, но я имел в виду готовый кусок для непосредственной вставки в текст OSS: Код: PROCEDURE comment;
... END comment; |
Автор: | Евгений Темиргалеев [ Воскресенье, 17 Январь, 2010 05:05 ] |
Заголовок сообщения: | Re: Этюд из книги "Построение компиляторов" |
Peter Almazov писал(а): 2 Евгений Темиргалеев: все честно сделано, только перед концом нужно проверять не R.eot, а level=0. Конец файла после комментария - не криминал. R.eot выставляется при попытке чтения в конце текста. Т.е. если после цикла level=0, то ~R.eot. Т.к. последняя считанная в цикле литера ")". (Если R.eot, то цикл отработал с ch=0X)
|
Автор: | Илья Ермаков [ Воскресенье, 17 Январь, 2010 13:22 ] |
Заголовок сообщения: | Re: Этюд из книги "Построение компиляторов" |
У меня идея сразу возникла та же, что и у Евгения - счётчик вложенности, но автомат делать не захотелось на этот случай. Лучше иметь в поле зрения два символа и строить условия по ним. Получился цикл вида ЦД (только общий конъюнкт во внешнем WHILE, а дополнительные - во внутреннем IF; можно нормализовать, но мне кажется, что так даже лучше): Код: PROCEDURE Comment; VAR c1, c2: CHAR; level: INTEGER; BEGIN level := 1; R.ReadChar(c1); R.ReadChar(c2); WHILE (level > 0) & ~R.eot DO IF (c1 = "(") & (c2 = "*") THEN INC(level); R.ReadChar(c1); R.ReadChar(c2) ELSIF (c1 = "*") & (c2 = ")") THEN DEC(level); IF level > 0 THEN R.ReadChar(c1); R.ReadChar(c2) END ELSE c1 := c2; R.ReadChar(c2) END END; IF level > 0 THEN Mark("комментарий не завершён") END END Comment; Писал быстро и без проверки, где-то мог мелко ошибиться. А с Драконом - обычный структурный алгоритм, выход из цикла по одной ситуации; автоматности у меня в решении нет. Всё так же. |
Автор: | Info21 [ Воскресенье, 17 Январь, 2010 16:53 ] |
Заголовок сообщения: | Re: Этюд из книги "Построение компиляторов" |
Илья Ермаков писал(а): Писал быстро и без проверки, где-то мог мелко ошибиться. Два чтения подряд без охраны перед вторым -- это ошибка.
|
Автор: | Peter Almazov [ Воскресенье, 17 Январь, 2010 17:11 ] |
Заголовок сообщения: | Re: Этюд из книги "Построение компиляторов" |
Info21 писал(а): Два чтения подряд без охраны перед вторым -- это ошибка. Я раньше тоже исходил из этого, а получается, что - нет. Читай сколько угодно, Reader'у все по-барабану, будет гнать нули.
|
Автор: | Илья Ермаков [ Воскресенье, 17 Январь, 2010 17:13 ] |
Заголовок сообщения: | Re: Этюд из книги "Построение компиляторов" |
Да, я на это поведение ридера и полагался. В принципе, если мы позволяем чтение за концом файла с постусловием eot, то мы должны соблюдать условие: попытка использования считанного (двух символов в нашем случае) охраняется охраной ~R.eot. В приведённом цикле это выполняется. Но... с этой точки зрения он громоздковат. В принципе, можно рассмотреть это как линейный поиск конца комментария с подсчётом вложенности внутри. Код: level := 1;
R.ReadChar(c1); R.ReadChar(c2); WHILE ~eot & ~( (level = 0) & (c1 = "*") & (c2 = ")") ) DO IF (c1 = "(") & (c2 = "*") THEN INC(level); ELSIF (c1 = "*") & (c2 = ")") THEN DEC(level) END; c1 := c2; R.ReadChar(c2) END |
Автор: | Info21 [ Воскресенье, 17 Январь, 2010 18:16 ] |
Заголовок сообщения: | Re: Этюд из книги "Построение компиляторов" |
Peter Almazov писал(а): Читай сколько угодно, Reader'у все по-барабану, будет гнать нули. Тогда зачем eot. Либо одно, либо другое.Где сказано, что такое R? Вон у Е.Э. просто In, и там тут (пардон) будет ошибка. И документация, к примеру, для TextModels.Reader не оговаривает таких вещей. Алгоритм должен быть устойчивым к такой фигне. А оптимизация толсто оговорена. С ассертами. Помнится, были всё-таки какие-то проблемы в подобном случае, причем не так давно. Возможно, как раз с TextModels.Reader в струменте для русских ключевых слов. Поэтому тут (где одновременно eot и особое поведение ридера) как минимум нехорошая неаккуратность. |
Автор: | Илья Ермаков [ Воскресенье, 17 Январь, 2010 18:18 ] |
Заголовок сообщения: | Re: Этюд из книги "Построение компиляторов" |
Поставить для красоты вложенную процедуру ReadChar(c), с проверкой, и заменить R.ReadChar на неё. |
Автор: | Peter Almazov [ Воскресенье, 17 Январь, 2010 18:39 ] |
Заголовок сообщения: | Re: Этюд из книги "Построение компиляторов" |
Евгений Темиргалеев писал(а): R.eot выставляется при попытке чтения в конце текста. Для меня это было новостью, причем крайне неприятной.Везде, где встречался с функциями типа EOF, EndOfStream, они заглядывают вперед. Например, если открыть пустой файл, то EOF сразу будет истинно. В ББ все не так, eot=FALSE! А ведь могли бы установить в ложь, т.к. перед этим делается SetPos. Не берусь критиковать, т.к., возможно, в этом есть какой-то великий смысл. Если кто знает, просьба про него написать. Но несовместимость с другими языками (библиотеками) - налицо. |
Автор: | Илья Ермаков [ Воскресенье, 17 Январь, 2010 18:47 ] |
Заголовок сообщения: | Re: Этюд из книги "Построение компиляторов" |
Вроде бы, смысл в том, что семантика "попытаться взять элемент.." позволяет писать условие WHILE с использованием этого элемента: rd.ReadChar(c); WHILE ~rd.eot & (c # 0DX) DO rd.ReadChar(c) END Иначе операция чтения должна быть МЕЖДУ ~rd.eot и условием на символ. (В "массах" пишут for-break, конечно, им пофигу). Т.е. смысл тут такой же, как у сокращённого вычисления логики - позволить сложные условия записывать. |
Автор: | Сергей Губанов [ Воскресенье, 17 Январь, 2010 23:41 ] |
Заголовок сообщения: | Re: Этюд из книги "Построение компиляторов" |
Info21 писал(а): Peter Almazov писал(а): Читай сколько угодно, Reader'у все по-барабану, будет гнать нули. Тогда зачем eot. Либо одно, либо другое.Где сказано, что такое R? Вон у Е.Э. просто In, и там тут (пардон) будет ошибка. Если вдруг в нижележащем считывателе текста есть eot дальше которого читать запрещено, то эта неприятность легко устраняется введением считывателя-обёртки трансформирующего попытку чтения после eot в нулевые литеры. В текстовый сканер отдаётся вот этот "хороший" считыватель. Все алгоритмы сканирования текста при этом упрощаются. А сделать алгоритмы проще и есть цель. |
Страница 1 из 4 | Часовой пояс: UTC + 3 часа |
Powered by phpBB® Forum Software © phpBB Group https://www.phpbb.com/ |