Когда их представляют вниманию учеников,
про них говорят, что эти утилиты реализуют разные формализмы.

lex — это регулярные автоматы
yacc — это КС-грамматики

но на самом деле всё не так.

Можно обойтись без lex, если токены будут соответствовать буквам.
Но тогда в грамматике придётся писать правила для учёта пробельных символов,
и грамматика станет более "зашумлённой".

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

Я бы хотел найти какие-нибудь тексты, посвящённые
формальному описанию такого разделения. Ведь
кроме пробелов ещё существуют препроцессоры, обработчики триграфов, esc-последовательностей и комментариев.

Неужели никто этого не описывал при помощи "научного подхода"?

Здравствуйте, Эйнсток Файр, Вы писали:

ЭФ>Можно обойтись без lex, если токены будут соответствовать буквам.
ЭФ>Но тогда в грамматике придётся писать правила для учёта пробельных символов,
ЭФ>и грамматика станет более "зашумлённой".

Может это в тему. В Boost.Spirit когда-то не было лексера, и всё сразу парсером делали, когда появился, объяснили, зачем.

AG>объяснили, зачем.

У них в первом же предложении:

strings called tokens, separated by whitespace

но это не бросается в глаза.
Дальше они уводят дискуссию в сторону, призывая
—

the "Chomsky Hierarchy"

—

the need for backtracking

Всё как обычно. Просто эталонный образец информационной пропаганды для сокрытия заговора.

Они не дают способа формального описания разделения двух грамматик.
Что если нижная грамматика — это грамматика препроцессора? С директивами #include ?

Или ладно, include можно ещё обработать регулярными выражениями, если не считать его
ключевым словом, отделённым от # пробелами.
А вот уже́ с вложенными директивами ifdef endif так не получится, там
потребуется вторая контекстно-свободная грамматика.

И тогда получается, что есть два уровня парсинга, которые оба описываются КС-грамматиками. Это значит что аргумент про "chomsky hierarchy" — фуфло.

Аргумент про бэктрекинг вообще смешон. Потому что он может быть не нужен если использовать КС-парсеры без необходимости бэктрекинга.

Главная причина — именно в пробелах.

Но препроцессор и компилятор — не единственная пара КС-языков в одном исходнике.
Может быть например Embedded SQL — это третья КС-грамматика внутри.

Или, например, финальный язык простой и описывается ДКА, но ему нужен препроцессор с вложенными if-ами.
Тогда получается что нужно склеить выход yacc со входом lex. Но такой возможности нет,
потому что нет единого фреймворка.
Практический пример — синтаксис файлов конфигурации Apache. Директивы самому апачу там простые,
а вот описание объектов, к которым директивы применяются, рекурсивное (директории).
Мог бы быть пример склеивания lex с lex (не могу пока придумать, но
в принципе-то это возможно, например конфиги типа как у systemd + препроцессор с include)

И вот неужели никто не попробовал описать единый подход к комбинированию и разделению таких грамматик?
Имея три разных грамматики, как их скомбинировать в одну?
А имея одну, как разделить на несколько?
Чтобы таким образом, например, реализовать поддежку template-ов.
Как при разделении грамматики разделяются описания действий (semantic actions)?
Как использовать разделение грамматик для избежания дублирования при описании
последовательных версий языка с наращиванем фич от версии к версии?

Здравствуйте, Эйнсток Файр, Вы писали:

ЭФ>Можно обойтись без lex, если токены будут соответствовать буквам.
ЭФ>Но тогда в грамматике придётся писать правила для учёта пробельных символов,
ЭФ>и грамматика станет более "зашумлённой".

А зачем тогда пробелы вообще нужны?

ЭФ>И вот неужели никто не попробовал описать единый подход к комбинированию и разделению таких грамматик?
ЭФ>Имея три разных грамматики, как их скомбинировать в одну?
VladD2 с бригадой в проекте Nitra

Автор(ы):

именно это и сделали

Автор(ы):

.

Здравствуйте, Эйнсток Файр, Вы писали:

ЭФ>Вот это и есть настоящая подлинная цель разделения процесса парсинга на два этапа.
ЭФ>Разделение на два этапа нужно для того, чтобы
ЭФ>скрыть механизм удаления пробелов во второй грамматике.

Нет, просто упростить написание с устранением необходимости рисовать грамматику и сложные контекстные реакции там, где достаточно регэкспа.

Вот, например, тебе надо распарсить плавучую константу. Поступает на вход какое-нибудь 9.066e-11. Ты будешь писать на yacc/аналоге правило типа целое — точка — ещё целое всегда без знака — 'e' — ещё целое?
А потом сохранять их по отдельности и комбинировать?
С лексическим уровнем такие вещи очень радикально упрощаются, и именно в этом смысл.

А то, что в теме парсинга теория очень условно соответствует практике, и там, где она начинает реально соответствовать, возникают суперпрорывы типа ANTLR — известно ещё с 70-х. Но теория всё равно нужна, хотя бы в самом базовом уровне.

ЭФ>Я бы хотел найти какие-нибудь тексты, посвящённые
ЭФ>формальному описанию такого разделения. Ведь
ЭФ>кроме пробелов ещё существуют препроцессоры, обработчики триграфов, esc-последовательностей и комментариев.
ЭФ>Неужели никто этого не описывал при помощи "научного подхода"?

Ты ещё спроси про научное обоснование парсинга C++

_> именно это

нет, они сделали другое.

Безлексерный парсер – позволяет легко разбирать языки с несколькими лексическими контекстами, такие как XML.

У меня ключевое не в том, что парсер безлексерный, а в декомпозиции грамматики. А парсер вполне может быть и комбинированным, многостадийным.

Здравствуйте, Эйнсток Файр, Вы писали:

ЭФ>И вот неужели никто не попробовал описать единый подход к комбинированию и разделению таких грамматик?
ЭФ>Имея три разных грамматики, как их скомбинировать в одну?
ЭФ>А имея одну, как разделить на несколько?
ЭФ>Чтобы таким образом, например, реализовать поддежку template-ов.
ЭФ>Как при разделении грамматики разделяются описания действий (semantic actions)?
ЭФ>Как использовать разделение грамматик для избежания дублирования при описании
ЭФ>последовательных версий языка с наращиванем фич от версии к версии?

Syntax Definition Formalism

YV>Syntax Definition Formalism

И чем оно от Нитры отличается, со своими scannerless парсерами ?

Здравствуйте, netch80, Вы писали:

N>суперпрорывы типа ANTLR
Разве это прорыв?

Здравствуйте, Эйнсток Файр, Вы писали:

ЭФ>но на самом деле всё не так.
да, на самом деле всё не так.

ЭФ>lex — это регулярные автоматы
ЭФ>yacc — это КС-грамматики

(1) Шо то грамматика, шо это грамматика. Вот это обе грамматики такие, шо я ... (и далее по определению)

ЭФ>Можно обойтись без lex, если токены будут соответствовать буквам.
Из (1) очевидно и тривиально следует: можно обойтись

ЭФ>Но тогда в грамматике придётся писать правила для учёта пробельных символов,
(2) Нет не для учета пробелов, а для разбора токенов. Подсказка: пробел это тоже токен.
ЭФ>и грамматика станет более "зашумлённой".
Из (2) очевидно и тривиально следует: станет более "зашумлённой"

ЭФ>Вот это и есть настоящая подлинная цель разделения процесса парсинга на два этапа.
Нет Подлинная цель — абстрагирование.

ЭФ>Разделение на два этапа нужно для того, чтобы
ЭФ>скрыть механизм удаления пробелов во второй грамматике.
Очевидно, проход по тексту лексером делается для нарезки входа на токены, а не для удаления пробелов.

ЭФ>У меня ключевое не в том, что парсер безлексерный, а в декомпозиции грамматики. А парсер вполне может быть и комбинированным, многостадийным.
Не знаю почему ты сагрился на пункт 3, но это следствие решения задач модульности и декомпозиции. Возможны такие грамматики, которые лексер не потянет просто потому что невозможно на стадии лексера в принципе определить на какие токены разбирать то что дальше. Гипотетичски:
Regex r = "\d+"; — идеальный модульный парсер должен по типу переменной r понять что "\d+" это не просто строка, а язык регулярных выражений, и красиво его разбить на элементы именно регекспа и раскрасить. С многостадийной фигнёй это невозможно.

Там в описании Nitra пункт "модульность", это про декомпозиции. Собственно в примере "калькулятор" "using Whitespaces;" как раз пример модульности. В документации ещё есть пункт "Поддержка неоднозначных грамматик (когда две ветви спарсили одинаковый набор токенов)." и "Пример расширения правила из импортируемого синтаксического модуля".

W> Подлинная цель — абстрагирование.

абстрагирование это побочный эффект. Если присмотреться к таблицам yacc, то там символы являются токенами, а ключевые слова превращаются в токены и добавляются в конец этой же таблицы. Не было бы ключевых слов (которые указываются в директиве %token (она же %term) ), yacc всё равно бы смог работать.

Здравствуйте, Wolverrum, Вы писали:

N>>суперпрорывы типа ANTLR
W>Разве это прорыв?

На фоне общего болота, где при любой минимальной проблеме переходят на рукопашные парсеры — да, прорыв.

_> это следствие решения задач модульности и декомпозиции

это следствие неправильного решения задач модульности и декомпозиции

_> С многостадийной фигнёй это невозможно.

спорное утверждение

Здравствуйте, Эйнсток Файр, Вы писали:

ЭФ>Когда их представляют вниманию учеников,
ЭФ>про них говорят, что эти утилиты реализуют разные формализмы.

ЭФ>lex — это регулярные автоматы
ЭФ>yacc — это КС-грамматики

Кто-то еще использует их?

ЭФ>> lex — это регулярные автоматы
ЭФ>> yacc — это КС-грамматики

AJD> Кто-то еще использует их?

Я абстрактно рассуждаю. Для C# есть gplex+gppg, там всё то же самое.

Здравствуйте, Эйнсток Файр, Вы писали:

ЭФ>Я бы хотел найти какие-нибудь тексты, посвящённые
ЭФ>формальному описанию такого разделения. Ведь
ЭФ>кроме пробелов ещё существуют препроцессоры, обработчики триграфов, esc-последовательностей и комментариев.

Сам же написал, lex — это регулярные автоматы.

Разбивка на токены описывается регулярным языком. Более сложный парсинг (например там, где появляется скобки) не описывается.

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

Кстати, по-моему опыту, написать парсер с нуля что на yacc'е, что руками, требует сравнимых усилий. Но если парсер написан на yacc'е, гораздо проще вносить небольшие изменения в грамматику. Но зато от парсера на yacc'е очень трудно добиться вменяемой реакции на синтаксические ошибки в разбираемом тексте.

Здравствуйте, AndrewJD, Вы писали:

ЭФ>>lex — это регулярные автоматы
ЭФ>>yacc — это КС-грамматики
AJD>Кто-то еще использует их?

netch@m2:/usr/src>>
$ find . -name '*.y' | fgrep -v /byacc/ | wc -l
      90
netch@m2:/usr/src>>
$ uname -r
11.3-RELEASE-p9

Среди заметных потребителей, например, Intel ACPICA.

Здравствуйте, Эйнсток Файр, Вы писали:

ЭФ>Неужели никто этого не описывал при помощи "научного подхода"?

Самую большую работу сделал Ноел Хомский, который говорил о грамматике как о способе формального описания и построения семантической модели.

Такая вещь как lex может вызывать вопросы, но только пока вы не повертите ситуацию в разных измерениях. Я помогу вам в ваших измышлениях, дав развернутую ретроспективу.

Вот смотрите. lex — это примитивный токенизатор. Он преобразовывает поток символов в токены. На входе поток (последовательность) символов, на выходе — тоже поток, но уже токенов. Токен — это набор символов, представляющий интерес. Например, в натуральных языках токенами являются слова и разделители слов, такие как пробелы и знаки пунктуации.

Токенизатор не делает никаких попыток интерпретации данных. Все что он делает — это свертку входного потока символов в выходной поток токенов. Иногда токенизатор делает примитивную валидацию, если налагается некоторый синтаксический формализм.

Например:

вот       такое   предложение.

Если отложить стилистику в сторону, то его семантическая суть: вот такое предложение. С точки зрения смысловой семантики, эти два предложения равнозначны. Токенизатор позволяет грамматике заниматься исключительно семантикой, а не низкоуровневной задачей вылавливания слов в потоке символов. Таким образом, достигается более естественное разделения обязанностей, что несколько упрощает понимание системы. Это просто проще для мозга человека. Но это также чище с точки зрения символьной алгебры.

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

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

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

Если говорить об общем научном подходе, то это называется функциональной композицией. Она повсеместна. Например, в тригонометрии есть набор таких примитивов как cos(x), sin(x) и т.д. Композируя их в одну функцию (формулу), вы получаете нужный результат. Все ограничено всего лишь вашей фантазией, глубиной абстракции и хитростью, которая позволяет получать нужный результат эффективно в заданный условиях. Казалось бы, мы все проходили это еще в школе, но мозг врозслого человека настолько засорен, что мы забываем применять эту простую и звучную конструкцию которая присутствует повсеместно.

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

Во всех языковых трансляторах есть нечто подобное. Например, в XML это SAX (поток) и DOM (Document Object Model, она же семантическая модель). DOM строится поверх SAX, так же как и формальная грамматика строится поверх токенизатора.