Здравствуйте, VjcheslavV, Вы писали:

VV>а DFA они сразу строят или через недетерминированный автомат?

Все зависит от точки зрения. Не факт, что там будет явно модель "недетерминированного автомата". Но, с другой стороны, сама по себе исходная грамматика эквивалентна недетерминированному автомату. Так что в реализации будет что-то очень похожее на алгоритм Томсона. Плюс дополнительные специфические вещи. Например, lex/flex поддерживают "состояния разбора", в которых применяются разные наборы правил. Самый простой пример — разбор символов внутри строки. В результате получается композиция из нескольких недетерминированных автоматов и каждый детерминируется отдельно.

VV>в алгоритме Томсана неудобно то что он под конец может возвратить несколько состояний

Это не проблема алгоритма, это проблема исходной грамматики. Ввод, приводящий в такое состояние, является валидным префиксом или выводом (зависит от того, промежуточные или конечные состояния НКА входят в состояние ДКА) сразу нескольких правил исходной грамматики. Более того, по получившемуся ДКА можно строить примеры ввода, которые будут соответсвовать сразу нескольким правилам исходной грамматики.

VV>Не знаите как с этим боротся? темболее не угодаешь когда его завершить...

Так в интернете все есть (5-я глава на странице). Если в ДКА-правиле только промежуточные состояния исходного НКА, вообще ничего делать не надо. Если в ДКА только конечные состояния, "первое" из НКА-состояний (входящих в текущее состояние ДКА) объявляется результатом разбора. Первое — это первое по тексту определения для lex. Такое поведение используется для ключевых слов, которые также обычно попадают под правила для идентификаторов. Самый интересный случай, когда в ДКА-состояние входят как конечные так и промежуточные состояния НКА. В этом случае текущая позиция и состояние отмечаются, как "возможный вывод" и разбор продолжается дальше. Когда дальше двигаться нельзя, берется последний "возможный вывод" (т.е. самую длинную последовательность ввода, подходящую под какое-либо правило), объявляется результатом. Текущая позиция разбора тоже возвращается назад, туда, где было встречено правило. В теории, это может приводить к квадратичной сложности разбора. Например, если есть правила shortId := [abc], longId := [a].*[b] (т.е. короткий идентификатор — символ, длиннй — несколько символов, где первый a и последний b). В этом случае разбор последовательности aaa...aaaa должен проийти ее всю (вдруг там b встретится?) и потом трактовать первый символ как shortId. В принципе, это можно оптимизировать до O(len*states) где len — длина ввода, states — количество состояний автомата. Но на практике так вряд ли кто-то делает. Для типичной грамматики возвраты скорее всего будут не нужны. А если и нужны, то очень короткие (вообще ограниченные константой).