У меня есть самопальный недетерминированный конечный автомат, на Delphi 6 написан. Что-то типа YACC, но вместо формирования парсера для некоторого языка, просто вызывает процедуры для конечных состояний на простеньком языке типа Форта.
До конца так и не дописал (пишу лишь редкими "набегами"), но вообще, он как-то работает. Вот и думаю скинуть-не скинуть исходник? С одной стороны не доделан, с другой, фиг его знает доделаю ли вообще (я ж не Глушков всё таки).
К тому же, мож и такой кому сойдёт?
Конструктивно он из состоит из простенькой программы, в которой можно открыть и "запустить" C-ишный файл. При этом в правой части окошка отображается то, что он там "думает" и делает. Выводимая информация дублируется в log-файл. Собственно это нужно потому, что ошибки refort (как я его обозвал) отлавливать ещё не умеет.
Практически вся основная программа умещается в одной библиотеке+ещё одна с процедурами для работы со строковыми переменными.
Программы для рефорта пишутся в двух файлах. Они там есть с расширениями lst (с описаниями грамматики) и prc (с описанием процедур). В былые времена, когда автомат был ещё детерминированным, он мог простенькие программы на Си компилировать. Файлы с правилами вплоть до rules54 были для него и приведены лишь для примера. rules-alt - это то, что он (теперь уже не детерминированный) использует сейчас. Фактически, сейчас, он не может толком скомпилировать одну простейшую процедуру из form5.c.
lst-файлы состоят из пар строк примерно такого вида:
`функция АБВ ( `внутренности )
"" "проц1,проц2" ",проц3" ""
здесь то, что помечено апострофом "`" является нетерминалом, то есть правилом для подстановок. Остальное - обязательные символы входного потока. Во второй строке (в кавычках) процедуры, исполняемые сразу при встрече символа (та, что до запятой) и после возврата из рекурсивных нетерминалов (та, что после запятой). Второй случай нужен для обработки правосторонних правил.
Стоит заметить, что в отличие от yacc подстановки осуществляются не префиксно, а постфиксно. Например, нужно создать список запятых.
для yacc:
zap: zap , | ;
для refort:
`zap , `zap_opt
`zap_opt `zap
`zap_opt `empty
Если попытаться написать нетерминал сразу после его объявления (н: `zap `zap), это приведёт к зацикливанию процедуры, составляющей список подстановок. Ещё из написанного видно два отличия (ещё пара недоработок):
1. приходится обязательно повторно писать названия нетерминалов (`zap_opt написан дважды), тогда, как у yacc можно поставить "|".
2. символ возможного пропуска пишется специальным оператором `empty. Тогда, как в yacc лишь пустота.
Кстати, есть и другие спец. операторы. `ident, например допускает любое слово в качестве подстановки.
Запускаемые из кавычек процедуры, находятся в prc-файлах. Формат процедуры простейший:
название x x x x x x x x x
То есть вся процедура должна быть в одной строке. Принцип работы тот же, что и в Форт-е имена переменных (они отмечены символом @ ) сохраняются в стек. Команды (например = ) забирают нужное число переменных с верхушки стека, а результат опять помещает на вершину. Например:
add_abv @tmpstr "" = 'абв' +
поместит на верх стека переменные tmpstr и пустую строку. Очистит tmpstr приравниванием и вернёт её же в стек. Потом + добавить к ней надпись "абв".
Стоит заметить, что все переменные refort-а - символьные. Для преобразования в число надо ставить $. Например:
summ @rez 4 $ 2 $ + =
сложит и приравняет к rez
полностью все команды я не помню (хоть их там как кот наплакал), часть указана в table.txt
Вот практически и всё, остальное - это лишь множество нюансов и недоделок. Плюс, непосредственно, вопросы связанные с разными типами грамматик и теорией компиляции. Они здесь не рассмотрены, но если надо, можно и пояснить.