Comments 16
У автора в оригинале нет идиоматики, почему она есть в переводе: о каком герое речь?
На одном из курсов Udacity на его основе создают простейший браузер.
Тема очень интересная и я в свободное время ей занимаюсь.
Когда-то я писал движок вики-подобного языка разметки. Первая ошибка, которую я допустил было смешивание уровней токенизации и построения дерева из последовательности токенов (т.е. tokenizer / lexer). Полученная штука была жутковатой, в частности, её было сложно модифицировать, было множество специальных кейсов, введение новых синтаксисов вводило новые специальные кейсы и ломало работу уже существующих.
Потом я писал шаблонизатор, в нём я осуществил разбивку этих двух этапов, в результате код стал очень простой и здоровый. Собственно, этот шаг мне видится разумным, но есть один связанный вопрос, который меня занимает.
Предположим у нас есть некоторый ЯП. Что считать токеном? Пусть в ЯП есть литералы строк: набор символов заключённых в двойные кавычки. По сути, это может быть один токен, который достаточно легко описать одной регуляркой (если регулярки поддерживают ленивость). Но если пойти дальше, то оказывается, что внутри строки тоже не всё так просто, могут быть эскейп последовательности, существует интерполяция. НО при этом внутри строки не действуют обычные токены языка. То есть внутри строки нет for, if, нет чисел и нет других строк. И ещё там важны пробелы, т.е. это значащие символы. Это означает, что токен строки это отдельный подъязык со своей грамматикой.
Получается, что на этапе токенизации мы должны заморачиваться с каким-то переключением контекста итп вещами, хотя этот этап должен быть очень простым. Налицо анализ последовательности токенов. То есть уровни всё таки как-то проникают друг в друга!? Мой вопрос в том, как разрешается это затруднение? Где кончается токенизация и начинается синтаксический анализ?
Заранее спасибо.
Ну так в начало поставить регулярку по типу r'"(.*?)"' а эти эскейпы для начало можно игнорировать, вот с парсером надо заморочится. А когда ты сможешь получить это выражение то просто сделать в AST класс "StrAexp" для строки.
На текущий момент самым простым и приятным в использовании для меня стал peg. Можно просто описывать грамматику высокоуровнево, а библиотека построит для нас более-менее оптимальные лексер и парсер сама, соответственно, отпадает необходимость разбираться самим что на данном уровне является элементарным токеном, а что нет. Я использовал на практике peg.js, она очень приятна в использовании. В качестве бонуса можно также делать простые трансформации того что было спарсено перед вставкой результата в ast. На практике это очень перспективный подход.
Если нужно что-то более оптимальное, то наилучшим вариантом вижу те же парсер комбинаторы. По сути мы так же пишем нашу грамматику, но уже в виде конкретных парсеров, которые затем комбинируются операторами И и ИЛИ в финальный парсер. Преимущество в том, что т.к. мы лучше знаем нашу грамматику, мы можем построить наилучший парсер. Всё это работает без бектрека (как и peg).
На практике регулярки хороши для регулярных грамматик, у них есть пределы. Для более сложных грамматик уже лучше использовать парсер комбинаторы или peg (да у них тоже есть пределы).
Простой интерпретатор с нуля на Python (перевод) #1