Size: a a a

Compiler Development

2020 July 09

VK

Val Krylov in Compiler Development
fldlg2
@val_krylov Если удобства важнее компьютерных ресурсов, или если входной поток не слишком длинный / не слишком многозначный, то можно найти аргументы в пользу top-down. Если входной поток огромен, а промежуточное parse tree — непозволительное излишество, то LALR вне конкуренции, как мне кажется.
Пока я не видел ни одного примера удобств top-down (кроме "проще написать, если нет готового генератора для bottom-up").
источник

c

cevek in Compiler Development
Alexander Tchitchigin
Статей не знаю — я в своё время "Дизайн и Эволюцию C++" читал. Может, кто-то посоветует что-то более конкретное.
Альтернативно можно посмотреть как делают в GObject/GTK+.
почитал про виртуальные методы, по сути практически хешмапа, также идет поиск указанного интерфейса в классе входящего объекта
источник

IK

Ivan Kochurkin in Compiler Development
fldlg2
@val_krylov Если удобства важнее компьютерных ресурсов, или если входной поток не слишком длинный / не слишком многозначный, то можно найти аргументы в пользу top-down. Если входной поток огромен, а промежуточное parse tree — непозволительное излишество, то LALR вне конкуренции, как мне кажется.
Неправда - используя LL тоже не обязательно строить промежуточное parse tree, ANTLR это позволяет например.
источник

AT

Alexander Tchitchigi... in Compiler Development
cevek
почитал про виртуальные методы, по сути практически хешмапа, также идет поиск указанного интерфейса в классе входящего объекта
Нет. Смещения заранее известны, так что просто массив.
источник

f

fldlg2 in Compiler Development
Ivan Kochurkin
Неправда - используя LL тоже не обязательно строить промежуточное parse tree, ANTLR это позволяет например.
Да, можно реализовать LL как табличный парсер, очень похожий на табличный LR-парсер 😊
источник

AT

Alexander Tchitchigi... in Compiler Development
cevek
почитал про виртуальные методы, по сути практически хешмапа, также идет поиск указанного интерфейса в классе входящего объекта
Поиска указанного интерфейса тоже нет, потому что передаётся указатель на нужную таблицу в месте вызова.
источник

c

cevek in Compiler Development
ну пример, у нас 1000 классов, и каждого класса имплементировано по 1000 разных интерфейсов в каждом классе свой набор, в функции мы принимаем 1 конкретный интерфейс, как он найдет смещение для этого интерфейса?
источник

IK

Ivan Kochurkin in Compiler Development
fldlg2
Да, можно реализовать LL как табличный парсер, очень похожий на табличный LR-парсер 😊
Грамматика остается LL, но дерево придется строить восходящим образом, если оно нужно.
источник

MM

Mikhail Maltsev in Compiler Development
cevek
а есть статейки хорошие?
источник

AT

Alexander Tchitchigi... in Compiler Development
cevek
ну пример, у нас 1000 классов, и каждого класса имплементировано по 1000 разных интерфейсов в каждом классе свой набор, в функции мы принимаем 1 конкретный интерфейс, как он найдет смещение для этого интерфейса?
В месте вызова компилятор знает какой класс используется, соответственно, знает, по какому смещению он разместил нужную таблицу. 🤷‍♀️
источник

c

cevek in Compiler Development
Alexander Tchitchigin
В месте вызова компилятор знает какой класс используется, соответственно, знает, по какому смещению он разместил нужную таблицу. 🤷‍♀️
а если у нас 1000 разных мест вызова функции и в каждый вызов применяется разный класс?
источник

VK

Val Krylov in Compiler Development
@fldlg2 Даже сам "выбор алгоритма" для bottom-up, как мне кажется, лучше оставить тоже алгоритму. Берём грамматику, а из неё в простейшем случае получается DFA, в сложном гибридный GLR, а где-то между "народный" LALR(1). Russ Cox давно делал что-то подобное, но только для ниши regular expressions https://swtch.com/~rsc/regexp/
источник

AT

Alexander Tchitchigi... in Compiler Development
cevek
а если у нас 1000 разных мест вызова функции и в каждый вызов применяется разный класс?
Не вижу никакой разницы. 🤷‍♀️
источник

f

fldlg2 in Compiler Development
Ivan Kochurkin
Грамматика остается LL, но дерево придется строить восходящим образом, если оно нужно.
Можно даже LALR реализовать как recursive ascent, но зачем? 😉 https://en.wikipedia.org/wiki/Recursive_ascent_parser
источник

f

fldlg2 in Compiler Development
Val Krylov
@fldlg2 Даже сам "выбор алгоритма" для bottom-up, как мне кажется, лучше оставить тоже алгоритму. Берём грамматику, а из неё в простейшем случае получается DFA, в сложном гибридный GLR, а где-то между "народный" LALR(1). Russ Cox давно делал что-то подобное, но только для ниши regular expressions https://swtch.com/~rsc/regexp/
Да, это всё детали реализации. Но эти детали приходится учитывать, выстраивая грамматику. Получается паразитная обратная связь 😉
источник

c

cevek in Compiler Development
Alexander Tchitchigin
Не вижу никакой разницы. 🤷‍♀️
все равно не понимаю, как в x в месте g.print() определить смещение? классы же приходят разные
interface A {void print()}
interface B {...}
interface C {...}
interface D {...}
class Foo implements B, A {...}
class Bar implements C, A {...}
function x(A g) {g.print()}
x(new Foo())
x(new Bar())
источник

IK

Ivan Kochurkin in Compiler Development
Зачем делать это не знаю, но не строить дефолтное дерево в LL парсере нужно, чтобы потреблять меньше памяти и использовать привычные и удобные LL грамматики, которых много.
источник

AT

Alexander Tchitchigi... in Compiler Development
cevek
все равно не понимаю, как в x в месте g.print() определить смещение? классы же приходят разные
interface A {void print()}
interface B {...}
interface C {...}
interface D {...}
class Foo implements B, A {...}
class Bar implements C, A {...}
function x(A g) {g.print()}
x(new Foo())
x(new Bar())
Смещение функции print в виртуальной таблице для интерфейса A одинаковое для всех классов.
источник

ВМ

Виталий Медоваров... in Compiler Development
cevek
все равно не понимаю, как в x в месте g.print() определить смещение? классы же приходят разные
interface A {void print()}
interface B {...}
interface C {...}
interface D {...}
class Foo implements B, A {...}
class Bar implements C, A {...}
function x(A g) {g.print()}
x(new Foo())
x(new Bar())
Ты сначала находишь адрес виртуальной таблицы для соответствующего интерфейса, далее просто по смещению там смотришь. Получается несколько шагов
источник

ВМ

Виталий Медоваров... in Compiler Development
При этом, если конкретный класс известен на этапе компиляции, динамической диспетчеризации может вообще не быть а будет сразу заинлайнен нужный вызов
источник