РС
Строит ли regex внутри таблицу переходов?)
Size: a a a
2021 March 06
РС
RS
У меня нет. В первом приближении можно попробовать перевести гуглом. А так там не очень много страниц и можно прочитать со словарем за не очень большое время.
DP
да, что-то такое
а подобные ленивые вычисления на зависимостях как-то красиво реализуются?
насколько понимаю, если в ооп-терминологии рассуждать, у каждого объекта есть какая-то метка виртуального времени, и движок запускает те вычисления, у описания которых эта метка меньше? т.е. реактивность на основе сравнения меток времени
насколько понимаю, если в ооп-терминологии рассуждать, у каждого объекта есть какая-то метка виртуального времени, и движок запускает те вычисления, у описания которых эта метка меньше? т.е. реактивность на основе сравнения меток времени
M
Каким способом можно реализовать с алгоритмом сортировочной станции не математематические операторы и сложные rvalue типа compound literals?
M
Нашел хак где к примеру тернарный оператор реализуют как два оператора один из которых с более низким приоритетом
K
Каким способом можно реализовать с алгоритмом сортировочной станции не математематические операторы и сложные rvalue типа compound literals?
При помощи улучшенной версии shunting yard'а - которая табличный LR - вот так, например:
https://github.com/Heimdell/LR/blob/master/app/Main.hs#L10
Это внутренее DSL, так что сорян за
https://github.com/Heimdell/LR/blob/master/app/Main.hs#L10
Это внутренее DSL, так что сорян за
\\\\ и всякие EOpt
M
Это shift reduce? Я про табличный парсер
K
Нашел хак где к примеру тернарный оператор реализуют как два оператора один из которых с более низким приоритетом
Не, тут это по-человечески делается.
Expr -> Expr1 ? Expr : Expr
Expr1 -> тут операции более высокого приоритета
K
Это shift reduce? Я про табличный парсер
Ага
ДК
Не могли бы вы порекомендовать литературы по реализации инкрементальной проверки типов и вообще общей структуры реализации компилятора если я хочу сразу делать поддержку IDE/LSP.
Я начал писать игрушечный язык, для того чтобы окончательно разобраться в том как все устроено (парсер/лексер/тайпчек/интерпретация/компиляция в х86/поддержка IDE), но я не совсем понимаю как лучше всего собственно реализовывать все. Из https://www.youtube.com/watch?v=wSdV1M7n4gQ&t=1818s и https://www.youtube.com/watch?v=74Y1n2v-gos&t=2106s я понял что большая часть принципов построения компиляторов слабо применима для работы IDE - в то время как при компиляции мы делаем полный проход по коду сверху вниз то для интерактивной работы мы фактически с нуля (с какими-то оптимизациями) собираем только нужную нам информацию.
Таким образом получается после CST/AST уже практически никаких схожих элементов нет, и фактически я пишу две разные программы, но может быть какие-то вещи которые я упустил.
И еще по поводу написания рекурсивного спуска - https://news.ycombinator.com/item?id=13915150 - я правильно понимаю что в конечном итоге если я хочу делать компилятор и IDE то можно переиспользовать парсер, только добавил поддержку инкрементального разбора? И если да то как это лучше всего сделать - я посмотрел но не нашел ничего про то как добавить это (есть вещи типа "A simple and efficient incremental LL(1) parsing", но там про табличные парсеры). Кидаться в код каких-то промышленных компиляторов (типа rustc или roslyn) я пока еще не готов, особенно если стоит вопрос просто общего понимания принципов.
Про tree-sitter знаю, но хотелось бы все же не делать два разных AST без острой на то необходимости.
Я начал писать игрушечный язык, для того чтобы окончательно разобраться в том как все устроено (парсер/лексер/тайпчек/интерпретация/компиляция в х86/поддержка IDE), но я не совсем понимаю как лучше всего собственно реализовывать все. Из https://www.youtube.com/watch?v=wSdV1M7n4gQ&t=1818s и https://www.youtube.com/watch?v=74Y1n2v-gos&t=2106s я понял что большая часть принципов построения компиляторов слабо применима для работы IDE - в то время как при компиляции мы делаем полный проход по коду сверху вниз то для интерактивной работы мы фактически с нуля (с какими-то оптимизациями) собираем только нужную нам информацию.
Таким образом получается после CST/AST уже практически никаких схожих элементов нет, и фактически я пишу две разные программы, но может быть какие-то вещи которые я упустил.
И еще по поводу написания рекурсивного спуска - https://news.ycombinator.com/item?id=13915150 - я правильно понимаю что в конечном итоге если я хочу делать компилятор и IDE то можно переиспользовать парсер, только добавил поддержку инкрементального разбора? И если да то как это лучше всего сделать - я посмотрел но не нашел ничего про то как добавить это (есть вещи типа "A simple and efficient incremental LL(1) parsing", но там про табличные парсеры). Кидаться в код каких-то промышленных компиляторов (типа rustc или roslyn) я пока еще не готов, особенно если стоит вопрос просто общего понимания принципов.
Про tree-sitter знаю, но хотелось бы все же не делать два разных AST без острой на то необходимости.
Для работы автокомплита всё равно придётся распарсить все файлы ибо подсказывать нужно даже то, что не "заимпорчено", но может быть "автоимпорчено". А вот результат парсинга нужно кешировать, желательно на диск, и хорошо бы, чтобы он не зависел от других файлов, а не как в сишечке.
2021 March 07
РС
Правильно ли я понимаю? Прошу советов
Как уже писал ранее, хочу написать универсальный лексико-синтаксический анализатор (лексический + синтаксический).
На входе: набор грамматик
На выходе: синтаксическое дерево, на узлы которого пользователь навешивает делегаты и делает что ему нужно.
Думаю это будет LL(1) - т.к. с рекурсивным спуском знаком лучше и он проще.
Читаю книгу дракона и пытаюсь составить для себя общую последовательность действий.
Поступают грамматики:
Для лексического анализатора:
1. из грамматик строится НКА, который затем преобразуется в ДКА (или сразу строится ДКА)
2.из ДКА строится таблица переходов
Для синтаксического анализатора:
1. из грамматик строится синтаксическая таблица разбора
Как это работает:
1. Лексический анализатор используя таблицу переходов читает входную строку и передает лексемы синтаксическому анализатору
2. Синтаксический анализатор используя свою таблицу разбора - строит дерево разбора
Где-то между ними обработка ошибок (не заканчивать работу после первой ошибки, а продолжать проверку)
Как уже писал ранее, хочу написать универсальный лексико-синтаксический анализатор (лексический + синтаксический).
На входе: набор грамматик
На выходе: синтаксическое дерево, на узлы которого пользователь навешивает делегаты и делает что ему нужно.
Думаю это будет LL(1) - т.к. с рекурсивным спуском знаком лучше и он проще.
Читаю книгу дракона и пытаюсь составить для себя общую последовательность действий.
Поступают грамматики:
Для лексического анализатора:
1. из грамматик строится НКА, который затем преобразуется в ДКА (или сразу строится ДКА)
2.из ДКА строится таблица переходов
Для синтаксического анализатора:
1. из грамматик строится синтаксическая таблица разбора
Как это работает:
1. Лексический анализатор используя таблицу переходов читает входную строку и передает лексемы синтаксическому анализатору
2. Синтаксический анализатор используя свою таблицу разбора - строит дерево разбора
Где-то между ними обработка ошибок (не заканчивать работу после первой ошибки, а продолжать проверку)
YS
Правильно ли я понимаю? Прошу советов
Как уже писал ранее, хочу написать универсальный лексико-синтаксический анализатор (лексический + синтаксический).
На входе: набор грамматик
На выходе: синтаксическое дерево, на узлы которого пользователь навешивает делегаты и делает что ему нужно.
Думаю это будет LL(1) - т.к. с рекурсивным спуском знаком лучше и он проще.
Читаю книгу дракона и пытаюсь составить для себя общую последовательность действий.
Поступают грамматики:
Для лексического анализатора:
1. из грамматик строится НКА, который затем преобразуется в ДКА (или сразу строится ДКА)
2.из ДКА строится таблица переходов
Для синтаксического анализатора:
1. из грамматик строится синтаксическая таблица разбора
Как это работает:
1. Лексический анализатор используя таблицу переходов читает входную строку и передает лексемы синтаксическому анализатору
2. Синтаксический анализатор используя свою таблицу разбора - строит дерево разбора
Где-то между ними обработка ошибок (не заканчивать работу после первой ошибки, а продолжать проверку)
Как уже писал ранее, хочу написать универсальный лексико-синтаксический анализатор (лексический + синтаксический).
На входе: набор грамматик
На выходе: синтаксическое дерево, на узлы которого пользователь навешивает делегаты и делает что ему нужно.
Думаю это будет LL(1) - т.к. с рекурсивным спуском знаком лучше и он проще.
Читаю книгу дракона и пытаюсь составить для себя общую последовательность действий.
Поступают грамматики:
Для лексического анализатора:
1. из грамматик строится НКА, который затем преобразуется в ДКА (или сразу строится ДКА)
2.из ДКА строится таблица переходов
Для синтаксического анализатора:
1. из грамматик строится синтаксическая таблица разбора
Как это работает:
1. Лексический анализатор используя таблицу переходов читает входную строку и передает лексемы синтаксическому анализатору
2. Синтаксический анализатор используя свою таблицу разбора - строит дерево разбора
Где-то между ними обработка ошибок (не заканчивать работу после первой ошибки, а продолжать проверку)
На первый взгляд похоже... а какие советы Вам нужны?
РС
Yaroslav Schekin
На первый взгляд похоже... а какие советы Вам нужны?
1. Не совсем понятно как должен действовать лексический анализатор, если по таблице переходов у него должен идти отличный от текущего терминал/символ
2. Как все же обрабатывать ошибки, чтобы получить желаемый результат (не заканчивать работу после первой ошибки, а продолжать проверку)
2. Как все же обрабатывать ошибки, чтобы получить желаемый результат (не заканчивать работу после первой ошибки, а продолжать проверку)
YS
1. Не совсем понятно как должен действовать лексический анализатор, если по таблице переходов у него должен идти отличный от текущего терминал/символ
2. Как все же обрабатывать ошибки, чтобы получить желаемый результат (не заканчивать работу после первой ошибки, а продолжать проверку)
2. Как все же обрабатывать ошибки, чтобы получить желаемый результат (не заканчивать работу после первой ошибки, а продолжать проверку)
1. Я не понял вопроса. Если у построенного NFA/DFA в этом состоянии нет перехода по текущему символу входного потока, то это (лексическая) ошибка. Что с ней делать — зависит от того, как взаимодействуют lexer и parser. Вы об этом спрашивали?
2. В Dragon book описано несколько методов обработки (восстановления после) ошибок для LL — используйте тот или те, которые Вам подойдут.
2. В Dragon book описано несколько методов обработки (восстановления после) ошибок для LL — используйте тот или те, которые Вам подойдут.
РС
Yaroslav Schekin
1. Я не понял вопроса. Если у построенного NFA/DFA в этом состоянии нет перехода по текущему символу входного потока, то это (лексическая) ошибка. Что с ней делать — зависит от того, как взаимодействуют lexer и parser. Вы об этом спрашивали?
2. В Dragon book описано несколько методов обработки (восстановления после) ошибок для LL — используйте тот или те, которые Вам подойдут.
2. В Dragon book описано несколько методов обработки (восстановления после) ошибок для LL — используйте тот или те, которые Вам подойдут.
1. Да, а схемы обработки лексических и синтаксических ошибок одинаковы?
YS
1. Да, а схемы обработки лексических и синтаксических ошибок одинаковы?
Не обязательно.
Но я не знаю, есть ли сейчас для LL-подобных (top-down) parsers какой-то принятый общий подход для обработки ошибок — если это интересует, поищите / подождите — может, подскажут.
Но я не знаю, есть ли сейчас для LL-подобных (top-down) parsers какой-то принятый общий подход для обработки ошибок — если это интересует, поищите / подождите — может, подскажут.
K
Правильно ли я понимаю? Прошу советов
Как уже писал ранее, хочу написать универсальный лексико-синтаксический анализатор (лексический + синтаксический).
На входе: набор грамматик
На выходе: синтаксическое дерево, на узлы которого пользователь навешивает делегаты и делает что ему нужно.
Думаю это будет LL(1) - т.к. с рекурсивным спуском знаком лучше и он проще.
Читаю книгу дракона и пытаюсь составить для себя общую последовательность действий.
Поступают грамматики:
Для лексического анализатора:
1. из грамматик строится НКА, который затем преобразуется в ДКА (или сразу строится ДКА)
2.из ДКА строится таблица переходов
Для синтаксического анализатора:
1. из грамматик строится синтаксическая таблица разбора
Как это работает:
1. Лексический анализатор используя таблицу переходов читает входную строку и передает лексемы синтаксическому анализатору
2. Синтаксический анализатор используя свою таблицу разбора - строит дерево разбора
Где-то между ними обработка ошибок (не заканчивать работу после первой ошибки, а продолжать проверку)
Как уже писал ранее, хочу написать универсальный лексико-синтаксический анализатор (лексический + синтаксический).
На входе: набор грамматик
На выходе: синтаксическое дерево, на узлы которого пользователь навешивает делегаты и делает что ему нужно.
Думаю это будет LL(1) - т.к. с рекурсивным спуском знаком лучше и он проще.
Читаю книгу дракона и пытаюсь составить для себя общую последовательность действий.
Поступают грамматики:
Для лексического анализатора:
1. из грамматик строится НКА, который затем преобразуется в ДКА (или сразу строится ДКА)
2.из ДКА строится таблица переходов
Для синтаксического анализатора:
1. из грамматик строится синтаксическая таблица разбора
Как это работает:
1. Лексический анализатор используя таблицу переходов читает входную строку и передает лексемы синтаксическому анализатору
2. Синтаксический анализатор используя свою таблицу разбора - строит дерево разбора
Где-то между ними обработка ошибок (не заканчивать работу после первой ошибки, а продолжать проверку)
Это очень похоже на yacc/menhir/happy.
M
Ребят такой вопрос а как верно собирать исполняемый фаил
M
llc? Или дергать как то либу можно