OberonCore
https://forum.oberoncore.ru/

Вычисление относительных выражений
https://forum.oberoncore.ru/viewtopic.php?f=61&t=1607
Страница 1 из 1

Автор:  Валерий Лаптев [ Четверг, 21 Май, 2009 08:50 ]
Заголовок сообщения:  Вычисление относительных выражений

Коллеги, прошу внимания!
Пишу я сейчас для книжки по системному программированию транслятор с ассемблера (вернее, несколько разных версий).
Дошел до перемещаемого модуля как результат трансляции.
Соответственно, парсер выражений перестает быть абсолютным и требуется различать относительные и абсолютные имена и выражения.
Обычный парсер написан по методу рекурсивного спуска по следующей обычной грамматике:
E = T {+T|-T}
T = F {*F | /F | %F }
F = A |+A|-A
A = константа|функция|имя|(E)
То есть Е - это абсолютное выражение.
Теперь, чтобы различать абсолютные и относительные, я добавляю в грамматику правилa:
R = R { +V |-V } | (R) | имяR
V = R-R | E
Далее - грамматика для E.
В последнем правиле для Е заменяем имя на имяА. Таким образом, определим две разные функции для получения значения метки: для относительной и абсолютной.

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

Автор:  Valery Solovey [ Четверг, 21 Май, 2009 11:00 ]
Заголовок сообщения:  Re: Вычисление относительных выражений

А что такое относительные выражения?

Автор:  Валерий Лаптев [ Четверг, 21 Май, 2009 11:26 ]
Заголовок сообщения:  Re: Вычисление относительных выражений

Valery Solovey писал(а):
А что такое относительные выражения?

Они же - адресные, они же перемещаемые.
Транслятор с ассемблера на первом проходе вычисляет смещения всех меток операторов. Все метки, помечающие команды или данные, по умолчанию являются относительными. Ибо абсолютные адреса памяти, представленные в программе именем-меткой, требуется изменять при загрузке увеличивая на адрес загрузки.
Абсолютные - это типа непосредственный операнд в команде. Он при загрузке никогда не изменяется.
Например в Интеле есть команда mov ax, 5 - тут абсолютное выражение. А в команде
lea ax, name - выражение относительное (name - адрес памяти).

Автор:  Valery Solovey [ Четверг, 21 Май, 2009 12:16 ]
Заголовок сообщения:  Re: Вычисление относительных выражений

Чем A отличается от T?
Если F = A + A, то *F = *A + A, а не *(A + A). А что самое неприятное - теряется очерёдность приоритетов (умножение и сложение становятся равноправными).

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

Автор:  Валерий Лаптев [ Пятница, 22 Май, 2009 11:52 ]
Заголовок сообщения:  Re: Вычисление относительных выражений

Грамматика для E - это классическая грамматика для арифметических выражений. Здесь звездочка - это не разыменование, а как раз умножение. Правило для F учитывает унарный плюс и минус. А правило для A уже либо обращается к терминалам, либо обеспечивает рекурсивный вызов для вычисления выражения в скобках.

Автор:  Valery Solovey [ Суббота, 23 Май, 2009 16:40 ]
Заголовок сообщения:  Re: Вычисление относительных выражений

Я так и понял, что звёздочка - это не разыменование. То есть, допустимы такие конструкции?
Код:
A*-A/+A

Арифметические выражения из книги Свердлова:
Код:
E → TA
A → ε | + TA | - TA
T → MB
B → ε | * MB | / MB
M → a | b | c | ( E )

А для унарного знака, наверное, лучше так:
Код:
E → TA | -TA



И всё равно не понятно, как будет выглядеть грамматика после добавления R.

Автор:  Валерий Лаптев [ Суббота, 23 Май, 2009 16:59 ]
Заголовок сообщения:  Re: Вычисление относительных выражений

Большое спасибо за наводку на Свердлова!
Как-то я про него забыл. Посмотрю.

Автор:  Валерий Лаптев [ Вторник, 26 Май, 2009 08:08 ]
Заголовок сообщения:  Re: Вычисление относительных выражений

Свердлов помог.
Я обычую грамматику переписал так:
A=+E|-E|E
E = T {+T|-T}
T = F {*F | /F | %F }
F = константа|функция|имя|(A)
Получилось лучше.
Относительность и абсолютность выражений на уровне LL(1) грамматики - сложно состряпать, если вообще возможно.
Дело в том, что возможны выражения R-A и R-R. Один и тот же символ (минус) в множестве first для разных правил. И там еще минус в правиле для E. А состряпать грамматику с единственным минусом мне не удалось (видно, тямы :) не хватает).
Я обошелся другим способом.
Просто вычислителю задается, какой тип выражений он должен считать, и он в лоб проверяет, соответствуют ли аргументы и операции этому выражению.

Автор:  Евгений Темиргалеев [ Вторник, 26 Май, 2009 09:06 ]
Заголовок сообщения:  Re: Вычисление относительных выражений

Интересно, какого года книга Свердлова... У Вирта такая грамматика ещё в синтаксисе Паскаля.

Автор:  Валерий Лаптев [ Вторник, 26 Май, 2009 10:21 ]
Заголовок сообщения:  Re: Вычисление относительных выражений

Евгений Темиргалеев писал(а):
Интересно, какого года книга Свердлова... У Вирта такая грамматика ещё в синтаксисе Паскаля.

Да понятно, что Свердлов у Вирта подсматривал :)
Но мне книга Свердлова нравится больше всего, ибо написана преподом именно для студентов. Отсюда - простой и понятный язык. Но все, что нужно - есть.
И еще, мужик реализовал язык О сразу на паскале, обероне, С++, Яве и Додиезе - и все листинги привел. Есть элемент для сравнения.
Относительно С++ могу сказать, что он, видимо, не имеет практики на С++, поэтому использовал немного устаревшие части С++.

Автор:  Valery Solovey [ Вторник, 26 Май, 2009 10:22 ]
Заголовок сообщения:  Re: Вычисление относительных выражений

>Интересно, какого года книга Свердлова...
http://www.piter.com/book.phtml?978546900378

Описываемый в книге язык О - очень урезанная версия Оберона.

Автор:  Info21 [ Вторник, 26 Май, 2009 10:26 ]
Заголовок сообщения:  Re: Вычисление относительных выражений

Евгений Темиргалеев писал(а):
Интересно, какого года книга Свердлова...
2007.

Автор:  Valery Solovey [ Вторник, 26 Май, 2009 10:28 ]
Заголовок сообщения:  Re: Вычисление относительных выражений

Валерий Лаптев писал(а):
Относительность и абсолютность выражений на уровне LL(1) грамматики - сложно состряпать, если вообще возможно.
Вся проблема из-за имён? Не известно, какое константа, а какое адрес? Так пусть это решается на уровне словаря имён. При разборе указывается ссылка на положение в словаре нужного имени, где делается соответствующая пометка, а при трансляции эта пометка учитывается.

Автор:  Евгений Темиргалеев [ Вторник, 26 Май, 2009 10:38 ]
Заголовок сообщения:  Re: Вычисление относительных выражений

Валерий Лаптев писал(а):
Да понятно, что Свердлов у Вирта подсматривал :)
Я так намекаю, что хорошую классику почитать полезно. Для меня интересен такой момент: где +- как унарные операции выделены, допустимо:
3 * -b + -a
При Виртовской грамматике, только как в математике можно:
3 * (-b) + (-a).

Автор:  Валерий Лаптев [ Вторник, 26 Май, 2009 13:09 ]
Заголовок сообщения:  Re: Вычисление относительных выражений

Valery Solovey писал(а):
Валерий Лаптев писал(а):
Относительность и абсолютность выражений на уровне LL(1) грамматики - сложно состряпать, если вообще возможно.
Вся проблема из-за имён? Не известно, какое константа, а какое адрес? Так пусть это решается на уровне словаря имён. При разборе указывается ссылка на положение в словаре нужного имени, где делается соответствующая пометка, а при трансляции эта пометка учитывается.

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

Автор:  Valery Solovey [ Вторник, 26 Май, 2009 15:50 ]
Заголовок сообщения:  Re: Вычисление относительных выражений

А это, наверное, делать лучше с помощью контекстных проверок: если текущая операция в списке разрешающих использовать относительные имена (или перемещаемые?), то одно из имён может быть относительным, иначе, ошибка.

Автор:  Валерий Лаптев [ Вторник, 26 Май, 2009 15:55 ]
Заголовок сообщения:  Re: Вычисление относительных выражений

Да я уже сделал все. Работает и различает относительные и абсолютные.

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