Вроде классически для разбора таких текстов как Markdown применяют типа конечный автомат:
Скрытый текст
TextSpan markdown2TextSpan(String markdownText) {
final spans = <TextSpan>[];
final buffer = StringBuffer();
int asteriskCount = 0;
bool isItalic = false;
bool isBold = false;
for (int i = 0; i < markdownText.length; i++) {
final char = markdownText[i];
if ("*" == char) {
if (asteriskCount < 2) {
asteriskCount++;
continue;
}
buffer.write(char);
continue;
}
if (asteriskCount > 0) {
if (buffer.isNotEmpty) {
spans.add(_buildTextSpan(buffer.toString(), isItalic, isBold));
}
if (1 == asteriskCount) isItalic = !isItalic;
if (2 == asteriskCount) isBold = !isBold;
buffer.clear();
asteriskCount = 0;
}
buffer.write(char);
}
if (buffer.isNotEmpty) {
spans.add(_buildTextSpan(buffer.toString(), isItalic, isBold));
}
return TextSpan(children: spans);
}
Но это не точно, голова сейчас не работает — могут быть ошибки тут.
Дал задание GPT — он сначала решил с помощью хитровумных регулярных выражений. Минус такого подхода — регулярки сложно поддерживать, если будут добавляться новые теги. В таком алгоритме как у меня все намного проще.
Попросил без регулярных выражений — он начал как бы заглядывать вперед, делать i+1 и т.д. Т.е. не понял как сделать проще. Когда попросил без i+1 — то он такого наворотил, раз в 5 больше кода и ошибку там найти стало не реально.
Вопрос у меня такой — где-то описан этот алгоритм парсинга? Узнаете ли вы его?
Здравствуйте, пффф, Вы писали:
П>Маркдаун — это не только и не столько звёздочки
Что мешает линейно добавлять другие управляющие символы?
S>>Вопрос у меня такой — где-то описан этот алгоритм парсинга? Узнаете ли вы его? П>Диалектов маркдауна и парсеров его — кучи
Да вопрос не в этом же...
=сначала спроси у GPT=
Re: Про канонический алгоритм парсинга Markdown и подобного
Здравствуйте, Shmj, Вы писали:
S>Вроде классически для разбора таких текстов как Markdown применяют типа конечный автомат:
Это ты у Marty спроси. Он большой специалист по маркдауну.
S>Дал задание GPT — он сначала решил с помощью хитровумных регулярных выражений. Минус такого подхода — регулярки сложно поддерживать, если будут добавляться новые теги. В таком алгоритме как у меня все намного проще.
GPT твой — он делает, "как все". Потому, что его учили на всехних текстах. А все теперь зачем-то любят регулярки, толком их не понимая.
Хорошая иллюстрация к вопросу, заменит ли GPT живых человеческих разработчиков.
Re: Про канонический алгоритм парсинга Markdown и подобного
Здравствуйте, Shmj, Вы писали:
S>Вроде классически для разбора таких текстов как Markdown применяют типа конечный автомат: S>Вопрос у меня такой — где-то описан этот алгоритм парсинга? Узнаете ли вы его?
Автомат лексического разбора. Без заглядывания вперёд там будут откладывания решений назад.
Типа, встретилась звёздочка — переходим в состояние "то ли это первый символ лексемы две звёздочки, то ли три звёздочки, то ли одинокая звёздочка в тексте". Ну и так далее.
А уже потом будешь синтаксическим разборщиком смотреть, что две звёздочки в начале соответствуют двум звёздочкам в конце жирного блока, или же это непарная и потому относящаяся просто к тексту.
Или что там можно мешать скобки как угодно: plain ** bold * bold italic ** italic * plain...
На регекспах сделать читаемый и универсальный код лексера, в принципе, не так уж и сложно.
Выписать все специальные строчки разметки,
— сделать группу с вариантами (\*\*|\*|etc) — далее назову этот паттерн MARKUP, — естественно, надо более длинные разметки поместить впереди более коротких, чтобы жадный алгоритм выгребал их полностью
— сделать группу простого текста с негативным забеганием, (. (?! MARKUP))+ — далее назову этот паттерн PLAINTEXT
— и объединить их, и дать группам имена ((?<markup> MARKUP) | (?<plaintext> PLAINTEXT))*
Всё, вы великолепны! И пусть у движка регекспа голова болит, как из этого недетерминированного автомата сделать детерминированный.
Негативное забегание всё ещё остаётся в регулярной грамматике. Вот заглядывание назад — это уже контекстно-зависимая грамматика.
Кажется, писать такое руками для чего-то более сложного, чем одна и две звёздочки, на голом C/C++/C#/что там больше нравится — это порнография.
Я не знаток, на каких библиотеках сейчас парсеры пишут. В конце концов, старая добрая кодогенерация lex+bison...
Перекуём баги на фичи!
Re[2]: Про канонический алгоритм парсинга Markdown и подобного
Здравствуйте, Pzz, Вы писали:
S>>Вроде классически для разбора таких текстов как Markdown применяют типа конечный автомат:
Pzz>Это ты у Marty спроси. Он большой специалист по маркдауну.
Да ну, какой я специалист... Так, решил запилить небольшую нашлёпку поверх маркдауна, а сам маркдаун я не разбираю пока, хотя это в планах тоже есть
Здравствуйте, Shmj, Вы писали:
S>Вроде классически для разбора таких текстов как Markdown применяют типа конечный автомат:
Кодт выше всё неплохо расписал, в общем.
Если писать автомат (что Кодт назвал порнографией, но лично я бы так и сделал), то писать его именно так, как написал Кодт, а не так, как у тебя. У тебя уже какая-то копрофилия.
Например:
enum State
{
stInitial
stWaitSecondAsterisc,
stWaitSecondUndersore,
stWaitSecondbacktick,
stWaitThirdbacktick,
//...
};
void handleChar(char ch, State &st)
{
switch(st)
{
case stInitial:
// Или тут тоже switchif (ch=='*')
st = stWaitSecondAsterisc;
else if (ch=='_')
st = stWaitSecondUndersore;
else if (ch=='`')
st = stWaitSecondbacktick;
else
{} // Процессим тут остальноеbreak;
case stWaitSecondAsterisc:
if (ch=='*')
{
// тут выплевываем двойной астерикс
st = stInitial;
}
else
{} // Процессим тут остальноеbreak;
case stWaitSecondUndersore:
if (ch=='_')
{
// тут выплевываем двойной андерскор
st = stInitial;
}
else
{} // Процессим тут остальноеbreak;
case stWaitSecondbacktick:
if (ch=='`')
st = stWaitThirdbacktick;
else
{} // Процессим тут остальноеbreak;
case stWaitThirdbacktick:
if (ch=='`')
{
// тут выплевываем тройной бэктик
st = stInitial;
}
else
{} // Процессим тут остальноеbreak;
// ...
}
}
Я бы разбил на две фазы — сначала "токенизируем" в токены, потом делаем второй автомат синтаксического анализатора.
Это классические фазы парсинга — сначала лексер (токенизер), потом семантический анализатор на выхлопе лексера.
Это можно сделать и разными инструментами. Я в своё время пробовал flex/bison для своего первого парсера плюсиков, который 0x03ие плюсики раскрашивал в HTML, но оно очень неудобно. Потом ещё рагель пытался юзать, но он тоже не удобен. Для рагеля я в своё время нашел тулзу в сорцах ABNFGEN, и подпиливал её под себя, это было поудобнее, но тоже хрень неудобная получилась, когда попытался что-то посложнее сделать. Сейчас, говорят, ANTLR массово используется. Я пробовал осилить теорию формальных грамматик, или как оно там, книгу дракона прочитал, но там об этом не особо было, потом ещё пару каких-то учебников вузовских, но все эти LL(N)/LR(N) как-то не раскурил. Кстати, если кто что посоветует на эту тему для совсем тупых, буду признателен.
Ещё можно врукопашку рекурсивным спуском налабать. Я такое делал по мотивам книжки Герберта Шилдта по сишечке (она у меня была ещё в распечатке на матричном принтере) — тут в принципе, всё просто, но писать долго и скучно. И если грамматика меняется (или, даже, просто приоритет операторов), дофига переписывать. Тут Sinclair про PEG расказывает, как я понял, оно само на основе правил генерит разбор рекурсивным спуском, и вроде даже удобно, но хз, есть ли для плюсов.
Мне больше нравится разбить поток символов на токены/лексемы, и потом творить с ними любую дичь — так, я как-то делал одну штуку, и уж не помню зачем, но мне захотелось поменять приоритеты операторов, сделать не так, как в плюсах. Я вроде что-то для асма специфического делал, и там вроде было с приоритетами по-другому. Я тогда написал парсер потока токенов, который строит дерево выражения с учетом передаваемой ему таблицы приоритетов операторов, и поменять приоритеты можно было хоть на лету — грубо говоря, в языке заводим директиву $asm_pri — выражения считаются по асмовским правилам, или $cpp_pri — выражения считаются по правилам плюсов. Мне это понравилось. Прикольно и гибко, хотя, конечно, хз зачем нужно, но такого с инструментариями автоматической генерации достичь очень сложно, если вообще возможно
Я же пришел в итоге к тому, что обе фазы в рукопашку делаю — задалбывает сначала долго разбираться со всеми этими инструментами, а потом ещё дольше воевать с их недостатками, которые всегда вылезают в тот самый момент, когда ты придумал новую фичу для своего языка, но она категорически не хочет укладываться в возможности инструмента.
В принципе, маркдаун почти везде парсят на регулярках — но в плюсах их долго не было, а тащить сторонние PCRE мне всегда было лень, а сейчас регулярки вроде уже есть в плюсах, но тормозные, да и привык уже без них как-то.
S>Дал задание GPT — он сначала решил с помощью хитровумных регулярных выражений. Минус такого подхода — регулярки сложно поддерживать, если будут добавляться новые теги. В таком алгоритме как у меня все намного проще.
Минус такого подхода — GPT тебе правдоподобной херни нальёт полную панамкутележку, сиди потом, разбирайся, чего он там накосячил.
S>Вопрос у меня такой — где-то описан этот алгоритм парсинга? Узнаете ли вы его?
Что значит — узнаете ли вы его?
Универсального алгоритма парсинга маркдауна нет.
Базовая спека по маркдауну — это CommonMark specification of Markdown.
Там же где-то ищи и Markdown.pl. Там как раз будут регулярки — на перле по другому никак ничего не сделать. ТОлько там перловый диалект регулярок, надо будет переводить в твой.
Ещё есть у нас Github Flavored Markdown — вроде вполне совместим с CommonMark, но добавляет некоторые расширения. GFM вполне совместим с тем, что юзается в GitLab, и также вполне совместим (кроме нескольких нюансов) с тем маркдауном, который поддерживает доксиген.
Как я понял, Github изначально был написал на Руби (на рельсах, наверное), и оттого там для рендеринга маркдауна используется написанный на Руби движок Jekyll, к нему только нужно доустановить пакет для GFM. Там, скорее всего, тоже регулярки, можно выдрать оттуда, только там, скорее всего, тоже свой диалект регулярок.
А какого-то каноничного парсера маркдауна нет и не будет. Каждая реализация в мелочах несовместима с другими.
Здравствуйте, Marty, Вы писали:
M>Что "это"? Мой набросок? Нет, не будет. Он вообще работать не будет, он про иллюстрацию, как бы я делал автомат. А как ты сделаешь, я не знаю
Я имею в виду саму идею — у вас состояние одномерное — enum, который может иметь только одно значение. Если я правильно понял, то такое уже не получится:
Здравствуйте, Shmj, Вы писали:
M>>Что "это"? Мой набросок? Нет, не будет. Он вообще работать не будет, он про иллюстрацию, как бы я делал автомат. А как ты сделаешь, я не знаю
S>Я имею в виду саму идею — у вас состояние одномерное — enum, который может иметь только одно значение. Если я правильно понял, то такое уже не получится:
S>
Получится. Внимательнее посмотри. У меня есть отдельные состояния для одной звездочки, двух звёздочек, и тп. Само собой, что надо вовремя выплёвывать накопленное в лексере дальше в парсер.
S>а в моем варианте — работает. Причем 3 строчки кода без сложной логики и регулярок.
У тебя состояние размазано, отдельно текущий символ, отдельно — количество его повторений. У меня это отражено в enum. Но код у тебя в любом случае говно. Если уж не хочется плодить много состояний, то можно так:
class MdLexer
{
char tokenChar = 0;
std::size_t charCnt = 0;
static bool isSpecialChar(char ch)
{
return ch=='\'' || ch=='*' || ch=='_' || ch=='`' || ch=='\"' || ch=='#'; // Можно отдельным параметром шаблона сделать, как Traits
}
public:
template<typename TokenHandler>
void operator()(char ch, const TokenHandler &tokenHandler)
{
// по нулевому символу - финализируем, сбрасываем кешированное, если было
// Финализировать можно без проблем много раз, финализация просто сбрасывает текущее состояние в парсер
// Если входной поток символов какой-то из говна, и там могут быть нулевые символы, и это не было проверено на входе
// то ничего тут не сломаетсяif (ch==0)
{
if (tokenChar!=0)
tokenHandler(tokenChar, charCnt, true);
// Нулевой символ не прокидываем, зачем парсеру геммор перекидывать?return;
}
if (tokenChar==ch)
{
// повторение символа
++charCnt;
return;
}
// Какой-то другой символ пришел, не тот, что мы коллекционируем.
// Сбросили в парсер то, что было накоплено, если былоif (tokenChar!=0)
tokenHandler(tokenChar, charCnt, true);
// Обнуляем накопления
tokenChar = 0;
charCnt = 0;
if (!isSpecialChar(ch))
{
tokenHandler(ch, 1, false); // прокинули просто символreturn;
}
// Стартуем накопление спец символов
tokenChar = ch;
charCnt = 1; // Один символ таки накопили сразу при его поступлении
}
}; // class MdLexertemplate<typename TokenHandler, typename MarkdownCharsContainer>
void parseMarkdown(const MarkdownCharsContainer &mdc, const TokenHandler &tokenHandler)
{
MdLexer lexer;
for(auto ch: mdc)
lexer(ch, tokenHandler);
lexer(0, tokenHandler); // Финализируем
}
В принципе, то же самое, что и у тебя, только гораздо более универсальное.
Только не забывай, что у тебя есть зависимость от контекста. Так, три бэктика, если они с новой строки (и впереди только опционально пробелы) — то это режим листинга, и там отключается разбор маркдауна, но включается режим подсветки синтаксиса (язык указывается сразу после бэктиков).
Это можно добавить в мой лексер выше, а можно учитывать в парсере. Я бы пошел по второму варианту. Потому что токенизация во входном потоке ничего не меняет, просто иногда группирует одинаковые символы, и их при желании в зависимости от режима так же легко разгруппировать. В более сложных случаях, как, например, разбор плюсового кода и парсинг шаблонов с угловыми скобками, и с угловыми повторяющимися скобками — это лучше делать на уровне лексера, с обратной связью от парсера к лексеру — являются ли угловые скобки отдельными спец операторными символами, или это просто "больше", "меньше", или оператор сдвига.
Ну, и в спец символы, для простоты, можно также добавить пробелы, табы, и переводы строки, проще будет в парсере это обрабатывать.
ЗЫ Вообще, глядя на твой код, я понимаю, что все твои десятки тем и вопросов по программированию, а также данные тебе там ответы — это всё не пошло тебе на пользу
Здравствуйте, Marty, Вы писали:
M>Получится. Внимательнее посмотри. У меня есть отдельные состояния для одной звездочки, двух звёздочек, и тп. Само собой, что надо вовремя выплёвывать накопленное в лексере дальше в парсер.
А что если и звездочка и подчеркивание открыты — это какое состояние? Будете перемножать?
=сначала спроси у GPT=
Re[7]: Про канонический алгоритм парсинга Markdown и подобно
Здравствуйте, Shmj, Вы писали:
M>>Получится. Внимательнее посмотри. У меня есть отдельные состояния для одной звездочки, двух звёздочек, и тп. Само собой, что надо вовремя выплёвывать накопленное в лексере дальше в парсер.
S>А что если и звездочка и подчеркивание открыты — это какое состояние? Будете перемножать?
Ты идиот? Обработаю согласно правилам MD (которые, кстати, у разных диалектов MD работают по-разному)
Здравствуйте, Shmj, Вы писали:
S>Вроде классически для разбора таких текстов как Markdown применяют типа конечный автомат:
S>Но это не точно, голова сейчас не работает — могут быть ошибки тут.
S>Дал задание GPT — он сначала решил с помощью хитровумных регулярных выражений. Минус такого подхода — регулярки сложно поддерживать, если будут добавляться новые теги. В таком алгоритме как у меня все намного проще.
Первые попытки парсеров маркдауна у меня были примерно такие же, но потом постоянно всплывают "нюансы". Причём GPT мне сразу говорил — не парься, а возьми готовую библиотеку, благо их есть. В конечном итоге прислушался к его советам.
Re: Про канонический алгоритм парсинга Markdown и подобного
Здравствуйте, Shmj, Вы писали:
S>Вроде классически для разбора таких текстов как Markdown применяют типа конечный автомат:
Классически все формальные языки делят на три группы: контекстно-зависимые, контекстно-свободные, и регулярные.
Сложность разбора каждого из классов радикально различается.
Поскольку примерно все реальные формальные языки относятся к КЗ-классу, прямой разбор которого слишком тяжёл, классический разбор делается в три этапа:
1. Токенизация (лексический анализ). Строим промежуточный "язык", который является регулярным. Разбирается конечным автоматом. На входе — поток символов, на выходе — поток лексем (токенов).
2. Парсинг (синтаксический анализ). Строим промежуточный "язык", который является контекстно-свободным. Разбирается конечным автоматом с магазинной памятью. На входе — поток лексем, на выходе — дерево разбора.
3. Семантический анализ. Проверяем, что то, что получилось на предыдущем этапе, соответствует некоторой программе на реальном КЗ-языке. Делается при помощи рукопашных правил. Классически — как цепочка трансформаций дерева и построений таблиц символов. Общего решения нет, пилят кто во что горазд. Кто-то подпиливает язык для того, чтобы семантический анализ был однопроходным (и тогда его вообще можно объединить с предыдущей фазой). Кто-то делает N-проходный анализ с фиксированным N, кто-то делает динамические алгоритмы, которые иногда даже могут свалиться в экспоненциально-сложные вычисления, но в среднем работают полиномиально.
Из недавних достижений в этой области — популяризация безлексерных парсеров. Во времена оны вторая фаза была дорогой в реализации, поэтому никому не хотелось выпиливать какой-нибудь LL(k) парсер со встроенным разбором идентификаторов/комментариев/строковых констант. Возможность применить DFA для токенизации и быстро обнаружить лексические ошибки была настолько искушающей, что и по сю пору часть народа не представляет себе других вариантов.
Оборотной стороной этого подхода являются дурацкие ограничения — вроде отсутствия поддержки вложенных комментов в более-менее всех C-подобных языках. Аналогичные сложности возникают примерно везде, где "токен" начинает иметь мало-мальски сложную структуру, типа интерполированных строк.
В общем, современное состояние желаний и возможностей устроено так, что удобнее применять генераторы безлексерных парсеров, способных строить эффективные магазинные автоматы для любых КС-языков, без необходимости вручную пилить последние на "регулярную" и "магазинную" части.
Вторая популярная проблема — ident-based parsing. Эта штука плохо работает с традиционными КС-парсерами, потому что является частным случаем КЗ. Известные мне решения — либо полностью ручной разбор, либо переход к МП-лексеру, который умеет вставлять в стрим токены ident/dedent.
С точки зрения этого подхода то, что вы пытаетесь сделать — это совместить "генерированный" токенизатор на основе регулярок с "рукопашным" КС-парсером.
Теоретически, вы можете даже достичь успеха на этом поприще. Особенно, если будете понимать, что именно вы делаете. Вы не один такой — в частности, VS Code (и многие другие языки) применяет для раскраски синтаксиса TextMate2. Это как раз язык, в котором токенизация делается регекспами, а разбор — рекурсивными правилами в КС-стиле.
На практике — я бы взял какой-нибудь взрослый генератор парсеров и построил решение сразу на нём. Если, конечно, есть нетерпимость к коробочным реализациям парсеров маркдауна, коих, АФАИК, завезено с избытком.
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
S>>Дал задание GPT — он сначала решил с помощью хитровумных регулярных выражений. Минус такого подхода — регулярки сложно поддерживать, если будут добавляться новые теги. В таком алгоритме как у меня все намного проще.
Pzz>GPT твой — он делает, "как все". Потому, что его учили на всехних текстах. А все теперь зачем-то любят регулярки, толком их не понимая.
Pzz>Хорошая иллюстрация к вопросу, заменит ли GPT живых человеческих разработчиков.
А, кстати, интересный вопрос — сейчас ИИ натаскан на примерах, созданных человеками. Само оно ничего не придумывает нового, только комбинирует старое, чем чаще в старом встречается какой-то вариант, тем чаще он предлагается как надежное проверенное решение.
Следующие поколения ИИ будут натаскиваться на текстах созданных текущими ИИ. И значит на еще более частом повторе всё техже вариантов.
Перекуём баги на фичи!
