Это ручная кодировка педали на металлический вопрос, а не ANTLR против BISON.
Кроме того, это для разбора двоичного формата. Лексического анализа нет.Анализаторы LL (1) более эффективны для префиксного кодирования, а LR (1) более эффективны для постфикса?
Стоимость разбора строгого пред- (постсоветского) порядка тривиальна, используя методы сверху вниз или снизу вверх. Это будет затмевать любая из других задач, даже лексический анализ. Крошечные разницы в скорости будут результатом деталей реализации, а не алгоритмической стратегии.
Нет смысла использовать парсер LR (1), поскольку для представления предзаказов или послепорядков вам не нужны маркерные представления, предполагая, что представление является чисто предварительным или пост-упорядоченным. LR (0) будет просто отлично. Вы вряд ли найдете полезный генератор парсеров LR (0), но если вы хотите вручную написать парсер, этот факт упростит вашу задачу.
Игнорируя сейчас LL (1) и LR (1), вы обычно разбираете эти выражения, сворачивая свой собственный синтаксический код. Вы должны поддерживать стек ранее проанализированных и оцененных подвыражений, а затем повторно или выставлять верхние два элемента из стека и объединять их (если вы читаете другой оператор) или толкать что-то в стек (если вы читаете число).
Есть несколько способов реализовать этот стек. У вас может быть стек, представляющий собой явную структуру данных стека, где вы просматриваете входные данные слева направо, а затем нажимаете и добавляете по мере необходимости. Это ближе всего к тому, как работает парсер LR (1), поскольку вы будете думать о смене (нажатии) и уменьшении (выскакивании). Вы можете альтернативно использовать рекурсивный алгоритм и иметь стек вызовов вместо явного стека, который ближе по духу к тому, как работает парсинг LL (1).
Анализ как LL (1), так и LR (1) в этом случае, если вы просто заботитесь о необработанных характеристиках, кажется полным перегибом. Они предназначены для обработки больших классов общих грамматик, а накладные расходы из таблиц, вероятно, будут потреблять вашу производительность. Я просто напишу код двумя разными способами (явный стек/снизу вверх против неявного стека/сверху вниз) и посмотрим, какая из двух на самом деле заканчивается быстрее.
Спасибо. Это педаль для металла, где критическая латентность критическая. Моя интуиция говорит, что LL лучше для префикса, а LR лучше для постфикса. Но, как вы полагаете, я напишу и тесты, и тесты. Фактически, я, вероятно, проверю все четыре случая: LL/pre, LL/post, LR/pre, LR/post и test. – Olsonist
На самом деле, стеки вызовов имеют явную поддержку HW на современных x86. Это дает преимущество рекурсивно-приличному над столом, который я не думал. – Olsonist
Эта статья, LL and LR Parsing Demystified, поддерживает свою интуицию:
польский и Reverse Polish обозначения непосредственно соответствуют, на мой взгляд, LL и LR разборе соответственно.
Добро пожаловать в Переполнение стека! Я отредактировал ваш вопрос, насколько я мог догадаться о вашей проблеме. Однако добавьте больше описания, чтобы увидеть больше людей со знанием предмета. P Удачи! – manetsus
Даже если у вас есть двоичный формат, вам все равно придется идентифицировать токены (например, извлекать четырехбайтовое целое число - в порядке байтов или байтов в байтах), в зависимости от вашего протокола - от входного потока), который является моральным эквивалентом лексического анализа. И в большинстве случаев это все равно будет занимать больше циклов, чем относительно тривиальная стоимость связывания токенов с синтаксическими формами («синтаксический анализ»). – rici