Size: a a a

Compiler Development

2020 June 08

MM

Mikhail Maltsev in Compiler Development
LALR(1) разве не O(N)?
источник

AT

Alexander Tchitchigi... in Compiler Development
Я что-то не помню как там математически это дело формулируется, но, наверное, все грамматики, которые *(1) работают за линейное время. Проблема в том, что не так много языков, которые реально под них подходят.
источник

E

Eugene in Compiler Development
Yaroslav Schekin
Я сразу предупрежу, что не очень в этом разбираюсь, но:

> зачем нужен лексер?

И

> Почему бы сразу не парсить текст в базовое промежуточное представление, минуя AST?

Не связаны друг с другом, нет? Lexer занимается преобразованием в поток токенов, а не построением AST.
Т.е. какой у Вас именно вопрос?
вам, наверное, стоит почитать про парсерные комбинаторы
источник

AT

Alexander Tchitchigi... in Compiler Development
Кажется, все популярные сейчас языки программирования по факту вообще контекстно-зависимые.
источник

IK

Ivan Kochurkin in Compiler Development
Дерево строится как минимум для того, чтобы проходить по нему несколько раз. Иначе как, например, в однопроходном компиляторе узнать, что за сущность объявлена ниже? Для этого информацию о классах и методах надо сначала собрать, а потом вывести типы.
источник

IK

Ivan Kochurkin in Compiler Development
Ну и как уже сказали выше, лексинг и парсинг обычно очень быстрый. А парсер на токенах быстрее парсера на тексте.
источник

YS

Yaroslav Schekin in Compiler Development
Eugene
вам, наверное, стоит почитать про парсерные комбинаторы
А там lexer строит AST? ;) Или зачем мне про них читать?
источник

p

polunin.ai in Compiler Development
Ivan Kochurkin
Ну и как уже сказали выше, лексинг и парсинг обычно очень быстрый. А парсер на токенах быстрее парсера на тексте.
это все эмпирические заключения, либо же подтвержденные хоть как-то?
источник

AT

Alexander Tchitchigi... in Compiler Development
polunin.ai
это все эмпирические заключения, либо же подтвержденные хоть как-то?
Для справки: "эмпирические" — это как раз "хоть как-то подтверждённые". Скорее всего, Вы имели в виду "умозрительные". 😊
источник

E

Eugene in Compiler Development
Yaroslav Schekin
А там lexer строит AST? ;) Или зачем мне про них читать?
там нет лексера — парсер получает исходный текст и выдаёт AST
источник

PS

Peter Sovietov in Compiler Development
Eugene
там нет лексера — парсер получает исходный текст и выдаёт AST
Там что хотите, то и будет :)
источник

AT

Alexander Tchitchigi... in Compiler Development
Yaroslav Schekin
А там lexer строит AST? ;) Или зачем мне про них читать?
Там лексинг и парсинг можно соединить в одну функцию. Но можно и разделить. Очень гибкая штука.
источник

YS

Yaroslav Schekin in Compiler Development
Eugene
там нет лексера — парсер получает исходный текст и выдаёт AST
Я про это ниже написал. https://t.me/CompilerDev/67737
источник

AT

Alexander Tchitchigi... in Compiler Development
Eugene
там нет лексера — парсер получает исходный текст и выдаёт AST
It depends. По крайней мере, "хорошие" библиотеки комбинаторов полностью параметризованы по входу и по выходу, поэтому можно написать и разбор текста, и разбор потока токенов. Или бинарный парсер.
источник

E

Eugene in Compiler Development
упс, сорян, не туда ответил
источник

YS

Yaroslav Schekin in Compiler Development
Alexander Tchitchigin
Там лексинг и парсинг можно соединить в одну функцию. Но можно и разделить. Очень гибкая штука.
Вы пытаетесь украсть изменить контекст обсуждения, или как? ;)
Я задавал уточняющий вопрос, если что.
источник

AT

Alexander Tchitchigi... in Compiler Development
Yaroslav Schekin
Вы пытаетесь украсть изменить контекст обсуждения, или как? ;)
Я задавал уточняющий вопрос, если что.
Типа "троллил"? ОК, извините, не распознал. 🤷‍♀️
источник

YS

Yaroslav Schekin in Compiler Development
Alexander Tchitchigin
Типа "троллил"? ОК, извините, не распознал. 🤷‍♀️
Не хамите. И перечитайте обсуждение, если не дошло.
источник

IK

Ivan Kochurkin in Compiler Development
polunin.ai
это все эмпирические заключения, либо же подтвержденные хоть как-то?
Когда токенов нет, это значит, что "токеном" является каждый символ текста. В большинстве случаев в этом нет смысла (за исключением какого-нибудь Markdown).

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

rule
   : subrule
   | A B
   ;

subrule
   : A C
   ;

Если при парсинге rule сфейлились на subrule, то по крайней мере не надо перевычислять токен A, когда попадаем во вторую альтернативу.

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

p

polunin.ai in Compiler Development
Ivan Kochurkin
Когда токенов нет, это значит, что "токеном" является каждый символ текста. В большинстве случаев в этом нет смысла (за исключением какого-нибудь Markdown).

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

rule
   : subrule
   | A B
   ;

subrule
   : A C
   ;

Если при парсинге rule сфейлились на subrule, то по крайней мере не надо перевычислять токен A, когда попадаем во вторую альтернативу.

Возможно в большинстве случаев фазу лексинга можно заинлайнить прямо в парсер, но от этого токены же не исчезнут.
тут можно заменить на
rule
 : A (B | C)
 ;
источник