Size: a a a

Compiler Development

2021 April 03

LA

Liber Azerate in Compiler Development
smthidk
у меня такой довольно нубский вопрос:
есть тестовое задание, в нем нужно ручками написать парсер языка по заданной грамматике
грамматика эта леворекурсивная, поэтому не хочется выдумывать костыли и писать для нее рекурсивный спуск, но при этом писать LR - еще хуже
скажите по своему опыту (возможно, по опыту проверки тестовых заданий): будет ли ок, если я видоизменю изначальную грамматику так, чтобы в ней не было левой рекурсии? или корректнее работать с тем, что дали изначально?
У меня нет какого-то опыта проверки, но обычно как раз ведь устраняется левая рекурсия. Так что думаю, это может быть в частности проверка на это
источник

s

smthidk in Compiler Development
если так, то прекрасно
спасибо
источник

K

Kir in Compiler Development
smthidk
у меня такой довольно нубский вопрос:
есть тестовое задание, в нем нужно ручками написать парсер языка по заданной грамматике
грамматика эта леворекурсивная, поэтому не хочется выдумывать костыли и писать для нее рекурсивный спуск, но при этом писать LR - еще хуже
скажите по своему опыту (возможно, по опыту проверки тестовых заданий): будет ли ок, если я видоизменю изначальную грамматику так, чтобы в ней не было левой рекурсии? или корректнее работать с тем, что дали изначально?
Если грамматика будет распознавать те же языки, и не делать это за O(exp(N)), то вопросов, думаю, не будет
источник

K

Kir in Compiler Development
smthidk
у меня такой довольно нубский вопрос:
есть тестовое задание, в нем нужно ручками написать парсер языка по заданной грамматике
грамматика эта леворекурсивная, поэтому не хочется выдумывать костыли и писать для нее рекурсивный спуск, но при этом писать LR - еще хуже
скажите по своему опыту (возможно, по опыту проверки тестовых заданий): будет ли ок, если я видоизменю изначальную грамматику так, чтобы в ней не было левой рекурсии? или корректнее работать с тем, что дали изначально?
Я как-то устранял экспоненту в парсере кортежей с аннотациями элементов и в итоге у меня было что-то вроде рекурсивного подъёма руками.

В любом случае, LR парсит за O(N).
источник

KR

K R in Compiler Development
Alexander Tchitchigin
Небезызвестная "The death of optimizing compilers" -- а есть ли запись выступления где-нибудь на Youtube? Предвкушаю, что оно феерично! 😄
Большое спасибо!

Это, всё-таки, скорее наброс в известном стиле "крутой пожилой профессор пересматривает основы", поэтому название совершенно не отражает содержание, которое, если "в двух словах":

1. Код разделился на hot & cold, что связано с большими объёмами данных, которые пропускаются через системы. А объёмы данных связаны с тем, что они реально лимитированы терпением конечных пользователей к тормозам (есть диалектическая пара - "производительность компа" и "объём данных, которые через него будут пропускать). Очень важно знать, какой кусок программы cold, какой hot.

2. Ручные оптимизации работают значительно лучше компиляторных, поскольку человек понимает, какие данные с какой вероятностью могут проходить через систему. А передать компилятору эти знания не может.

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

В данном случае, компилятор знает многое о машине, но рассказать разработчику не может.

4. Резюме - компилятору и разработчику нужен диалог. И этот диалог надо вести на одном языке.
источник

KR

K R in Compiler Development
То есть, насколько я понимаю, Бернштайн хочет что-то вроде

Написали на С++, пометили где горячий участок, компилятор раскрыл это место в стиле С, сохранив высокоуровневый код в виде псевдокода. Дальше можно посмотрев на то, что компилятор нагенерировал, добавить какие-то дополнительные ограничения на входные данные и статистику с прогонов PGO.
источник

KR

K R in Compiler Development
Регер же "слайды не читал, но осуждает" - отвечает на название, которое - откровенный наброс. И, соответственно, практически весь его ответ пролетает мимо.
источник

M

MrSmith in Compiler Development
K R
Большое спасибо!

Это, всё-таки, скорее наброс в известном стиле "крутой пожилой профессор пересматривает основы", поэтому название совершенно не отражает содержание, которое, если "в двух словах":

1. Код разделился на hot & cold, что связано с большими объёмами данных, которые пропускаются через системы. А объёмы данных связаны с тем, что они реально лимитированы терпением конечных пользователей к тормозам (есть диалектическая пара - "производительность компа" и "объём данных, которые через него будут пропускать). Очень важно знать, какой кусок программы cold, какой hot.

2. Ручные оптимизации работают значительно лучше компиляторных, поскольку человек понимает, какие данные с какой вероятностью могут проходить через систему. А передать компилятору эти знания не может.

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

В данном случае, компилятор знает многое о машине, но рассказать разработчику не может.

4. Резюме - компилятору и разработчику нужен диалог. И этот диалог надо вести на одном языке.
Он профессор? Если так то мне льстит это
источник

M

MrSmith in Compiler Development
Когда то давно я с теми же идеями писал здесь про bx
источник

M

MrSmith in Compiler Development
Ровно также мысль, нужно как то научить компилятор общаться с программистом, причем как это сделать визуально я придумал
источник

M

MrSmith in Compiler Development
И даже вполне как сделать не визуально, но... Мне снова не хватило теории что бы понять как это сделать в архитектуре
источник

M

MrSmith in Compiler Development
K R
То есть, насколько я понимаю, Бернштайн хочет что-то вроде

Написали на С++, пометили где горячий участок, компилятор раскрыл это место в стиле С, сохранив высокоуровневый код в виде псевдокода. Дальше можно посмотрев на то, что компилятор нагенерировал, добавить какие-то дополнительные ограничения на входные данные и статистику с прогонов PGO.
Ну почти у меня дизайн все же из ide с закосом был
источник

M

MrSmith in Compiler Development
Но проблема что там окошек требовалось многовато
источник

M

MrSmith in Compiler Development
Я с @hirrolot когда то общался на тему управляемых оптимизаций и интерфейса. Может быть когда нибудь, если я найду ещё кого то, и буду достаточно подкован в теме bx, можно будет протестировать идею на компиляторе си.
Основная идея была примерно такой если бы компилятор представлял из себя одну большую линзу кое с чем ещё он был бы способен отображать оптимизации прямо на код. Но да похоже немного на бред сумасшедшего.
источник

M

MrSmith in Compiler Development
Он бы кстати ещё был одновременно и декомпилятором, и любой бекенд становился бы ещё автоматически и фронтендом, вообшем да звучит как бред
источник

M

MrSmith in Compiler Development
Вообще кому такое интересно?
источник

KR

K R in Compiler Development
MrSmith
Я с @hirrolot когда то общался на тему управляемых оптимизаций и интерфейса. Может быть когда нибудь, если я найду ещё кого то, и буду достаточно подкован в теме bx, можно будет протестировать идею на компиляторе си.
Основная идея была примерно такой если бы компилятор представлял из себя одну большую линзу кое с чем ещё он был бы способен отображать оптимизации прямо на код. Но да похоже немного на бред сумасшедшего.
Я не знаю, кто он, но часто такое - убеленный крутой чувак выступает с набросом «мы все всё делаем не так»
источник

M

MrSmith in Compiler Development
Ну так и есть, смотри я тут местный дурак а тоже самое говорю
источник

M

MrSmith in Compiler Development
Просто работающий код лучше не работающего
источник

M

MrSmith in Compiler Development
Это известный факт
источник