OberonCore
https://forum.oberoncore.ru/

Этюд из книги "Построение компиляторов"
https://forum.oberoncore.ru/viewtopic.php?f=82&t=2233
Страница 2 из 4

Автор:  Galkov [ Понедельник, 18 Январь, 2010 08:34 ]
Заголовок сообщения:  Re: Этюд из книги "Построение компиляторов"

Сергей Губанов писал(а):
Если вдруг в нижележащем считывателе текста есть eot дальше которого читать запрещено, то эта неприятность легко устраняется введением считывателя-обёртки трансформирующего попытку чтения после eot в нулевые литеры.

В текстовый сканер отдаётся вот этот "хороший" считыватель. Все алгоритмы сканирования текста при этом упрощаются. А сделать алгоритмы проще и есть цель
Совершенно правильно.
Правда, более эффективно (чем програмные "прослойки") добавить лишний нулик(и) в конец файла... Или строки...

Автор:  Валерий Лаптев [ Понедельник, 18 Январь, 2010 09:26 ]
Заголовок сообщения:  Re: Этюд из книги "Построение компиляторов"

Peter Almazov писал(а):
Евгений Темиргалеев писал(а):
R.eot выставляется при попытке чтения в конце текста.
Для меня это было новостью, причем крайне неприятной.
Везде, где встречался с функциями типа EOF, EndOfStream, они заглядывают вперед. Например, если открыть пустой файл, то EOF сразу будет истинно. В ББ все не так, eot=FALSE! А ведь могли бы установить в ложь, т.к. перед этим делается SetPos.
Не берусь критиковать, т.к., возможно, в этом есть какой-то великий смысл. Если кто знает, просьба про него написать. Но несовместимость с другими языками (библиотеками) - налицо.

Не везде заглядывают вперед. В С++ для двоичного файла с записями после чтения последней записи никакого eof нет. Только при попытке чтения следующей записи выставляется eof. Студенты неоднократно на это нарывались. из-за этого в цикле оператор чтения приходится ставить последним, чтобы после него сразу выполнилась проверка. И читать перед циклом один раз (имеется ввиду цикл while).

Автор:  Виктор О [ Понедельник, 18 Январь, 2010 12:49 ]
Заголовок сообщения:  Re: Этюд из книги "Построение компиляторов"

Валерий Лаптев писал(а):
Peter Almazov писал(а):
Не везде заглядывают вперед. В С++ для двоичного файла с записями после чтения последней записи никакого eof нет. Только при попытке чтения следующей записи выставляется eof. Студенты неоднократно на это нарывались. из-за этого в цикле оператор чтения приходится ставить последним, чтобы после него сразу выполнилась проверка. И читать перед циклом один раз (имеется ввиду цикл while).

В прошлом году с этим нетривиальным eof у кого-то из новичков были проблемы, и я размышлял, почему заглядывающий eof был заменен на оглядывающийся.

Пришел к выводу, что смысл есть для смешанного чтения

ЦИКЛ
Читать(байт); Читать(целое); Читать(запись)
КОНЕЦЦИКЛА

В этом случае, в отличие от типизированного файла компьютер не может знать, удастся ли очередное чтение, поскольку требуемое количество байт разное. А старая реализация eof ИМХО просто аппаратно заглядывала в буфер, что недостаточно при чтении записей.

Поэтому правильным и структурным циклом чтения будет такой

TryLoop
Читаем(X)
If_EOF_go_EXIT_Loop
Применяем(X)
EndLoop

Его можно моделировать обычным LOOP, но обычный LOOP - пасынок Оберона :(

Автор:  Peter Almazov [ Понедельник, 18 Январь, 2010 14:46 ]
Заголовок сообщения:  Re: Этюд из книги "Построение компиляторов"

Galkov писал(а):
Правда, более эффективно (чем програмные "прослойки") добавить лишний нулик(и) в конец файла... Или строки...
Это не всегда возможно, т.к. нужно потребовать, чтобы нулик не встречался внутри файла иначе как в качестве обозначения конца файла.

Кстати, Сергей Губанов в своем варианте вообще не проверяет на конец файла, а рассматривает нуль как конец файла. Я считаю это недостатком, т.к. требуется, чтобы нули не встречались внутри комментария. Требование 100% разумное, но, с моей т.з., чересчур сильное. Если мы пытаемя улучшить вариант Вирта, сканер которого пропустит нули внутри комментария, то не должны позволять себе такой отсебятины.

Автор:  Сергей Губанов [ Понедельник, 18 Январь, 2010 15:10 ]
Заголовок сообщения:  Re: Этюд из книги "Построение компиляторов"

Кстати, в Блэкбоксе та же самая рекурсивная кракозябра с двумя вложенными лупами DevCPS:
Код:
      PROCEDURE Comment;   (* do not read after end of file *)
      BEGIN DevCPM.Get(ch);
         LOOP
            LOOP
               WHILE ch = "(" DO DevCPM.Get(ch);
                  IF ch = "*" THEN Comment END
               END ;
               IF ch = "*" THEN DevCPM.Get(ch); EXIT END ;
               IF ch = DevCPM.Eot THEN EXIT END ;
               DevCPM.Get(ch)
            END ;
            IF ch = ")" THEN DevCPM.Get(ch); EXIT END ;
            IF ch = DevCPM.Eot THEN err(5); EXIT END
         END
      END Comment;

Автор:  Сергей Губанов [ Понедельник, 18 Январь, 2010 15:24 ]
Заголовок сообщения:  Re: Этюд из книги "Построение компиляторов"

Peter Almazov писал(а):
Требование 100% разумное, но, с моей т.з., чересчур сильное.
Так 100% или не совсем 100%? Если ровно 100%, то какие могут быть ещё "но"-оговорки?
Peter Almazov писал(а):
Если мы пытаемся улучшить вариант Вирта, сканер которого пропустит нули внутри комментария, то не должны позволять себе такой отсебятины.
Так это Вы пытаетесь улучшить вариант Вирта, а я его выбросил нафикъ :D, у меня свой компилятор ещё более простой чем у Вирта: у меня конец текста - ноль.

Кстати, а не пора ли уже пароль от архива выложить?

Автор:  Galkov [ Понедельник, 18 Январь, 2010 15:43 ]
Заголовок сообщения:  Re: Этюд из книги "Построение компиляторов"

Вообще-то, мне показалось (!!!), что выложенные Виртом коды преследуют обучающую цель в большей степени, чем генерация оптимального кода.
Оптимальный код - это табличная обработка конечного автомата, написанная на асм-е. Что как два пальца, после разработки нужных таблиц, естественно... Мне думается...

И это для полного лексера, а не только для comment-а.

P.S. А вообще-то, у меня возникли "претензии" к Вирту по поводу строгости изложения тех же лексеров (ну или регулярных языков). Вот только куда запоститься - не понял еще :(

Автор:  Сергей Губанов [ Понедельник, 18 Январь, 2010 16:26 ]
Заголовок сообщения:  Re: Этюд из книги "Построение компиляторов"

Оптимизировал по производительности свой предыдущий вариант. Ещё исправил ошибку с утверждением о незавершённости комментария. Напоминаю, что мой считыватель сигнализирует о конце чтения текста нулевой литерой, её я сейчас переобозвал как "литеры.конец_текста" (для наглядности) (в ББ она называется DevCPM.Eot)
Код:
ПРОЦЕДУРА пропустить_комментарий (ЧЗ с: Сканер);
   ПЕРЕМЕННЫЕ вложенность: ЦЕЛОЕ32;
НАЧАЛО
   СТРАХОВКА(с.литера = литеры.звёздочка);
   вложенность := 1;
   считать_литеру(с);
   ПОВТОРЯТЬ
      ПОКА (с.литера # литеры.конец_текста) И (с.литера # литеры.звёздочка) И (с.литера # литеры.левая_круглая_скобка) ДЕЛАТЬ
         считать_литеру(с)
      КОНЕЦ;
      ЕСЛИ с.литера = литеры.звёздочка ТОГДА
         считать_литеру(с);
         ЕСЛИ с.литера = литеры.правая_круглая_скобка ТОГДА
            УМЕНЬШИТЬ(вложенность); считать_литеру(с)
         КОНЕЦ
      АЕСЛИ с.литера = литеры.левая_круглая_скобка ТОГДА
         считать_литеру(с);
         ЕСЛИ с.литера = литеры.звёздочка ТОГДА
            УВЕЛИЧИТЬ(вложенность); считать_литеру(с)
         КОНЕЦ
      КОНЕЦ;
   ПРЕКРАТИТЬ (вложенность = 0) ИЛИ (с.литера = литеры.конец_текста);
   ЕСЛИ вложенность > 0 ТОГДА
      ошибка("незавершёный комментарий")
   КОНЕЦ      
КОНЕЦ пропустить_комментарий;

Автор:  Peter Almazov [ Понедельник, 18 Январь, 2010 16:31 ]
Заголовок сообщения:  Re: Этюд из книги "Построение компиляторов"

Пароль и текст с комментариями - во втором сообщении от начала темы.

Автор:  Сергей Губанов [ Понедельник, 18 Январь, 2010 17:02 ]
Заголовок сообщения:  Re: Этюд из книги "Построение компиляторов"

Сергей Губанов писал(а):
Оптимизировал по производительности свой предыдущий вариант.
Вот аналог для Блэкбокса (модуль DevCPS)
Код:
      PROCEDURE Comment;
         VAR level: INTEGER;
      BEGIN DevCPM.Get(ch); level := 1;
         REPEAT
            WHILE (ch # DevCPM.Eot) & (ch # "*") & (ch # "(") DO DevCPM.Get(ch) END;
            IF ch = "*" THEN
               DevCPM.Get(ch);
               IF ch = ")" THEN DEC(level); DevCPM.Get(ch) END
            ELSIF ch = "(" THEN
               DevCPM.Get(ch);
               IF ch = "*" THEN INC(level); DevCPM.Get(ch) END
            END
         UNTIL (level = 0) OR (ch = DevCPM.Eot);
         IF level > 0 THEN err(5) END
      END Comment;

Автор:  Trurl [ Понедельник, 18 Январь, 2010 17:44 ]
Заголовок сообщения:  Re: Этюд из книги "Построение компиляторов"

Сергей Губанов писал(а):
Вот аналог для Блэкбокса (модуль DevCPS)


Ох, не советую этот аналог подключать к Блэкбоксу ;)

Автор:  Сергей Губанов [ Понедельник, 18 Январь, 2010 18:41 ]
Заголовок сообщения:  Re: Этюд из книги "Построение компиляторов"

Почему?

Автор:  Info21 [ Понедельник, 18 Январь, 2010 21:41 ]
Заголовок сообщения:  Re: Этюд из книги "Построение компиляторов"

Сергей Губанов писал(а):
Почему?
Береженого бог бережет...

Автор:  Сергей Губанов [ Понедельник, 18 Январь, 2010 23:57 ]
Заголовок сообщения:  Re: Этюд из книги "Построение компиляторов"

Не смотря на то, что конец чтения сигнализируется DevCPM.Eot лишнего-то чтения (за пределами DevCPM.Eot) в этом алгоритме не делается. Так что же вас пугает?

Автор:  Trurl [ Вторник, 19 Январь, 2010 09:00 ]
Заголовок сообщения:  Re: Этюд из книги "Построение компиляторов"

Не, все нормально. Это я ошибся, перепутал с gpcp.

Автор:  Евгений Темиргалеев [ Вторник, 19 Январь, 2010 09:47 ]
Заголовок сообщения:  Re: Этюд из книги "Построение компиляторов"

Info21 писал(а):
Сергей Губанов писал(а):
Почему?
Береженого бог бережет...

Согласен. Правка даст альтернативную версию (изменёны исходники) с нулевым различием по функционалу:
- не ошибка
- не оптимизация (разницу в скорости компиляции никто не увидет)
Т.е. в ней просто нет смысла.

Напоминаю, что речь изначально шла про более грамотную запись учебного примера.

Автор:  Сергей Губанов [ Вторник, 19 Январь, 2010 11:50 ]
Заголовок сообщения:  Re: Этюд из книги "Построение компиляторов"

Евгений Темиргалеев писал(а):
Правка даст альтернативную версию (изменёны исходники) с нулевым различием по функционалу:
- не ошибка
- не оптимизация (разницу в скорости компиляции никто не увидет)
Т.е. в ней просто нет смысла.
У меня есть что сказать по этому поводу. Начну издалека.

Вчера вечером на работе наткнулся на следующий код:
Код:
      private string ParseDestination (string sParse)
      {
         bool bFirstEnterence = true;
         string sReturnText = String.Empty;
         string sCutText = String.Empty;

         for (int i = 0; i < sParse.Length; i++)
         {
            sCutText = sParse.Substring(i, 1);
            if (!new Regex("^[0-9]+$").IsMatch(sCutText) && bFirstEnterence)
            {
               continue;
            }
            else
            {
               bFirstEnterence = false;
               if (new Regex("^[0-9]+$").IsMatch(sCutText))
                  sReturnText += sCutText;
               else break;
            }
         }

         return sReturnText;
      }
По замыслу автора этот алгоритм извлекает из строки непрерывную последовательность цифр отбрасывая нецифровой заголовок и хвост если они есть. Немного поясню, что тут написано для тех кто с C# не очень хорошо знаком. Здесь в цикле из строки извлекалась одна буква, создавалась (размещалась в динамической памяти) новая строка длины 1 из этой буквы. Создавалась (размещалась в динамической памяти) машина распознавания регулярных выражений. Эта машина использовалась один раз и выбрасывалась. Использовалась она для того, чтобы узнать состоит ли новая строка из цифр или нет (это при том, что эта строка всего из одной буквы). Так для каждой буквы заголовка. Когда нецифровой заголовок строки наконец пропускался, то срабатывал флаг bFirstEnterence и управление отныне всегда передавалось на вторую ветвь условного оператора внутри тела цикла. Однако, так как проверка флага осуществлялась во вторую очередь, то теперь машина распознавания регулярных выражений создавалась, использовалась и выбрасывалась уже по два раза на каждую букву и в if и в else блоках. Результат побуквенно присовокуплялся к строке sReturnText причём каждое такое присовокупление приводило к созданию (размещению в динамической памяти) нового экземпляра строки в силу иммутабельности строк в дотнете. Понятно, что создавая множество временных (паразитных) объектов этот код ещё и лишний раз жестоко напрягал сборщик мусора.

Что надо было сделать?
  • Для начала убедиться что строка не пуста: if (!string.IsNullOrEmpty(s))
  • Пропустить нецифровой заголовок: int i = 0; while ((i < n) && !IsDigit(s[i])) { i++; }
  • Если последовательность цифр найдена if (i < n) тогда:
  • Запомнить её начало: int start = i;
  • Пропустить все цифры последовательности (найти начало нецифрового хвоста): while ((i < n) && IsDigit(s[i])) { i++; }
  • Вычислить количество цифр в найденной последовательности: int count = i - start;
  • Извлечь ответ: result = s.Substring(start, count);
Код:
      private string ParseDestination (string s)
      {
         string result = string.Empty;
         if (!string.IsNullOrEmpty(s))
         {
            int n = s.Length;
            int i = 0;
            while ((i < n) && !IsDigit(s[i])) { i++; }
            if (i < n)
            {
               int start = i;
               while ((i < n) && IsDigit(s[i])) { i++; }
               int count = i - start;
               result = s.Substring(start, count);
            }
         }
         return result;
      }

      private static bool IsDigit (char c)
      {
         return ('0' <= c) && (c <= '9');
      }
И каков сухой остаток? А никакой:
- не ошибка
- не оптимизация (разницу в скорости работы всей программы никто не увидет, так как не каждый раз этот говнокод вызывается)
Т. е. в моей правке просто нет смысла :D :D :D

Автор:  Info21 [ Вторник, 19 Январь, 2010 14:25 ]
Заголовок сообщения:  Re: Этюд из книги "Построение компиляторов"

Чистить надо, но в таком месте код трогать без большой реальной нужды как-то ... стрёмно :)

Автор:  Peter Almazov [ Вторник, 19 Январь, 2010 15:55 ]
Заголовок сообщения:  Re: Этюд из книги "Построение компиляторов"

Info21 писал(а):
Чистить надо, но в таком месте код трогать без большой реальной нужды как-то ... стрёмно :)
Что может быть безобиднее, чем пропуск комментариев? Это ж не генератор кода.

Автор:  Евгений Темиргалеев [ Вторник, 19 Январь, 2010 18:37 ]
Заголовок сообщения:  Re: Этюд из книги "Построение компиляторов"

Но это и не внутрефирменный "код на работе", а компилятор, которым пользуется совершенно разные люди и организации.

Так что разница в "Правка даст альтернативную версию (изменёны исходники)" велика.

Страница 2 из 4 Часовой пояс: UTC + 3 часа
Powered by phpBB® Forum Software © phpBB Group
https://www.phpbb.com/