Форум на Исходниках.RU https://forum.sources.ru Форум на Исходниках.RU Форум на Исходниках.RU https://forum.sources.ru/index.php?showtopic=411567&view=findpost&p=3832676 Tue, 16 Jun 2020 20:12:51 +0000 Алгоритм разбора BB-разметки с вложениями https://forum.sources.ru/index.php?showtopic=411567&view=findpost&p=3832676 Pavia, спасибо еще раз! Как говорится ... не прошло и пол-года :lol:

Сейчас соглашусь - для качественного выделения без AST не обойтись. Да возможны мелкие и частные решения, которые декларируют AVA12 и Akina, ну и тупо чуйка (траблы типа - строк без квотирования, целых, дробных, квотирование в квотировании). Но, имхо, и они не качественные! Да, можно решить 20% злободневных задач на отличненько (Паретто бы кончил) - в угоду сиюминутного профита.]]> JoeUser Алгоритмы https://forum.sources.ru/index.php?showtopic=411567&view=findpost&p=3748813 Fri, 10 Nov 2017 02:35:26 +0000 Алгоритм разбора BB-разметки с вложениями https://forum.sources.ru/index.php?showtopic=411567&view=findpost&p=3748813 Pavia, спасибо за инфу! В плане "познавания" хороша, но для моей задачи - неимоверно избыточна. В блоке {code} может быть представлено 135 ЯП - по заявлениям автора либы для php-раскрасски. Влезать в парсинг всех тех языков, да еще и формально правильно, используя описанную теорию - ни желания, ни времени.

Поэтому, подход, описанный Akina, а ниже и AVA12 - будет вполне пригоден для этой моей задачи.]]> JoeUser Алгоритмы https://forum.sources.ru/index.php?showtopic=411567&view=findpost&p=3748810 Thu, 09 Nov 2017 21:39:30 +0000 Алгоритм разбора BB-разметки с вложениями https://forum.sources.ru/index.php?showtopic=411567&view=findpost&p=3748810 Pavia и напустил туману.
Цитата
Регулярные выражения находятся классом выше, но не покрывают весь второй класс поэтому для вас они непригодны.

Тут, вроде бы, грамотные люди, которые понимают, что HTML регвырами не парсят. А вот для лексического анализа регвыров в два наката вполне достаточно.]]> AVA12 Алгоритмы https://forum.sources.ru/index.php?showtopic=411567&view=findpost&p=3748809 Thu, 09 Nov 2017 21:34:36 +0000 Алгоритм разбора BB-разметки с вложениями https://forum.sources.ru/index.php?showtopic=411567&view=findpost&p=3748809 AVA12 Алгоритмы https://forum.sources.ru/index.php?showtopic=411567&view=findpost&p=3748808 Thu, 09 Nov 2017 21:30:53 +0000 Алгоритм разбора BB-разметки с вложениями https://forum.sources.ru/index.php?showtopic=411567&view=findpost&p=3748808 Цитата JoeUser @
Как всю эту шляпу разобрать правильно? На ум приходит - строить дерево и по нему бегать. И то, пока не понятно как
Ваши мнения?


Ваша задача от носится к теории языков. Сразу скажу что теория очень сильно оторвана от практики.

Вначале определим класс грамматики по Хомскому. Ваша грамматика относится к контекстно-зависимым.

ТипВид правилНазвания правилМетод распознавания
0α→βПроизвольные правила,
неограниченные правила
свободные грамматики 		Машины Тьюринга
1γAδ→γβδ
aAβ→αγβ		Контекстно-зависимые грамматика,
КЗ-правила 		Рекурсивные автоматы, рекурсивный спуск
2A→γКонтекстно-свободные грамматика,
КС-правила 		Автоматы с магазинной памятью(табличные автоматы со стековой памятью)
3A→aB
A→a
A→ε
Регулярные грамматики,
Р-правила
Автоматические грамматики
А-правила		Конечные автоматы


Не стоит путать регулярные выражения с регулярными грамматиками.
Регулярные выражения находятся классом выше, но не покрывают весь второй класс поэтому для вас они непригодны.

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

В теории вы можете найти множество различных парсеров. Каждый парсер решает свою частную задачу и эти задачи плохо ложатся на выше изложенную классификацию. SLR относится к типу 3, а LALR(N) к типу 2. Но благодаря тому что теория не стояла на месте тип 2 легко сводится к типу 3.

И да если вы не дай бог решите ещё глубже копать в теорию, то обязательно прочтите
https://swtch.com/~rsc/regexp/regexp1.html
и изучите код детерминированного конечного автомата .

Это всё, что вы должны знать из теории. А теперь забудьте всё, что вы знали и переходите к практике.
За основу вашего парсера предлагаю взять шаблоны-проектирования и подходы из компилятора LCC - это обязательно к изучению.
https://sites.google.com/site/lccretargetab...piler/downloads

Второй способ и что главное гораздо продуктивный использование генератора парсеров Bison или Bison++.
Для этого метода обязательно к прочтению является документ
https://www.opennet.ru/docs/RUS/bison_yacc/bison_toc.html

После прочтения вы должны ответить на ряд вопросов:
Конфликты свёртка/сдвиг?
Конфликты свёртка/свёртка?
Что такое висячий else?
Левые операторы/правые операторы зачем нужны и почему недостаточно приоритетов?

Вот тут можно посмотреть пример как создать парсер для языка сложнее калькулятора.
https://habrahabr.ru/post/99397/

И да вы правильно заметили результатом работы парсера будет дерево. AST - абстрактное синтаксическое дерево.]]> Pavia Алгоритмы https://forum.sources.ru/index.php?showtopic=411567&view=findpost&p=3748794 Thu, 09 Nov 2017 19:14:14 +0000 Алгоритм разбора BB-разметки с вложениями https://forum.sources.ru/index.php?showtopic=411567&view=findpost&p=3748794 Akina, согласен!]]> JoeUser Алгоритмы https://forum.sources.ru/index.php?showtopic=411567&view=findpost&p=3748728 Thu, 09 Nov 2017 12:09:56 +0000 Алгоритм разбора BB-разметки с вложениями https://forum.sources.ru/index.php?showtopic=411567&view=findpost&p=3748728 Цитата JoeUser @
Ошибка разметки

В корне не согласен с трактовкой. Разбор должен проходить по принципу "Кто первый встал, того и тапки". Так что в первом примере у тебя валидный тег {pre}, внутри которого есть подстрока {code}, и "зависший" закрывающий тег {/code}, который должен интерпретироваться как обычный текст. Аналогично и во втором примере всё наоборот - валиден {code} и "подвис" {/pre}. А то с твоим подходом какое-нибудь
    {code} ... {pre} ... {/code} ... {code} ... {/pre} ... {/code}

вообще нормально не разберётся.

Цитата JoeUser @
Как всю эту шляпу разобрать правильно?

Флаг текущего тега, и всё. Пока не попался закрывающий, всё есть тело тега. Если текст кончился, а тег не закрыт - закрывать автоматически.]]> Akina Алгоритмы https://forum.sources.ru/index.php?showtopic=411567&view=findpost&p=3748724 Thu, 09 Nov 2017 11:56:15 +0000 Алгоритм разбора BB-разметки с вложениями https://forum.sources.ru/index.php?showtopic=411567&view=findpost&p=3748724 Взялся я немного усовершенствовать форумный движок FluxBB. А именно:

  1. Вместо забитого хардкодом bb-кода "code" - дать возможность пользовать нечто типа "code=language"
  2. Добавить тэг разметки "pre"

Для справки, тэг "code" обрамляет блок текста, который нужно выводить моноширинным шрифтом, обрамлять css-атрибутом "pre", сам блок не квотить. ВВ-тег делает все тоже самое. Разница в том, что в последующем блок "code" будет раскрашиваться по синтаксису, а блок "pre" - просто выводить моноширинный текст на своем фоне.

Получить позиции этих bb-тегов - первый шаг и очень простой, в PHP решается регуляркой и функцией "preg_match_all", последующим сканом текста. А вот далее - самое сложное. Далее в примере я буду использовать фигурные скобки в тегах, дабы нынешний форум не съедал разметку.

Вложенность

В этом варианте вложенный блок "code" - выделяться не должен, от часть текста из "pre":

    {pre}
    {code=cpp}
    if (true == false) exit();
    {/code}
    {/pre}

В этом варианте вложенный блок "pre" - выделяться не должен, от часть строки из кода:

    {code=cpp}
    std::cout << "{pre} строка {/pre}" << std::endl;
    {/code}


Ошибка разметки

В этом случае открывающий тег "pre" не закрывается, т.к. "закрывалка" находится в валидном блоке "code". Первый открывающий тег "pre" должен просто квотиться:

    {pre}
    {code}
    std::cout << "строка {/pre}" << std::endl;
    {/code}


В этом случае открывающий тег "code" не закрывается, т.к. "закрывалка" находится в валидном блоке "pre". Первый открывающий тег "code" должен просто

    {code}
    {pre}
    delimitel="{/code}"
    {/pre}


Собственно, вопрос:

Как всю эту шляпу разобрать правильно? На ум приходит - строить дерево и по нему бегать. И то, пока не понятно как :-?
Ваши мнения?]]> JoeUser Алгоритмы