Отвёртка для выражений

    Область применения разбора математических выражений представить не сложно — это и всевозможные парсеры SQL-запросов, и обработчики формул, вводимых пользователем (то же построение графиков или фильтры к БД) — вплоть до создания собственных языков (намеренно не пишу слово «программирования», т.к. зачастую это языки описания данных и иже с ними).

    Возможно, я не прав, но я не сумел найти на просторах сети более или менее юзабельный парсер выражений для PHP — и, как наверное уже привыкли те, кто периодически читает мои статьи, я отправился реализовывать это дело своими силами, т.е. изобретать велосипед. :^)

    Результат моих потуг вы можете обнаружить здесь. В архиве вы найдёте скрипты, необходимые для функционирования библиотеки, и пример её работы (sample.php). Библиотека собрана как standalone.

    Но, я полагаю, интересно было бы разобраться, что там к чему.

    Как несложно догадаться, библиотека построена на основе ОПЗ (обратная польская запись, или нотация, если вам так привычнее). Однако ОПЗ имело смысл доработать до нужной кондиции, потому как в её описании даётся лишь базовый функционал для разбора выражений. Итак, вот схема работы библиотеки:

    Описание правил разбора выражения производится в класса, унаследованном от класса CIpr. Определение грамматик и классов производится в защищённом методе p_build.

    Для начала нужно определить грамматические классы (или грамматики), на основе которых парсер будет разделять переданную ему строку на лексемы. Каждая лексема состоит из токена (собственно слова) и идентификатора класса (того, который вызвал выделение этой лексемы). Идентификатор класса — это индекс массива, т.е. это может быть строка или целое число (я использовал строки для наглядности). Я определил следующие возможные типы грамматик:

    grammar_char(символы[, сочетания])
    Такие грамматики определяются набором символов (строка, в которой эти символы перечислены) и, возможно, сочетаниями символов (массив строк).
    Определение выглядит так: grammar_char("+-*/=", array("+=", "++")). Эта грамматика определяет одиночные символы +, -, *, / и = и их сочетания += и ++.

    grammar_list(лексемы[, чувствительность к регистру = true])
    Этот тип грамматик определяется предопределёнными наборами лексем. Можно так же определить, учитывать ли при определении лексемы регистр (по умолчанию — да).
    Использовать можно так: grammar_list(array(«prefix1», «prefix2»), false). Эта грамматика определяет лексемы prefix1 и prefix2, не чувствительные к регистру. Важно, что будет просто производиться поиск одной лексемы из списка в начале строки без учёта разделителей, т.е. из выражения prefix1something будет выделена лексема prefix1.

    grammar_preg(начло[, извлечение])
    Этот тип грамматик, вместе с символьными, я думаю будет наиболее полезен. Это грамматики, построенные на основе регулярных выражений. Они описываются регуляркой начала и, возможно, регуляркой для извлечения. Если извлечение не указано, то вместо него используется начало. Вот такое регулярное выражение, например, выберет комментарии вида // комментарий: /^\/\/.*/

    grammar_quot(символ кавычки[, режим экранирования = C_ESCAPE_CHAR])
    Грамматики этого типа — это заключённые в кавычки строки. Режим экранирования может принимать следующие значения:
    C_ESCAPE_NONE — экранирование символов в строке не производится. (Строка «10\»" будет распознана как 10\).
    C_ESCAPE_CHAR — экранировать можно только управляющие символы. (Строка «10\'-\»" будет распознана как 10\'-").
    C_ESCAPE_ALL — экранирующий символ \ можно ставить перед всеми символами. (Строка «1\0\'-\»" будет распознана как 10'-").

    grammar_brac(символы скобок[, режим экранирования = C_ESCAPE_ALL[, <разрешать вложенность = true>]])
    Это скобочные грамматики (т.е. выделяющие выражения типа <anfg>). Их использование лично мне представляется сомнительным в данном контексте — они предназначены для других целей (эта библиотека — только часть платформы). Но можете их использовать, если пригодятся. :^)

    grammar_user(начало, извлечение)
    Это пользовательская грамматика, определяемая функциями начала и извлечения.

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

    Дальше, что интереснее, определяются классы возможных команд в коде выражения. Можно определять следующие типы команд:

    ipr_lexeme(лексема)
    Определяет, что указанная лексема должна обрабатываться как команда типа «лексема». В роли лексемы может выступать как полноценная лексема, определённая через функции lexeme и ilexeme, или просто строка, определяющая токен лексемы.

    ipr_operator(лексема, приоритет[, арность = 2[, ассоциативность = нет(что сейчас эквивалентно левой, что не совсем верно)]])
    Определяет оператор.
    Можно так же использовать функции:
    ipr_perfix — префиксный унарный оператор;
    ipr_postfix — постфиксный унарный оператор;
    ipr_binary — бинарный оператор.

    ipr_compound(массив лексем, приоритет[, арность = 3[, ассоциативность = правая[, вычислять автоматически = нет]]])
    Определяет сложный оператор. В чём отличие от простого? Операнды простого оператора вычисляются самим движком, что, скажем, для оператора ?: не совсем корректно, т.к. вычислить нужно только один из его второго и третьего операндов. Для этого и нужен сложный оператор — для него вычисляется автоматически только первый операнд, а все последующие передаются на обработку в пользовательский метод. Таким образом имеет смысл определять сложные операторы с арность не менее 2.
    Можно так же использовать функции:
    ipr_access — бинарный оператор доступа к полю объекта;
    ipr_ternary — тернарный оператор.

    ipr_brackets(открывающая лексема, закрывающая лексема, запятая[, могут ли использоваться без операнда = нет[, арность = не определено[, вычислять автоматически = да]]])
    Определяет скобки. Скобки могут использоваться без операнда (например (a + b)) или с операндом (например, arr[10]). Так же может быть определена арность скобок, когда в них нужно указывать строго определённое количество операндов. Про автоматический можно прочитать выше.
    Можно так же использовать функции:
    ipr_default — определение скобок, используемых для установки приоритете (т.е. скобок по умолчанию).

    ipr_instruction(лексема, открывающая лексема, закрывающая лексема, запятая[, арность = не определено[, вычислять автоматически = нет]])
    Определяет инструкцию. Фактически то же самое, что и скобки с запретом автоиспользования, только вместо операнда перед скобками используется лексема инструкции.

    ipr_end(лексема)
    Определяет лексему, на которой выражение считается закончившимся.

    ipr_until(лексема)
    Определяет лексему, на которой выражение считается закончившимся. При этом лексема остаётся в начале остатка выражения.

    Теперь нужно определить обработчики всех типов команд, коих 5 — операнд, лексема, оператор, сложный оператор, скобки и инструкция. Это следующие защищённые методы:

    p_run_operand(команда)
    p_run_lexeme(команда)
    p_run_operator(команда, операнды)
    p_run_compound(команда, операнд, операнды)
    p_run_brackets(команда, операнд, операнды)
    p_run_instruction(команда, операнды)

    Команда содержит тип команды (не важен, т.к. им и определяется обработчик, т.е. ситуация, когда в обработчик операнда придёт команда оператора, невозможна), класс команды и лексему, которая была определена как команда. Операнд содержит вычисленный операнд, а операнды — операнды, либо вычисленные, либо ожидающие обработки через метод p_run (в зависимости от типа команды и флага «вычислять автоматически»).

    Теперь, чтобы создать обработчик выражения, нужно создать экземпляр класса обработчика, которому передано в конструктор выражение для обработки. Конструктор выполнит грамматический разбор и компиляцию выражения. Чтобы запустить выражение, следует использовать метод run.

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

    Благодарю за ваше внимание! Буду очень рад услышать ваши отзывы и замечания в комментариях вне зависимости от их положительности. :^)
    Share post

    Comments 17

      +2
      А вы не хотите вместо написания yet another parser перенести на php комбинатор парсеров parsec?
        0
        … простите: лучшей, вероятно, будет эта ссылка: www.haskell.org/haskellwiki/Parsec
          0
          Спасибо, уже нашёл эту же ссылку же через Google. :^)

          Да, идея интересная, благодарю. Не сталкивался с этой штукой раньше. Будет время — обязательно разберусь и займусь (если никто ещё не перенёс, конечно :^)
            +1
            Осторожно, и придерживайте мозг свободной рукой, когда будете читать :)
        +1
        Почитайте «Книгу дракона» Ахо, Сети и Ульмана.
        Да и мануал по функции token_get_all() думаю не повредит.
          0
          За совет насчёт книги — спасибо, я обязательно прочитаю.

          А вот по поводу token_get_all — я про неё знаю, и она прекрасно подойдёт для грамматического разбора выражения — если оно записано на PHP. Не уверен, что синтаксис PHP подойдёт в 100% случаев.
            +1
            В книге рассматриваются, кроме всего прочего, существующие генераторы синтаксических анализаторов. А в конце книги приводится синтаксис языков С, Java и, если память не изменяет, C#. Думаю с учетом ваших интересов, стоит уделить на это особое внимание, чтобы не изобретать велосипед.
            Кроме того, рассматривая разбор граматики математических выражений, не стоит забывать о функциях. Применяя простые грамматики типа LL(1) вполне можно реализовать ваши пожелания :)
              0
              Благодарю ещё раз за полезную ссылку — я действительно собирался в ближайшее время заниматься подобными разработками (правда, не на PHP, и данный парсер не имеет к ним никакого отношения :^), так что с этой литературой так же ознакомлюсь.
                +1
                Не за что. Единственный момент: «книг дракона» 3 части. Первая — практически на одной теории, вторая со множеством примеров на C и Pascal. Третья — с примерами на Java. Выбирайте ту, что наиболее вам подходит.
          0
          не смотрел код, но прочитал бегло статью. Сам удивлялся почему ничего подобного пока еще никто не описал. Хотя реально нужно как правило «маленький» парсер, а он пишется за пару часиков.
            0
            не говорю конкретно про Вас, но обычно когда говорят «пару часиков» то дело сводится к пару дням… парсер — не регулярное выражение которое бьет строку на части, и это надо изначально учитывать
              0
              парсер именно выражения даже проще может быть — например рекурсивный спуск

              Вообще гугль по «parser generator php» выдает ненулевой результат
                0
                Во-первых, я хочу поблагодарить всех за ссылки на полезный материал по этой теме. Многое из этого полезно было вспомнить, а что-то — узнать. И всё это наверняка будет полезно тем, кто данный топик читает как " ещё один источник по теме".

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

                1) Использования сложных операторов и инструкций.
                2) Вызова функций (настоящего, а не в форме sin(x), который превращается в вызов оператора sin).

                Таким образом алгоритм ОПЗ в данной библиотеке был расширен, во-первых, тем что в базовый алгоритм были внесены дополнительные понятия, и, во-вторых, тем что возможности по определению команд и грамматических классов оставлены на откуп пользователю, благодаря чему вы сможете парсить как выражения а-ля
                (A * B? sin: cos)(10)
                так и
                Если A умножить на B тогда sin иначе cos аминъ вызвать с аргументами 10 аминъ
                или чуть посерьёзнее, типа
                IF(A MUL B, CONCAT(user.lastname, ' ', user.firstname), 'Unknown user')

                Но я соглашусь с тем, что

                1. Универсальность полученного парсера — это его недостаток. Если «вернуться к истокам» ОПЗ и жёстко определить грамматические классы, код сократится раз в десть точно. Но тогда не получится парсить такие замечательные выражения, как «Давай 10 прибавь-ка к 12, вот.» (ассоциативность правая, вроде :^) А если серьёзно — невозможно заранее предугадать цели, с которыми данный парсер будет использоваться. Поэтому я бы порекомендовал использовать данный парсер (если кто-то, конечно, будет это делать) не наследованием класса CIpr, как это «предусмотрено стандартом» библиотеки, а отстриганием от библиотеки всего ненужного для решения конкретной задачи и жёстким определением всего, что отдано на откуп пользователю — производительность возрастёт в разы, равно как и уменьшится объём кода.

                2. «Простой» парсер в PHP — это то же самое, что шоколадка с шоколадной начинкой. PHP сам по себе уже является неплохим «парсером», т.е. во многих случаях, когда встаёт вопрос о необходимости парсера математики или даже более сложных конструкций, достаточно использовать eval для получения нужного результата. Причём eval, по понятным причинам, сработает заведомо быстрее любого, даже самого оптимального алгоритма, реализованного на PHP. Построение любого парсера либо преследует чисто академическую цель, либо нужно для решения задач, которые значительно сложнее простых математических выражений (как в данном случае).

                Это я всё к тому, что я хотел предостеречь тех, кто собирается использовать данное решения для вычисления выражений типа 1 + 2 / 3, и уж тем более тех, кто собирается для подобных целей изобретать свой парсер «с блэкджеком и шлюхами» (с) Бендер. Если бы я, на момент написания этого «шедевра» имел уже готовую альтернативу для реализации собственного языка описания данных, я бы воспользовался ей.

                Благодарю за внимание тех, кто до сюда дочитал — я люблю изъясняться развёрнуто. :^)
                  0
                  я о сроках, я писал простенький парсер, который парсил банальные условия вида if( {field} = value and|or {field2} != value2… ) и это не выглядит очень прям сложным, но заняло далеко не пара часов
                    0
                    это вместе с лексером? В проуессе вы что нибудь учили или вы помнили курс конструирования компиляторов?
                      0
                      нет, я ничего не учил, работал императивным методом, я вкурсе что это замедлило процесс, но задача изначально казалась проще, надо было просто чекнуть галочки по условию на JS, и я тоже подумал что справлюсь за «пару часов»
                  0
                  мои потуги тут: habrahabr.ru/blogs/php/73665/

              Only users with full accounts can post comments. Log in, please.