похоже, именно то, что вы предлагаете в своем ответе, верно?

ою простой сканер. Предположим, у меня есть следующие токены, определенные для моего языка:

!, !=, !==, <, <<, {

Теперь я могу указать их с помощью регулярных выражений, поэтому:

!=?=? | { | <<?

Тогда я использовалhttp://hackingoff.com построить NFA и DFA. Теперь каждая машина может определить, введен ли ввод на языке регулярных выражений или нет. Но моя программа - это последовательность токенов, а не один токен:

!!=!<!==<<!{

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

 melpomene18 окт. 2017 г., 12:14
Если вы не говорите о коде, то я не знаю, что вы подразумеваете под «подходом».
 Max Koretskyi aka Wizard18 окт. 2017 г., 12:05
@ melpomene, мой вопрос: что делать с этими машинами? как разобрать фактическую строку из многих токенов?
 Max Koretskyi aka Wizard18 окт. 2017 г., 12:14
@ melpomene, подход, я нигде не упоминаю код
 melpomene18 окт. 2017 г., 12:09
Вы просите нас написать код для вас?
 melpomene18 окт. 2017 г., 12:04
Что именно вы спрашиваете?

Ответы на вопрос(1)

Решение Вопроса

при котором всегда выбирается максимально длинный токен.

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

Установите состояние DFA в начальное состояние. Затем для каждого входного символа в последовательности:

если DFA имеет переход на персонажа, перейдите в указанное состояние. Если это состояние является принимающим, запишите текущий курсор ввода и номер состояния.

в противном случае перемотайте вход до последней записанной позиции принятия и верните номер записанного состояния.

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

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

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

 Max Koretskyi aka Wizard18 окт. 2017 г., 16:53
@rici, спасибо большое. Я нашел следующее:Dfa должен работать, пока не достигнет точки, в которой текущее состояние, S, не имеет исходящего перехода на следующем символе. На этом этапе реализация должна решить, какому регулярному выражению оно соответствует. Если S является принимающим состоянием, тогда dfa нашел слово в языке и должен сообщить слово и его синтаксическую категорию.
 sepp2k18 окт. 2017 г., 16:09
На самом деле я однажды видел статью об алгоритме, который может выполнять основанное на регулярном выражении токнирование максимального жука в O (n) (то есть без возврата). Это просто не используется на практике.
 rici18 окт. 2017 г., 16:33
@ sepp2k: если у вас есть ссылка, я бы хотел ее увидеть. Я не верю, что O (N) lexing вообще возможен в постоянном пространстве, но я был бы счастлив, если бы оказался неправ. (Если вы ослабите ограничение пространства, это должно быть выполнимо, но это гораздо менее интересно.) На практических языках, с добавлением шаблонов для таких вещей, как неопределенные строки и комментарии, обычно можно ограничить возврат к O ( 1) символы, в этом случае токенизация O (N). Поэтому мотивация использовать более сложный алгоритм ограничена.
 Max Koretskyi aka Wizard18 окт. 2017 г., 16:53
В противном случае, если dfa прошел через одно или несколько принимающих состояний на своем пути к S, распознаватель должен выполнить резервное копирование в самое последнее такое состояние. Эта стратегия соответствует самому длинному действительному префиксу во входной строке. Если он никогда не достиг состояния принятия, то ни один префикс входной строки не является допустимым словом, и распознаватель должен сообщить об ошибке.
 Max Koretskyi aka Wizard18 окт. 2017 г., 16:54
похоже, именно то, что вы предлагаете в своем ответе, верно?

Ваш ответ на вопрос