Парсер‑комбинаторы «с нуля»

[lubaskinc0de]

Блестящая статья, очень круто и понятно написано.

[Alexandroppolus]

из‑за большого количества вызовов функций, у нас постоянно пересоздаются строки из‑за substring.

В движках JS для такого кейса давно реализованы т.н. sliced-строки, переиспользующие буфер.

[tapeline]

Да, но такие оптимизации есть, к сожалению, не во всех языках. TS здесь чисто для примера

[ChilliWil]

TS хорош для примеров потому что его синтаксис понятен всем) Для обучения концепциям это норм, для перфоманса - нет

[programania]

Кто-то может попытаться использовать RegEx, но скоро поймёт, что парсить что-то сложнее телефонных номеров уже очень больно или даже невозможно.

Что же такое мы получили? Мы получили то, что называется Расширенной Формой Бэкуса-Наура (Extended Backus-Naur Form — EBNF). По сути, это способ описать грамматику языка: какие конструкции как описываются и где что можно записать

Так ведь регулярные выражения это и есть способ описания грамматики, причём много мощнее чем BNF, только в отличии от BNF и прочих самодельных, RegEx поддерживаются во всех языках и их все знают.
И я сделал интерпретатор языка типа JS ещё на java 4, в котором каждая конструкция языка описывается одним RegEx. Они по порядку сравниваются с текстом программы и сравнение заменяется на ссылку на элемент массива AST так, что в конце остаётся 1 элемент, который и выполняется.

[tapeline]

Так ведь регулярные выражения это и есть способ описания грамматики, причём много мощнее чем BNF,

Скорее наоборот) Выражение на то и регулярное, что парсит регулярные языки. А далеко не все таковыми являются. Например, правильные скобочные последовательности уже в них не входят.

RegEx поддерживаются во всех языках и их все знают.

Достаточно попробовать описать простую арифметику (числа, +-*/ и скобки) в БНФ и в RegEx и сравнить, что получится (честно говоря, даже не знаю, как в последнем это описать, потому что уже есть ПСП)

[programania]

RegExp описывает грамматику так же как и БНФ по элементам начиная снизу: сначала числа, потом число знак число, потом выражение в скобках и т.д. так что после каждой замены начинают сравниваться элементы более высокого уровня. И так один алгоритм распознаёт и выражения со скобками и функции и вложенные блоки и т.д.:

Скрытый текст

    static String[] zt={
    //конструкции языка,                        на что менять, номер
    "\".*?(?<!\\\\)\"|'.*?(?<!(?<!\\\\)\\\\)'",           "p", "0", // строка
    "//.*?$|/\\*.*?\\*/|[А-я][А-я\\w\\., ]+$",            "c", "23",// коментарий
    "\\.(repl|equals|htm|matches|substr|rex|trim|lower|upper|replex|length|pos)(?=\\()",
                                                          "e", "26",// методы строк
    "(?<!\\w)var ([\\w=~,]+)",                            "p", "22",// локальные переменные
    "(?<!\\w|~)(?!(if|else|while|function|for|return|break|continue|var)\\W)(\\+\\+|--|)([A-Za-zА-я\\$\\.][\\wА-я\\.]*)(\\+\\+|--|)",
                                                          "p", "1", // переменная
    "(?<!\\d|\"|\\.|~|\\)|\\])([\\+-])([\\d\\.]+|~\\d+~)","p", "2", // число с одноместным +-
    "!(~\\w+~)(?!\\(|\\[)",                               "p", "28",// выражение с одноместным !
    "(?<!~|\\w|\\.)[\\d\\.]+",                            "p", "3", // число
    "(?<!/|\\*)(~\\w+~)(/|\\*)(~\\w+~)(?!\\(|\\[|~e)",    "p", "4", // выражение */ выражение
    "(?<!/|\\*|-)(~\\w+~)(\\+|-)(~\\w+~)(?!\\*|/|\\(|\\[|~e)", "p", "4", //5 выражение +- выражение
    "(~\\w+~)(\\>|<|<=|>=|==|!=)(~\\w+~)(?![-\\+\\*/\\[\\(]|~e)",
                                                          "p", "12",// выражение >=< выражение
    "(~\\w+~)(&&|\\|\\|)(~\\w+~)(?!\\*|/|\\()",           "p", "12",//18 выражение && || выражение
    "(?<=[\\(\\[,])(~[pm]\\w+~),(~[pm]\\w+~)(?!\\(|~e|\\[|~|\\+|-|\\*|/|=)","p", "6", // параметры через ,
    "(~p\\w+~)\\[(~[pm]\\w+~)\\](\\+\\+|--|)",            "m", "16",// массив
    "(?<!\\w)for\\(([^;]*);([^;]*);([^\\)]*)\\)",         "f", "19",// заголовок цикла for
    "(?<!\\w)return([^;]*);",                             "o", "21",// return в функции
    "(?<!\\w)(break|continue);",                          "o", "24",// break в цикле
    "(?<=[-\\(=\\+\\*/])(~[mp]\\w+~)()=(~[mps]\\w+~)(?![-\\+\\*/\\[\\(]|~e)", "p", "29", // оператор присвоения в выражении
    "(~[mp]\\w+~)(\\+|-|)=(~[mps]\\w+~)(,|;|$)","o", "13",// оператор присвоения
    "\\((~\\w+~)\\)",                                     "s", "7", // (выражение)
    "(?<!~)(~[spm]\\w+~)(~e\\w+~)(~s\\w+~)",              "p", "27",// методы строк для преобразования в функции
    "if(~\\w+~)(~o\\w+~)(?:else (~o\\w+~)|(?!else))",     "o", "11",// условный оператор
    "(?<=\\{|^)(~o\\w+~)(~o\\w+~)",                       "o", "10",// 2 оператора
    "\\{ *(~o\\w+~|) *\\}",                               "o", "15",// {оператор}
    "function (~\\w+~)(~\\w+~)(~o\\w+~)",                 "o", "17",// обьявление функции
    "(?<!function(?: |))(~[mp]\\w+~)(~s\\w+~)",           "p", "8", // вызов функции
    "(~\\w+~)\\?(~\\w+~):(~\\w+~)(?!\\(|~|\\[|\\+|-|\\*|/|=)", "p","25",// усл?p1:p2
    "(?<![-=\\+\\*></:])(~[^s]\\d+~);",                   "o", "9", // оператор
    "while(~\\w+~)(~o\\w+~)",                             "o", "14",// цикл while
    "(~f\\w+~)(~o\\w+~)",                                 "o", "20"};//цикл for

[CorwinH]

регулярные выражения это и есть способ описания грамматики, причём много мощнее чем BNF

Регулярными выражениями можно парсить только регулярные грамматики?

[Genrih124]

интересно

[ddranic]

Парсер‑комбинаторы имеют некоторое количество минусов. Среди главных:

• широкое использование функций легко может приводить к проблемам с производительностью и переполнению стека

кажется главная проблема производительности будет экспоненциальная сложность из-за откатов, а не substring

[tapeline]

Да, это так, забыл упомянуть. Хотя можно попытаться это оптимизировать, например, мемоизацией

[ChilliWil]

экспоненциальная сложность

это фича) называется "прогрев процессора перед парсингом следующего токена"

[ChilliWil]

Наивная реализация комбинаторов без мемоизации гарантированно свалится в экспоненциальное время при левой рекурсии

[Filipp42]

Добрый день!
Спасибо вам за статью!
Я когда-то писал парсер-комбинаторы на Лиспе. Похоже, что подходящей оптимизации не было, комбинаторы работали очень медленно.
В языке программирования Lean комбинаторы чуть ли не в стандартную библиотеку встроены.
Скажите, может быть, вы не против посмотреть язык Lean, и немного попрограммировать на нём?
Он вообще имеет двоякую природу. С одной стороны он язык программирования общего назначения, похожий на Haskell, только там гораздо более мощная система типов - зависимые типы.
С другой - средство доказательства теорем. Мне было забавно сегодня доказать теоремы про алгоритм Евклида. Правда, на индуктивном доказательстве я застрял. Но это нормально. Математику я только изучаю.

В любом случае, штука интересная.

[SystemSoft]

Привет!
Статья классная, но можете подсказать мне (чайнику)?
Как обходится с ситуацией когда к примеру вы сделали sequence для print и там может быть и int, и id (ну имя переменной)?

[tapeline]

Пусть у нас есть правило: print что-то, где что-то — это имя переменной или число. Тогда, имея уже готовый парсер pInt и pId, мы можем сделать что-то вроде:

pPrint = pSequence(pString("print"), pSpace, pOneOf(pInt, pId))

Но вообще, скорее всего, вы захотите получать там любое выражение в принципе, поэтому выделите в правило вроде pExpr все выражения.

Советую посмотреть, как это сделано в других языках, например, в Python: ссылка на грамматику есть в статье, вам нужно найти правило expression, там расписано, как парсятся выражения с учетом приоритета операций (в том числе и вызовы функций). Проделав действия, обратные разделу “Немножко формализма”, вы можете написать похожий парсер на комбинаторы.

[SystemSoft]

Спасибо