Синтаксический анализ (Теория автоматов и формальных языков)

Необходимо выполнить контрольную работу по Теории автоматов и формальных языков из двух заданий.

Задание 1. Синтаксический анализ с использованием конечных автоматов и регулярных выражений

На вход программы подается единственная строка символов. Данная строка задает присваивание переменной значения арифметического выражения в виде ПЕРЕМЕННАЯ = ВЫРАЖЕНИЕ. Выражение может включать: – знаки сложения и умножения («+» и «*»); – круглые скобки («(» и «)»); – константы (например, 5; 3.8; 1e+18, 8.41E-10); – имена переменных (последовательности букв и цифр, начинающиеся с буквы). Программа должна с помощью регулярного выражения построить дерево, соответствующее заданному во входном файле выражению, и выдать для данного выражения: 1) таблицу имен; 2) неоптимизированный код; 3) оптимизированный код.

Задание 2. Синтаксический анализ с использованием КС-грамматик

На вход программы подается описание структур (записей) на выбранном языке (Pascal, C++, C#), а также описание LR(1)-грамматики. Необходимо проверить, является ли описание структур/записей корректным с точки зрения заданной грамматики и не содержатся ли в нем конфликты имен. Таким образом, задание разбивается на две части: 1. Проверка синтаксиса. 2. Проверка семантики. Семантика зависит от выбранного языка, и поэтому ее проверка жестко привязана к анализатору (в данном случае – вашей программе). Грамматика же должна быть универсальной, т. е. должна позволять задавать любые правила для разбора структур/записей (и не только). Например, должны быть доступны изменения: ключевых слов, знаков пунктуации, правил разбора идентификаторов, а также добавление новых языковых конструкций и т. п....

Подробнее текст заданий и требования по составлению отчета в приложенной методичке.