@Zukaboo спасибо за очень важные замечания. А как вам такой

вариант?
______________
Очень часто разбор текста и построение из него дерева разбора (parse tree) удобно разбить на две фазы. В первой фазе используется близкая к регулярной, но не регулярная грамматика (грамматика, описываемая регулярными выражениями), во второй фазе - контекстно-свободная. Это разбиение, в принципе, не обязательно, но крайне удобно и быстро.

В первой фазе текст пропускается через некоторую программу (*лексер*), которая читает текст программы посимвольно (UTF8 или ASCII символы), составляя из этих символов слова (так называемые tokens) используя регулярные выражения. Грамматика языка, разбираемого лексером отличается от регулярной тем, что в случае альтернативы выбирается не первый подходящий вариант, а тот, что даёт наиболее длинный префикс (жадный выбор). Важно, что получающееся дерево разбора *вырождено*, то есть, это просто список, и, таким образом, поток символов ASCII превращается в поток token'ов. С формальной точки зрения и то, и другое - _символы_, но разных языков.
_______________

То есть, подчёркиваем, что грамматика не регулярная, но близкая к ней. Отличается от регулярной тем, что выбор альтернатив жадный. Поскольку это всё равно разбор, пусть и экзотического неназванного класса грамматик, это парсер.

> Это разбиение, в принципе, не обязательно, но крайне удобно и быстро. Нет, это разбиение строго обязательно для разбора подавляющего большинства практически используемых ЯП с помощью CFG (и parser generators, особенно широко используемых LALR / LR), т.е. сделать это без него тупо невозможно. > составляя из этих символов слова (так называемые tokens) используя регулярные выражения. Нет, чаще всего lexer-ы используют не только регулярные выражения (в том числе в этом и суть их применения). Тут уже приводили примеры — мне кажется, или Вы их все проигнорировали? :( > Грамматика языка, разбираемого лексером По-моему, это вообще не разбор. Если открыть любой учебник по parsers (или формальной лингвистике), или даже погуглить определение этого понятия (и того, что такое recognition, вообще) — очевидно, что то, что делают lexers — это, в общем (практическом!) случае, не он: "Parsing is the process of structuring a linear representation in accordance with a given grammar." "The task of parsing is to reconstruct the derivation tree (or graph) for a given input string." "To parse a string according to a grammar means to reconstruct the production tree (or trees) that indicate how the given string can be produced from the given grammar." "Parsing, syntax analysis, or syntactic analysis is the process of analyzing a string of symbols, either in natural language, computer languages or data structures, conforming to the rules of a formal grammar. " Обратите внимание, что во всех определениях есть строка символов, и parsing определяет, какое дерево (или деревья, или графы) разбора соответствуют ей целиком, понимаете? Т.е. даже грамматика языка, получаемого последовательными вызовами gettoken() для строки (до победного конца), хотя эта функция использует исключительно longest DFA matching — не регулярная! > Важно, что получающееся дерево разбора Там может вообще не получаться ни дерева разбора, ни потока или массива tokens, в практическом случае. Поступать так на практике для одного языка не принято... но про lexer hack (из C) все слышали, вроде? ;) А при language composition (т.е. например, "смешивании" C и SQL в один язык) с использованием lexers сами выделяемые tokens будут контекстно-зависимы, т.е. модель "поток/массив токенов" тут неприменима. > то есть, это просто список, и, таким образом, поток символов ASCII превращается в поток token'ов. Но это, в самом деле, распространённая "абстрактная" модель для [упрощения изложения темы] parsing. Только к практике она относится далеко не всегда. > Поскольку это всё равно разбор, пусть и экзотического неназванного класса грамматик, это парсер. Для некоторых случаев это "сойдёт", см. выше.

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

1. Спасибо за упоминание того, что учёт контекста в лексере позволяет убрать учёт контекста в парсере. Александр упоминал про контекстно-зависимые грамматики второй фазы, но я забыл это вставить. 2. Да, в лексерах используют не только регулярные выражения. Я сознательно замёл это под ковёр. Обычно это всё-таки делает малая доля правил. 3. > По-моему, это вообще не разбор. Список лексем - это тоже дерево, просто очень частный вид. Грамматика, упрощённая вот - регулярная + жадность. 4. > Там может вообще не получаться ни дерева разбора, ни потока или массива tokens, в практическом случае. Ну конкретно flex не может выдать ничего другого, кроме потока, на вход парсера.

Это, в общем случае, такая штука, которая для текущей (или заданной) позиции во входном потоке (почти всегда — потоке символов), и, возможно, внутреннего (хранимого) состояния и передаваемых ему parser-ом параметров возвращает очередной token.

> Обычно это всё-таки делает малая доля правил. "Обычно" Вы без этого почти ни один практический язык не разберёте. Т.е. Вы ребёнка под ковёр замели выплеснули вместе с водой. ;( > Список лексем - это тоже дерево, просто очень частный вид. Если он вообще есть. Покажете нам, как создать "список лексем" для типичного LALR-parser для C, не используя parser? > Ну конкретно flex не может выдать ничего другого, кроме потока, на вход парсера. Вы вообще не поняли, что я имел в виду. :( То, что выдаёт flex на вход parser, может зависеть (хоть целиком определяться!) теми параметрами, с которыми его вызывает parser, а не входным потоком символов, понимаете?

> т.е. сделать это без него тупо невозможно integer = digit | digit integer digit = '0' | … Не вижу невозможности.

Вопрос с жадностью остаётся открытым.

Этот вопрос появляется при лексинге, а не при разборе одной огромной грамматики.

Стикер

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

Стикер