^ и $ выражаются в фундаментальных операциях в регулярных выражениях

Question

Я прочитал книгу, в которой говорится, что все фундаментальные операции в регулярных выражениях concatatenation, or(|), closure(*) и parenthesis для переопределения приоритета по умолчанию.Любая другая операция является просто ярлыком для одной или нескольких основных операций.

Например, ярлык (AB)+ расширяется до (AB)(AB)* и (AB)? до (ε | AB), где ε - пустая строка.Прежде всего, я посмотрел таблицу ASCII и не уверен, какой код обозначен пустой строкой.Это ASCII 0?

Я бы хотел выяснить, как выразить сочетания клавиш ^ и $ как в выражении ^AB или AB$ в основных операциях, но я неуверен, как это сделать.Можете ли вы помочь мне, как это выражается в основах?

Answer 1

Регулярные выражения, как они определены в математике, на самом деле являются генераторами строк , а не шаблонами поиска. Они используются как удобные обозначения для определенного класса наборов строк. (Эти наборы могут содержать бесконечное количество строк, поэтому перечисление всех элементов нецелесообразно.)

В контексте программирования регулярные выражения обычно используются в качестве гибких шаблонов поиска. В математических терминах мы говорим: « найти подстроку целевой строки S, которая является элементом набора, сгенерированного регулярным выражением R ». Этот поиск подстроки не является частью самого регулярного выражения; это похоже на цикл вокруг действительного механизма регулярных выражений, который пытается сопоставить каждую возможную подстроку с регулярным выражением (и останавливается, когда находит совпадение).

В терминах фундаментальных регулярных выражений это похоже на добавление неявного .* до и после вашего паттерна. Когда вы смотрите на это так, ^ и $ просто препятствуют добавлению .* в начале / конце регулярного выражения.

Кроме того, регулярные выражения (которые обычно используются в программировании) на самом деле не являются "регулярными" в математическом смысле; то есть есть много конструкций, которые не могут быть преобразованы в фундаментальные операции, перечисленные выше. К ним относятся обратные ссылки (\1, \2, ...), границы слов (\b, \<, \>), прогнозные / прогнозные утверждения ((?= ), (?! ), (?<= ), (?<! )) и др.

Что касается ε: он не имеет символьного кода, потому что пустая строка является строкой, а не символом. В частности, строка представляет собой последовательность символов, а пустая строка не содержит символов.

Answer 2

^AB может быть выражено как (εAB), то есть за пустой строкой следует AB, а AB$ может быть выражено как (ABε) это AB, за которым следует пустая строка.

На самом деле пустая строкаопределяется как '', это строка длиной 0, поэтому не имеет значения в таблице ASCII.Однако язык программирования C завершает все строки символом ASCII NULL, хотя это не учитывается в длине строки, которую он все равно должен учитывать при выделении памяти.

EDIT As @Мелпомена, указанная в их комментарии, εAB эквивалентна AB, что делает вышеуказанное недействительным.Поговорив с рабочим колледжем, я больше не уверен, как это сделать, и даже если это возможно.Надеюсь, кто-то может придумать ответ.