СЛ
Например можно на С++ написать ТАКОЕ, что даже gcc начинает испытывать трудности
Size: a a a
2020 March 21
PS
а за какое сейчас парсится? n*log(n)?
Вы совершили алгоритмический прорыв, судя по всему. Поскольку привычные для этого чата Эрли, GLR и CYK работают за O(n^3).
AT
Например можно на С++ написать ТАКОЕ, что даже gcc начинает испытывать трудности
Ну, к написанию своих языков это имеет мало отношения.
А грамматика C++ всё равно ни в какие формализмы не влазит - по-любому руками придётся разбирать. 🤷♀️
А грамматика C++ всё равно ни в какие формализмы не влазит - по-любому руками придётся разбирать. 🤷♀️
PS
в общем я к тому что для компиляторов время парсинга занимает очень мало времеин по сравнению с другими частями, и тут скорость парсинга не важна даже если будет n^2 времени, так как оно будет чувствоваться на файлах >10к строк.
Время разбора вполне может занимать и половину всего времени компиляции. Сужу по некоторым чужим и своим компиляторам. А у Вас откуда информация?
AT
Вы совершили алгоритмический прорыв, судя по всему. Поскольку привычные для этого чата Эрли, GLR и CYK работают за O(n^3).
Я только подзабыл, n - это что там? Мне почему-то кажется, что входную строку GLR всё равно один раз читает. Но работы производит не константное количество на токен.
AK
Например можно на С++ написать ТАКОЕ, что даже gcc начинает испытывать трудности
Много где можно перенапрячь систему. Как в недавнем меме - “Everybody gangsta until a JSON file is 700GB”
IJ
в общем я к тому что для компиляторов время парсинга занимает очень мало времеин по сравнению с другими частями, и тут скорость парсинга не важна даже если будет n^2 времени, так как оно будет чувствоваться на файлах >10к строк.
Ну такие файлы не то, чтобы редкость
IJ
Особенно если речь идет о сгенерированных файлах с кодом
PS
Я только подзабыл, n - это что там? Мне почему-то кажется, что входную строку GLR всё равно один раз читает. Но работы производит не константное количество на токен.
n — длина разбираемой строки
AT
n — длина разбираемой строки
Что-то мне кажется такую оценку можно и уточнить. Как минимум - считать токены, а не символы. 😊
PS
Что-то мне кажется такую оценку можно и уточнить. Как минимум - считать токены, а не символы. 😊
А что это даст для _худшего_ случая? В формализме КСГ вообще нет отдельного понятия токенов :)
A
Вы совершили алгоритмический прорыв, судя по всему. Поскольку привычные для этого чата Эрли, GLR и CYK работают за O(n^3).
CF-грамматики можно парсить за время умножения матриц (на практике O(n^log2(7)) Штрассеном)
SS
Что-то мне кажется такую оценку можно и уточнить. Как минимум - считать токены, а не символы. 😊
Разве это существенно? Длина лексемы ограничена, поэтому в смысле О-большого это одно и то же. Хотя про токены говорить естественней в таком разговоре.
p
Время разбора вполне может занимать и половину всего времени компиляции. Сужу по некоторым чужим и своим компиляторам. А у Вас откуда информация?
ну я пишу в основном на Rust сейчас, там парсинг 50к+ строк занимает 31 мс
p
это 0,07% от общего времени компиляции
AT
Разве это существенно? Длина лексемы ограничена, поэтому в смысле О-большого это одно и то же. Хотя про токены говорить естественней в таком разговоре.
Я знаю, но для меня разница всё равно есть. 😊
Всё-таки читать символы из внешнего источника и манипулировать токенами в памяти - не одно и то же.
Всё-таки читать символы из внешнего источника и манипулировать токенами в памяти - не одно и то же.
PS
CF-грамматики можно парсить за время умножения матриц (на практике O(n^log2(7)) Штрассеном)
Да, хотя это, скорее, чисто теоретический результат.
VM
Например можно на С++ написать ТАКОЕ, что даже gcc начинает испытывать трудности
Конечно, войны американской и европейской школ ЯП уже предмет анекдотов про их "бессмысленность и беспощадность", но в речи некоторых лауреатов премии Тьюринга можно прочитать:
не стоит делать грамматику языка программирования "под компьютер".
Т.е. надо делать максимально простой.
(
И, IMHO, мастерство создателя ЯП в этом.
)
не стоит делать грамматику языка программирования "под компьютер".
Т.е. надо делать максимально простой.
(
И, IMHO, мастерство создателя ЯП в этом.
)
PS
это 0,07% от общего времени компиляции
Тут любопытно, что принимается за общее время — этап LLVM туда входит?
p
Тут любопытно, что принимается за общее время — этап LLVM туда входит?
нет