Являются ли отдельные операции синтаксического анализа и лексинга хорошей практикой с комбинаторами синтаксического анализа?

18

Когда я начал использовать комбинаторы синтаксического анализа, моей первой реакцией было чувство освобождения от того, что казалось искусственным различием между синтаксическим анализом и лексингом. Внезапно все было просто разбор!

Однако недавно я наткнулся на эту публикацию на codereview.stackexchange, иллюстрирующую кого-то, кто вновь подтверждает это различие. Сначала я думал, что это было очень глупо с их стороны, но затем тот факт, что в Parsec существуют функции для поддержки такого поведения, заставляет меня задаться вопросом.

Каковы преимущества / недостатки синтаксического анализа уже лексированного потока в комбинаторах синтаксического анализа?

Эли Фрей
источник
Может кто-нибудь добавить тег [parser-combinator]?
Эли Фрей

Ответы:

15

Под синтаксическим анализом мы чаще всего понимаем анализ контекстно-свободных языков. Свободный от контекста язык более мощный, чем обычный, поэтому синтаксический анализатор может (чаще всего) выполнять работу лексического анализатора сразу.

Но это а) довольно неестественно б) часто неэффективно.

Для a), если я думаю о том, как, например, ifвыглядит выражение, я думаю, ЕСЛИ expr THEN expr ELSE expr, а не 'i' 'f', возможно, некоторые пробелы, тогда любой символ, с которого может начинаться выражение, и т. Д. идея.

Для б) существуют мощные инструменты, которые отлично справляются с распознаванием лексических сущностей, таких как идентификаторы, литералы, скобки всех видов и т. Д. Они выполнят свою работу практически в кратчайшие сроки и предоставят вам удобный интерфейс: список токенов. Больше не нужно пропускать пробелы в парсере, ваш парсер будет гораздо более абстрактным, когда он имеет дело с токенами, а не с символами.

В конце концов, если вы считаете, что парсер должен быть занят вещами низкого уровня, зачем вообще обрабатывать символы? Можно написать и на уровне битов! Видите ли, такой синтаксический анализатор, который работает на уровне битов, будет почти непостижимым. То же самое и с персонажами и жетонами.

Просто мои 2 цента.

Инго
источник
3
Просто ради точности: парсер всегда может выполнять работу лексического анализатора.
Джорджио
Кроме того, что касается эффективности: я не уверен, что парсер будет менее эффективным (медленнее). Я ожидаю, что полученная грамматика будет содержать подграмму, описывающую обычный язык, и код этой под грамматики будет таким же быстрым, как и соответствующий лексический анализатор. ИМО реальная точка зрения (а): насколько естественно, интуитивно работать с более простым, более абстрактным парсером.
Джорджио
@ Джорджио - По поводу вашего первого комментария: Вы правы. Здесь я имел в виду случаи, когда лексер прагматично выполняет некоторую работу, облегчающую грамматику, так что можно использовать LALR (1) вместо LALR (2).
Инго
2
Я удалил свое согласие с вашим ответом после дальнейших экспериментов и размышлений. Кажется, вы оба родом из мира Антлр и всех остальных. Учитывая первоклассную природу комбинаторов синтаксического анализа, я часто просто заканчиваю тем, что определяю синтаксический анализатор для моих анализаторов токенов, оставляя каждый токен как отдельное имя в слое синтаксического анализа. например, ваш пример if будет выглядеть так if = string "if" >> expr >> string "then" >> expr >> string "else" >> expr.
Эли Фрей
1
Производительность остается открытым вопросом, я сделаю несколько тестов.
Эли Фрей
8

Все, кто полагает, что разделение лексических операций и синтаксического анализа - это «хорошая практика» - я должен не согласиться - во многих случаях выполнение лексических операций и синтаксического анализа за один проход дает гораздо больше возможностей, и последствия для производительности не так плохи, как они представлены в другие ответы (см. Пакрат ).

Этот подход проявляется, когда нужно смешать несколько разных языков в одном потоке ввода. Это необходимо не только для странных, ориентированных на метапрограммирование языков, таких как Katahdin и тому подобное , но и для гораздо большего числа основных приложений, таких как грамотное программирование (смешивание латекса и, скажем, C ++), использование HTML в комментариях, вставка Javascript в HTML и скоро.

SK-логика
источник
В своем ответе я предположил, что это «хорошая практика в определенных контекстах», а не то, что это «лучшая практика во всех контекстах».
Джорджио
5

Лексический анализатор распознает обычный язык, а синтаксический анализатор распознает язык без контекста. Поскольку каждый обычный язык также не зависит от контекста (его можно определить с помощью так называемой линейно - правильной грамматики ), синтаксический анализатор также может распознавать обычный язык, и различие между синтаксическим анализатором и лексическим анализатором добавляет некоторую ненужную сложность: один контекст Свободная грамматика (парсер) может выполнять работу парсера и лексического анализатора.

С другой стороны, может быть полезно захватить некоторые элементы языка без контекста через обычный язык (и, следовательно, лексический анализатор), потому что

  1. Часто эти элементы появляются настолько часто, что с ними можно обращаться стандартным образом: распознавать числовые и строковые литералы, ключевые слова, идентификаторы, пропускать пробелы и т. Д.
  2. Определение обычного языка токенов делает полученную контекстно-свободную грамматику более простой, например, можно рассуждать с точки зрения идентификаторов, а не с точки зрения отдельных символов, или можно полностью игнорировать пробелы, если они не относятся к этому конкретному языку.

Таким образом, отделение синтаксического анализа от лексического анализа имеет то преимущество, что вы можете работать с более простой неконтекстной грамматикой и инкапсулировать некоторые базовые (часто рутинные) задачи в лексическом анализаторе (split et impera).

РЕДАКТИРОВАТЬ

Я не знаком с комбинаторами синтаксического анализа, поэтому я не уверен, как вышеуказанные соображения применимы в этом контексте. У меня сложилось впечатление, что даже если с комбинаторами синтаксического анализа есть только одна не зависящая от контекста грамматика, различие между двумя уровнями (лексический анализ / анализ) может помочь сделать эту грамматику более модульной. Как уже говорилось, нижний уровень лексического анализа может содержать базовые парсеры многократного использования для идентификаторов, литералов и так далее.

Джорджио
источник
2
Lexemes попадает в регулярные грамматики не естественно, а условно, так как все лексеры построены на движках регулярных выражений. Это ограничивает выразительную силу языков, которые вы можете создавать.
SK-logic
1
Можете ли вы привести пример языка, для которого было бы целесообразно определить лексемы, которые нельзя описать как обычный язык?
Джорджио
1
например, в нескольких языках, которые я специально создал для домена, идентификаторы могли бы быть выражениями TeX, которые упрощали бы красивую печать кода, например, такие выражения, как \alpha'_1 (K_0, \vec{T}), где \ alpha'_1, K_0 и \ vec {T} являются идентификаторами.
SK-logic
1
При наличии контекстно-свободной грамматики вы всегда можете взять нетерминальный N и трактовать слова, которые он может получить, как единицы, которые имеют полезное значение сами по себе (например, выражение, термин, число, утверждение). Это можно сделать независимо от того, как вы анализируете этот модуль (парсер, парсер + лексер и т. Д.). IMO выбор парсера + лексера - это скорее технический (как реализовать синтаксический анализ), чем семантический (в чем смысл блоков исходного кода, которые вы анализируете). Может быть, я что-то упускаю, но эти два аспекта мне кажутся ортогональными.
Джорджио
3
Итак, я согласен с вами: если вы определяете некоторые произвольные базовые строительные блоки ( лексемы ) и хотите использовать лексический анализатор для их распознавания, это не всегда возможно. Мне просто интересно, если это цель лексера. Насколько я понимаю, цель лексического анализатора - это скорее техническая задача: убрать некоторые утомительные детали реализации низкого уровня из анализатора.
Джорджио
3

Проще говоря, лексизм и синтаксический анализ должны быть разделены, потому что это разные сложности. Лексинг - это DFA (детерминированный конечный автомат), а синтаксический анализатор - это PDA (автомат с нажатием). Это означает, что синтаксический анализ по своей сути потребляет больше ресурсов, чем лексирование, и существуют специальные методы оптимизации, доступные только для DFA. Кроме того, написание конечного автомата гораздо менее сложно, и его легче автоматизировать.

Вы расточительны, используя алгоритм синтаксического анализа для lex.

DeadMG
источник
Если вы используете парсер для выполнения лексического анализа, КПК никогда не будет использовать стек, он в основном будет работать как DFA: просто потреблять ввод и переходить между состояниями. Я не уверен на 100%, но я думаю, что методы оптимизации (сокращение числа состояний), которые можно применить к DFA, также можно применить к КПК. Но да: легче написать лексический анализатор как таковой, не используя более мощный инструмент, а затем написать более простой синтаксический анализатор поверх него.
Джорджио
Кроме того, это делает все это более гибким и обслуживаемым. Например, предположим, что у нас есть синтаксический анализатор для языка Haskell без правила компоновки (т. Е. С точкой с запятой и фигурными скобками). Если у нас есть отдельный лексер, мы могли бы теперь добавить правила размещения, просто сделав еще один проход по токенам, добавив фигурные скобки и точки с запятой по мере необходимости. Или, для более простого примера: предположим, что мы начали с языка, поддерживающего символы ASCII только в идентификаторах, и теперь мы хотим поддерживать символы юникода в идентификаторах.
Инго
1
@ Инго, а зачем тебе это делать в отдельном лексере? Просто выделите эти терминалы.
SK-logic
1
@ SK-логика: я не уверен, что понимаю ваш вопрос. Почему отдельный лексер может быть хорошим выбором, я попытался обосновать в своем посте.
Инго
Джорджио, нет Стек является важнейшим компонентом обычного синтаксического анализатора стиля LALR. Выполнение лексических операций с помощью синтаксического анализатора - отвратительная трата памяти (как статической, так и динамически выделяемой), которая будет выполняться намного медленнее. Модель Lexer / Parser эффективна - используйте ее :)
riwalk
1

Одним из основных преимуществ отдельных parse / lex является промежуточное представление - поток токенов. Это может быть обработано различными способами, которые иначе были бы невозможны при комбинированном lex / parse.

Тем не менее, я обнаружил, что хорошее рекурсивное приличие может быть менее сложным и легче работать с обучением некоторому генератору синтаксического анализатора и необходимости выяснить, как выразить слабость грамматики в правилах генератора синтаксического анализатора.

Сильванаар
источник
Не могли бы вы объяснить больше о грамматиках, которые легче выразить в заранее подготовленном потоке, чем во время разбора? У меня есть только опыт реализации игрушечных языков и немногочисленных форматов данных, так что, возможно, я что-то упустил. Заметили ли вы какие-либо характеристики производительности между своими свернутыми вручную RD-парсерами / лекс-комбо и генераторами с питанием от BNF (я предполагаю)?
Эли Фрей