Регулярные выражения: как научиться читать между строк

[apevzner]

Как написать регулярное выражение, которое проверит, правильно ли расставленны скобки в арифметическом выражении?

(())()()(((()()))) - OK
(())) - не ОК
())(() - не ОК

[cupraer]

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

Возьмите PDA, не нужно заколачивать шурупы микроскопом :)

[apevzner]

Вопрос был с подвохом.

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

POSIX regexp, кстати, нифига не регулярная грамматика. С возможностью ссылаться на уже разобранные части входного текста, она куда мощнее. Но и цена соответствующая, никакого O(n), где n - длина входного текста, она не гарантирует.

[cupraer]

Есть совершенно гениальная книга Michael Sipser, Introduction to the Theory of Computation. У меня бумажная третья версия, но вторая, оказывается, доступна в pdf, так что вот ссылка выше.

Лично я ее просто как детектив читал. Супер, очень рекомендую.

[cupraer]

Кстати, для данной конкретной задачи PDA по-прежнему справляется за O(n):

defmodule Grammar do
  @input """
         (())()()(((()()))) - OK
         (())) - не ОК
         ())(() - не ОК
         """
         |> String.trim()

  def parse(input, acc \\ %{lefts: 0, pos: 0})

  def parse("", %{lefts: 0}), do: :ok
  def parse("", %{lefts: lefts}), do: {:error, {:missing_closings, lefts}}
  def parse(")" <> _, acc) when acc.lefts < 1, do: {:error, {:extra_closing_at, acc.pos + 1}}
  def parse(")" <> rest, acc), do: parse(rest, %{lefts: acc.lefts - 1, pos: acc.pos + 1})
  def parse("(" <> rest, acc), do: parse(rest, %{lefts: acc.lefts + 1, pos: acc.pos + 1})
  def parse(<<_::utf8, rest::binary>>, acc), do: parse(rest, acc)

  def test do
    @input
    |> String.split("\n")
    |> Enum.map(&parse/1)
  end
end

Grammar.test()
#⇒ [:ok, {:error, {:extra_closing_at, 5}}, {:error, {:extra_closing_at, 3}}]

[Teilot]

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

[cupraer]

Не получится, эта задача не имеет решения на регулярках. Выше я привел рекурсивное решение, которое отрабатывает за O(n) и не создает никаких списков и не использует вообще ничего, кроме входной строки (ну и аккумулятора незаметного размера).

[martin_wanderer]

Адреса электронной почты не регулярны

[apevzner]

Смотря что считать адресом.

Если адрес целиком, в терминах RFC822 ("Vasya Pupkin [e-mail]"), то там такая неудачная грамматика, что она не только не регулярная, а еще и backtracking требуется, чтобы этот синтаксис правильно разобрать.

А в той части, которая имя@домен - что в этом не регулярного?

[martin_wanderer]

Да, я имел в виду именно RFC-822. А если даже и говорить только про local-part@domain, то они, кажентся, регулярны, но тоже имеют право быть quoted-strings, что не учтено в приведенных регулярках.

[cupraer]

Регулярные выражения или regex (от англ. regular expression) – это особый синтаксис […]

Синтаксис? Регулярные выражения — это синтаксис? Передайте вашей LLM, что она бредит.

[Veta_liza]

хм, саппорт гугла говорит о синтаксисе для регулярных выражений: https://support.google.com/a/answer/1371415?hl=ru

[cupraer]

«Синтаксис, позволяющий описывать регулярные выражения» и «регулярные выражения — это синтаксис» — не изоморфные конструкции.