Курсовая работа: Разработка программы-компилятора
Знаки, эквивалентные числам, начинающимся с 1 (1, 10, 100, 1000), могут использоваться от одного до 3 раз. Знаки, эквивалентные числам, начинающимся с 5 (5, 50, 500) могут использоваться только 1 раз. Таким образом, чтобы образовать число 4, нужно из 5 вычесть 1 (IV), а чтобы образовать число 6, нужно прибавить 1 к 5 (VI).
В соответствии с приведёнными правилами, сформируем ряд ограничений для автомата-распознавателя:
Символ X может встречаться в начале строки от 1 до 3 раз подряд (см. правило 3).
Символ V может встречаться не более 1 раза в начале строки и после 1 или более символов X (см. правило 3).
Символ I может встречаться от 1 до 3 раз подряд в начале строки, а также в конце правильной строки, образованной символами X и V (см. ограничения 1 и 2, правило 3).
Символ X может встречаться в конце строки 1 раз после символа I, если перед последним находятся только символы X или ничего (иначе будет нарушено правило 2 - неизвестно, к какому символу будет относиться символ I).
Символ V может встречаться в конце строки 1 раз после символа I, если перед последним находятся только символы X (аналогично ограничению 4).
рис.4. Автомат для распознавания римских констант
Состояния автомата:
S - начальное состояние;
Sg - промежуточное состояние, соответствующее распознаванию знака константы.
1 - промежуточное состояние, соответствующее распознаванию символа X.
2 - промежуточное состояние, соответствующее распознаванию символа V.
3 - промежуточное состояние, соответствующее распознаванию символа I.
4 - конечное состояние, соответствующее ошибке пр. выделении римской константы.
5 - промежуточное состояние, соответствующее распознаванию строки XX.
6 - промежуточное состояние, соответствующее распознаванию строки XXX.
7 - промежуточное состояние, соответствующее распознаванию символа I после V, XV, XXV или XXXV.
8 - промежуточное состояние, соответствующее распознаванию символа X после I, XI, XXI или XXXI.
9 - промежуточное состояние, соответствующее распознаванию символа V после I, XI, XXI или XXXI.
10 - промежуточное состояние, соответствующее распознаванию символа I после правильной строки, заканчивающейся на I.
11 - промежуточное состояние, соответствующее распознаванию символа I после правильной строки, заканчивающейся на II.
В конечное состояние автомата, соответствующее распознаванию правильной римской константы, можно перейти из любого состояния, кроме Sg и 4, как только наступит конец лексемы.
2.3.4 Объединённый автомат
Объединённый автомат является соединением приведённых выше автоматов при общем начальном состоянии S. Все состояния и входные сигналы останутся теми же.
2.4 Разработка алгоритма и программы лексического анализа
Непосредственно лексический анализ представляет собой 2 этапа: выделение лексем и их распознавание. На экран выводятся таблицы констант, идентификаторов, терминальных символов и кодов лексем. Все таблицы сохраняются в файлы на диске.
После завершения лексического анализа становится возможным выполнить синтаксический анализ.