Конструкция компилятора - Почему некоторым токенам требуется конечное состояние с возвратом назад?

Question

Итак, я изучаю конструкцию компилятора для экзамена, но мне кажется, что я чего-то не понимаю.

Давайте предположим следующий набор терминалов:

T = {:, *, =, (, ), <, >, {, }, [a..z], [0..9]}

И набор принятых токенов (l указывает на букву, а d указывает на цифру):

A = { l(l|d)* , (d)+ , { (anything)* } , : , := , < , <= , <> , > , >= , ( , (* , * , *) } 

Вот диаграмма перехода состояний:

Теперь я понимаю, что номер состояния 20 нуждается в возврате, потому что:

• A ( может прийти, но за ним может следовать *.
• A : может прийти, но за ним может последовать =.
• A < может прийти, но за ним может следовать = или >.
• A > может прийти, но за ним может последовать =.

А как быть с состояниями 3 , 5 и 11 ? зачем нам их возвращать?

Answer 1

Похоже, «возврат» означает, что вы прочитали персонажа, но не использовали его.Таким образом, для состояния 3 мы использовали l и, возможно, некоторые l и d, а затем мы получаем некоторый символ, который не является ни тем, ни другим;этот символ завершает правило l(l|d)*, но затем все еще нуждается в обработке.

Сравните это с состоянием 7, где мы читаем символ }, чтобы завершить правило, и мы израсходовали } так что нам не нужно «возвращаться».

Это объяснение согласуется с состояниями 3, 5 и 20, но я не понимаю, почему 11 нужно возвращаться назад.