Конечный автомат для раскраски синтаксиса - PullRequest
Новая
       6

Конечный автомат для раскраски синтаксиса

1 голос
/ 08 мая 2009

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

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

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

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

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

Ответы [ 3 ]

1 голос
/ 08 мая 2009

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

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

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

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

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

0 голосов
/ 10 мая 2009

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

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

0 голосов
/ 08 мая 2009

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

...