Информация об изменениях

Сообщение Re: Про канонический алгоритм парсинга Markdown и подобного от 13.01.2025 22:32

Изменено 13.01.2025 22:33 Marty

Старый текст
Новый текст
Разница

Re: Про канонический алгоритм парсинга Markdown и подобного

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

S>Вроде классически для разбора таких текстов как Markdown применяют типа конечный автомат:

Кодт ниже всё неплохо расписал, в общем.

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

Например:

enum State
{
  stInitial
  stWaitSecondAsterisc,
  stWaitSecondUndersore,
  stWaitSecondbacktick,
  stWaitThirdbacktick,
  //...

};

void handleChar(char ch, State &st)
{
  switch(st)
  {
    case stInitial:
        // Или тут тоже switch
        if (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 расказывает, как я понял, оно само на основе правил генерит разбор рекурсивным спуском, и вроде даже удобно, но хз, есть ли для плюсов.

Мне больше нравится разбить поток символов на токены/лексемы

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

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

S>Дал задание GPT — он сначала решил с помощью хитровумных регулярных выражений. Минус такого подхода — регулярки сложно поддерживать, если будут добавляться новые теги. В таком алгоритме как у меня все намного проще.

Минус такого подхода — GPT тебе правдоподобной херни нальёт полную ~~панамку~~тележку, сиди потом, разбирайся, чего он там накосячил.

S>Вопрос у меня такой — где-то описан этот алгоритм парсинга? Узнаете ли вы его?

Что значит — узнаете ли вы его?

Универсального алгоритма парсинга маркдауна нет.

Базовая спека по маркдауну — это CommonMark specification of Markdown.
Там же где-то ищи и Markdown.pl. Там как раз будут регулярки — на перле по другому никак ничего не сделать. ТОлько там перловый диалект регулярок, надо будет переводить в твой.

Ещё есть у нас Github Flavored Markdown — вроде вполне совместим с CommonMark, но добавляет некоторые расширения. GFM вполне совместим с тем, что юзается в GitLab, и также вполне совместим (кроме нескольких нюансов) с тем маркдауном, который поддерживает доксиген.

Как я понял, Github изначально был написал на Руби (на рельсах, наверное), и оттого там для рендеринга маркдауна используется написанный на Руби движок Jekyll, к нему только нужно доустановить пакет для GFM. Там, скорее всего, тоже регулярки, можно выдрать оттуда, только там, скорее всего, тоже свой диалект регулярок.

А какого-то каноничного парсера маркдауна нет и не будет. Каждая реализация в мелочах несовместима с другими.

Да, ещё есть VSCode и к нему разные плагины

Можно поковырять их сорцы

Re: Про канонический алгоритм парсинга Markdown и подобного

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

S>Вроде классически для разбора таких текстов как Markdown применяют типа конечный автомат:

Кодт выше всё неплохо расписал, в общем.

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

Например:

enum State
{
  stInitial
  stWaitSecondAsterisc,
  stWaitSecondUndersore,
  stWaitSecondbacktick,
  stWaitThirdbacktick,
  //...

};

void handleChar(char ch, State &st)
{
  switch(st)
  {
    case stInitial:
        // Или тут тоже switch
        if (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;

    // ...
  }
}

Можно поковырять их сорцы