На главную Наши проекты:
Журнал   ·   Discuz!ML   ·   Wiki   ·   DRKB   ·   Помощь проекту
ПРАВИЛА FAQ Помощь Участники Календарь Избранное RSS
msm.ru
! правила раздела Алгоритмы
1. Помните, что название темы должно хоть как-то отражать ее содержимое (не создавайте темы с заголовком ПОМОГИТЕ, HELP и т.д.). Злоупотребление заглавными буквами в заголовках тем ЗАПРЕЩЕНО.
2. При создании темы постарайтесь, как можно более точно описать проблему, а не ограничиваться общими понятиями и определениями.
3. Приводимые фрагменты исходного кода старайтесь выделять тегами code.../code
4. Помните, чем подробнее Вы опишете свою проблему, тем быстрее получите вразумительный совет
5. Запрещено поднимать неактуальные темы (ПРИМЕР: запрещено отвечать на вопрос из серии "срочно надо", заданный в 2003 году)
6. И не забывайте о кнопочках TRANSLIT и РУССКАЯ КЛАВИАТУРА, если не можете писать в русской раскладке :)
Модераторы: Akina, shadeofgray
  
> Алгоритм разбора BB-разметки с вложениями
    Буэнос диас, амигос! :)
    Взялся я немного усовершенствовать форумный движок FluxBB. А именно:

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

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

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

    Вложенность

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

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

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

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


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

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

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


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

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


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

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

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

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

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

      Флаг текущего тега, и всё. Пока не попался закрывающий, всё есть тело тега. Если текст кончился, а тег не закрыт - закрывать автоматически.
      Сообщение отредактировано: Akina -
        Akina, согласен!
          Цитата 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 - абстрактное синтаксическое дерево.
            В случае с pre и code можно сделать еще проще: все от открывающего тега до ближайшего подходящего закрывающего считать одним самозакрывающимся тегом, и пофиг, что у него в нутре. Если же юзер забудет закрыть специальный тег, он будет распознан, как обычный. Увидев одинокий открывающий специальный тег можно будет либо обругать юзера, либо автоматически пропустить оставшуюся часть текста и закрыть-таки тег.
              P. S. Пришел Pavia и напустил туману.
              Цитата
              Регулярные выражения находятся классом выше, но не покрывают весь второй класс поэтому для вас они непригодны.

              Тут, вроде бы, грамотные люди, которые понимают, что HTML регвырами не парсят. А вот для лексического анализа регвыров в два наката вполне достаточно.
                Pavia, спасибо за инфу! В плане "познавания" хороша, но для моей задачи - неимоверно избыточна. В блоке {code} может быть представлено 135 ЯП - по заявлениям автора либы для php-раскрасски. Влезать в парсинг всех тех языков, да еще и формально правильно, используя описанную теорию - ни желания, ни времени.

                Поэтому, подход, описанный Akina, а ниже и AVA12 - будет вполне пригоден для этой моей задачи.
                  Pavia, спасибо еще раз! Как говорится ... не прошло и пол-года :lol:

                  Сейчас соглашусь - для качественного выделения без AST не обойтись. Да возможны мелкие и частные решения, которые декларируют AVA12 и Akina, ну и тупо чуйка (траблы типа - строк без квотирования, целых, дробных, квотирование в квотировании). Но, имхо, и они не качественные! Да, можно решить 20% злободневных задач на отличненько (Паретто бы кончил) - в угоду сиюминутного профита.
                  0 пользователей читают эту тему (0 гостей и 0 скрытых пользователей)
                  0 пользователей:


                  Рейтинг@Mail.ru
                  [ Script execution time: 0,0307 ]   [ 16 queries used ]   [ Generated: 28.03.24, 15:59 GMT ]