Наиболее распространенным правилом является «максимальный жевание», при котором всегда выбирается максимально длинный токен.
В общем, алгоритм сканирования одного токена с использованием DFA выглядит следующим образом: (Для токенизации ввода этот алгоритм повторяется до тех пор, пока не будет достигнут конец ввода, при этом каждое сканирование начинается с курсора ввода, оставленного предыдущим сканированием. )
Установите состояние DFA в начальное состояние. Затем для каждого входного символа последовательно:
если в DFA есть переход на символ, перейти в указанное состояние. Если это состояние является принимающим, запишите текущий курсор ввода и номер состояния.
в противном случае перемотать ввод на последнюю записанную позицию принятия и вернуть записанный номер состояния.
Здесь номер состояния принятия используется для указания того, какой маркер был обнаружен. На практике принято связывать каждое состояние принятия с кодом токена, потому что некоторые типы токенов могут иметь более одного состояния принятия.
Не всегда необходимо использовать алгоритм поиска с возвратом, описанный выше. В некоторых случаях анализ DFA покажет, что последнее принимающее состояние всегда находилось в непосредственно предшествующей входной позиции. Однако многие языки требуют возврата.
Например, язык, в котором . и ... являются токенами, но не .. (например, C), должен откатиться на входе ..1, который должен быть обозначен как ., .1. При токенизации этого ввода первое сканирование примет первое ., продолжится со вторым . (которое не является принимающим состоянием), а затем не сможет найти переход на входе 1. Затем он сообщит, что нашел . (записанный принятый токен), и сбросит курсор ввода на позицию второго символа, чтобы при следующем сканировании был виден токен .1.
person
rici
schedule
18.10.2017
