Парсер рекурсивного спуска должен быть быстрее
... или вы делаете что-то не так.
Во-первых, ваш код должен быть разбит на 2 отдельныхшаги.Лексер + Парсер.
Некоторые справочные примеры в Интернете сначала разбивают весь синтаксис на большие промежуточные структуры данных, а затем передают его синтаксическому анализатору.Хотя хорошо для демонстрации;не делайте этого, это удваивает время и сложность памяти.Вместо этого, как только лексер определит совпадение, уведомите синтаксический анализатор о переходе состояния или переходе состояния + данные.
Что касается лексера.Это, вероятно, где вы найдете свое текущее узкое место.Если лексер четко отделен от вашего парсера, вы можете попробовать переключаться между реализациями Regex и не-Regex, чтобы сравнить производительность.
Regex ни в коем случае не быстрее, чем чтение необработанных строк.Это просто позволяет избежать некоторых распространенных ошибок по умолчанию.В частности, ненужное создание строковых объектов.В идеале, ваш лексер должен сканировать ваш код и производить вывод с нулевыми промежуточными данными, кроме минимума, необходимого для отслеживания состояния в вашем анализаторе.В отношении памяти у вас должно быть:
- Необработанный ввод (т. Е. Источник)
- Состояние анализатора (например, isExpression, isSatement, строка, столбец)
- Данные (например, AST, Tree, 2D Array и т. Д.).
Например, если ваш текущий лексер соответствует нетерминалу и копирует каждый символ по одному, пока не достигнет следующего терминала;по сути, вы воссоздаете эту строку для каждой подходящей буквы.Имейте в виду, что строковые типы данных неизменны, concat всегда будет создавать новую строку.Вы должны сканировать текст, используя арифметику указателя или какой-либо эквивалент.
Чтобы решить эту проблему, вам нужно отсканировать от начальных позиций нетерминала до конца нетерминала и копировать только при совпадениизавершено.
Regex поддерживает все это по умолчанию из коробки, поэтому это предпочтительный инструмент для написания лексеров.Вместо того, чтобы пытаться написать Regex, который анализирует всю грамматику, напишите тот, который фокусируется только на сопоставлении терминалов и нетерминалов в качестве групп захвата.Пропустите токенизацию и передайте результаты непосредственно в свой анализатор / конечный автомат.
Ключ в том, что не пытайтесь использовать Regex в качестве конечного автомата.В лучшем случае он будет работать только для декларативных синтаксисов Regular (то есть Chomsky Type III, без стека) - отсюда и название Regular Expression.Например, HTML является декларативным синтаксисом без контекста (т. Е. Chomsky Type II, основанный на стеке), поэтому одного Rexeg никогда не достаточно для его анализа.Ваша грамматика и вообще все синтаксисы шаблонов попадают в эту категорию.Вы уже достигли предела Regex, поэтому вы на правильном пути.
Используйте Regex только для токенизации.Если вы действительно обеспокоены производительностью, перепишите свой лексер, чтобы исключить все ненужное копирование строк и / или промежуточные данные.Посмотрите, сможете ли вы превзойти версию Regex.
Ключ к тому же.Версию Regex легче понять и поддерживать, в то время как ваш лексер, созданный вручную, скорее всего, будет быстрее, если будет написан правильно.Обычная мудрость гласит: сделай себе одолжение и отдай предпочтение первому.С точки зрения сложности Big-O, между ними не должно быть никакой разницы.Это две формы одного и того же.