(F) Лекс, как мне сопоставить отрицание?

(TL;DR: пролистайте вниз, чтобы найти практический ответ.)

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

Случай """, по крайней мере, не так уж сложен.

Во-первых, давайте проясним, что мы пытаемся сопоставить.

Строго говоря, не """ будет означать любую строку, кроме """. Но это будет включать, например, x""".

Поэтому может возникнуть соблазн сказать, что мы ищем любую строку, не содержащую """. (То есть, инверсия .*""".*). Но и это не совсем правильно. Типичное использование заключается в токенизации ввода, например:

"""This string might contain " or ""."""

Если мы начнем после начального """ и найдем самую длинную строку, не содержащую """, мы найдем:

This string might contain " or "".""

тогда как мы хотели:

This string might contain " or "".

Получается, что нам нужна любая строка, не оканчивающаяся на " и не содержащая """, которая на самом деле является конъюнкцией двух инверсий: (~.*" ∧ ~.*""".*)

Для этого (относительно) легко создать диаграмму состояний:

(Обратите внимание, что единственное различие между приведенным выше и диаграммой состояний для любой строки, которая не содержит """, заключается в том, что на этой диаграмме состояний все состояния будут допускающими, а на этой диаграмме состояния 1 и 2 недопустимыми.)

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

([^"]|\"([^"]|\"[^"]))*

Эта модель будет работать для любой простой строки, но она немного сложнее, когда строка представляет собой не просто последовательность одного и того же символа. Например, предположим, что мы хотим сопоставить строки, оканчивающиеся на END, а не на """. Наивное изменение приведенного выше шаблона приведет к:

([^E]|E([^N]|N[^D]))*   <--- DON'T USE THIS

но это регулярное выражение будет соответствовать строке

ENENDstuff which shouldn't have been matched

Нам нужна диаграмма реального состояния:

и один из способов записать это как регулярное выражение:

([^E]|E(E|NE)*([^EN]|N[^ED]))

Опять же, я произвел это, отследив все пути, чтобы оказаться в состоянии 0:

[^E] stays in state 0
E    in state 1:
     (E|NE)*: stay in state 1
     [^EN]: back to state 0
     N[^ED]:back to state 0 via state 2

Это может быть много работы, как для создания, так и для чтения. И результаты подвержены ошибкам. (Формальная проверка проще с диаграммами состояний, которые малы для этого класса задач, а не с регулярными выражениями, которые могут стать огромными).

Практичное и масштабируемое решение

Практические наборы правил Flex используют начальные условия для решения подобных проблем. Например, вот как вы можете распознать строки Python в тройных кавычках:

%x TRIPLEQ
start \"\"\"
end   \"\"\"
%%

{start}        { BEGIN( TRIPLEQ ); /* Note: no return, flex continues */ }

<TRIPLEQ>.|\n  { /* Append the next token to yytext instead of
                  * replacing yytext with the next token
                  */
                 yymore();
                 /* No return yet, flex continues */
               }
<TRIPLEQ>{end} { /* We've found the end of the string, but
                  * we need to get rid of the terminating """
                  */
                 yylval.str = malloc(yyleng - 2);
                 memcpy(yylval.str, yytext, yyleng - 3);
                 yylval.str[yyleng - 3] = 0;
                 return STRING;
               }

Это работает, потому что правило . в начальном условии TRIPLEQ не будет соответствовать ", если " является частью строки, соответствующей {end}; flex всегда выбирает самое длинное совпадение. Его можно было бы сделать более эффективным, используя [^"]+|\"|\n вместо .|\n, потому что это привело бы к более длинным совпадениям и, следовательно, к меньшему количеству вызовов yymore(); Я не написал это так выше просто для ясности.

Эту модель гораздо легче расширять. В частности, если бы мы хотели использовать <![CDATA[ в качестве начала и ]]> в качестве конца, нам нужно было бы только изменить определения

start "<![CDATA["
end   "]]>"

(и, возможно, оптимизированное правило внутри начального условия, если используется предложенная выше оптимизация.)