Состояние машины для раскраски синтаксиса

Question

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

current event next action 
IDLE $  COLOR - 
COLOR any -  OnColor() 
COLOR \n IDLE - 

Это будет вызывать действие OnColor() для каждого символа, который находится между «$» и конец линии, поэтому я могу его раскрасить. Конечно же, это может быть автоматически сгенерировано из regexp, но я действительно хочу знать, как это работает до использования тяжелой магии :). Далее идет проблема: если у меня есть правило: (хотите окрасить любую строку текста, который заканчивается с долларом, таблица перехода состояния не очень понятно:

current  event next    action 
IDLE   any -    - 
IDLE   $  DOUND_DOLLAR  - 
FOUND_DOLLAR \n IDLE    OnDollar() 
FOUND_DOLLAR any IDLE    - 

Я могу научить свою государственную машину, чтобы позвонить OnDollar (), если он обнаружил знак «$» в конце строки, но что я могу сделать, чтобы раскрасить текст, который был перед знаком знака доллара? Каковы общие шаблоны для решения таких проблем? Конечно, это будет 1 строка с регулярным выражением, но мне действительно интересно узнать, как такой парсер можно реализовать с помощью конечного автомата, и это вообще возможно.

Answer 1

Чтение «Purple Dragon Book» (sic) кажется, что современные компиляторы и интерпретаторы активно используют «заглядывать вперед» в буфер и накапливают свежий текст, поэтому они могут легко проверить несколько следующих символов и несколько предыдущих символов, чтобы получить точную лексем.

Итак, в моем примере event() необходимо посмотреть следующий и предыдущий символы, чтобы определить тип лексемы, который может быть накоплен.

Answer 2

Если вы ограничены цветом одного символа за раз (т.е. у вас нет буферизации, просмотра, перекрашивания или маркировка capa bility), то это невозможно.

В противном случае, если у вас есть такие возможности, это можно сделать; техника зависит от того, что доступно.

• Повторное окрашивание - есть действие, которое может перекрасить n символов назад. Очевидно, это тривиальное решение.

• Буферизация/маркировка - действие, которое помещает символ в конец буфера/устанавливает именованный знак в источнике, а не пропускает символ. Затем, когда вы позже узнаете, что делать, выполните действие, которое так или иначе выполняет буфер, или сбрасывается с именованного знака. Повторное окрашивание более 1 персонажа с этим несколько усложняется.

• Lookahead - имеет спекулятивные переходы, то есть использовать NFA вместо DFA.

Answer 3

Большинство колоризаторов всегда работают на более крупном блоке, говорят целую линию (что достаточно в большинстве случаев) плюс флаг «утечка», например, для многострочных комментариев. См. Пример Qt Syntax Highlighter для такого API.