Какие шаги мне нужно сделать, чтобы выполнить это задание по программированию?

Question

Мне трудно понять, что я должен делать. Единственное, что я понял, мне нужно использовать yacc в файле cminus.y. Я полностью запутался во всем после этого. Может ли кто-то объяснить мне это по-другому, чтобы я мог понять, что мне нужно делать?

ВВЕДЕНИЕ:

Мы будем использовать lex / flex и yacc / Bison для генерации LALR-парсера. Я дам вам файл с именем cminus.y. Это файл грамматики в формате yacc для простого C-подобного языка, называемого C-minus, из книги «Создание компилятора» Кеннета К. Лоудена. Я думаю, что грамматика должна быть достаточно очевидной. У группы Yahoo есть ссылки на несколько описаний того, как использовать yacc. Теперь, когда вы знаете flex, выучить yacc должно быть довольно легко. Единственный базовый тип - int. Int составляет 4 байта. Логические значения обрабатываются как целые, как в C. (На самом деле грамматика позволяет вам объявлять переменную как тип void, но не будем этого делать.) У вас могут быть одномерные массивы. Указателей нет, но ссылки на элементы массива следует рассматривать как указатели (как в C). Язык предусматривает присваивание, IF-ELSE, WHILE, а также вызовы и возвраты функций. Мы хотим, чтобы наш компилятор выводил код сборки MIPS, а затем мы сможем запустить его на SPIM. Для такого простого компилятора без оптимизации IR не должен быть необходим. Мы можем вывести ассемблерный код непосредственно за один проход. Тем не менее, наш первый шаг заключается в создании таблицы символов.

ТАБЛИЦА СИМВОЛОВ:

Мне нравится подход доктора Барретта, который использует множество указателей для обработки объектов разных типов. По сути, элементами таблицы символов являются идентификатор, тип и указатель на объект атрибута. Структура объекта атрибута будет отличаться в зависимости от типа. У нас есть только небольшое количество типов, чтобы иметь дело с. Я предлагаю использовать линейный поиск, чтобы найти символы в таблице, хотя бы для начала. Вы можете изменить его на хеширование позже, если хотите улучшить производительность. (Если вы хотите сохранить в C, вы можете делать динамическое размещение объектов, используя malloc.) Во-первых, вам нужно составить список всех различных типов символов, которые существуют - их немного - и какие атрибуты будут необходимы для каждого. Не забудьте разрешить добавление новых атрибутов, потому что мы еще не охватил все вопросы. Глядя на грамматику, вопрос списков параметров для функций - это то место, где нужно задуматься над дизайном. Я предлагаю больше записей таблицы символов и указателей.

ИСПЫТАНИЯ:

Грамматика правильная, поэтому, принимая существующую грамматику и генерируя анализатор, синтаксический анализатор примет правильную C-минус-программу, но не выдаст никакого вывода, потому что с правилами не связаны фрагменты кода, связанные с правилами. , Мы хотим добавить фрагменты кода, чтобы построить таблицу символов и распечатать информацию, как это происходит. Когда идентификатор объявлен, вы должны напечатать информацию, вводимую в таблицу символов. Если найдено предыдущее объявление того же символа в той же области, должно быть напечатано сообщение об ошибке. Когда на идентификатор ссылаются, вы должны найти его в таблице, чтобы убедиться, что он там есть. Сообщение об ошибке должно быть напечатано, если оно не было объявлено в текущей области. При закрытии области действия должны быть сгенерированы предупреждения для идентификаторов, на которые нет ссылок. Ваш тестовый ввод должен быть правильно сформированной C-минусовой программой, но на этом этапе ничего не произойдет с большинством правил производства.

ОБЗОРНОЕ:

Самый базовый подход имеет глобальную область действия и область действия для каждой объявленной функции. Язык допускает объявления в любом составном операторе, то есть вложение области видимости. Реализация этого потребует какой-либо схемы нумерации области или схемы стекирования. (Укладка работает лучше всего за один проход компилятор, который мы и собираем.)

Answer 1

(отказ от ответственности) У меня нет большого опыта работы с классами компиляторов (как в школьных курсах по компиляторам), но вот что я понимаю:

1) Вы должны использовать упомянутые инструменты для создания парсера, который при заданном вводе сообщит пользователю, является ли ввод правильной программой относительно грамматики, определенной в cminus.y. Я никогда не использовал yacc / bison, поэтому я не знаю, как это делается, но вот что, похоже, делается:

• (входной) некоторый файл, представляющий выходные данные для анализа
• (выходной) ответ некоторого рода, который сообщает, является ли (входной) правильным по отношению к предоставленной грамматике.

2) Также кажется, что вывод должен проверить согласованность переменных (то есть вы не можете использовать переменную, которую вы не объявили так же, как любой другой язык программирования), что осуществляется через таблицу символов. Короче говоря, каждый раз, когда что-то объявляется, вы добавляете это в таблицу символов. Когда вы сталкиваетесь с идентификатором, если он не является одним из идентификаторов языка (например, if или while или for), вы будете искать его в таблице символов, чтобы определить, был ли он объявлен. Если это там, продолжайте. Если это не так - выведите что-то вроде ошибки

Примечание: в пункте (2) имеется упрощенный подход к таблице символов; на самом деле, для них есть нечто большее, чем я только что написал, но это поможет вам начать.

Я бы начал с примеров с yacc - посмотрим, что может сделать yacc и как он это делает. Я предполагаю, что там должна быть какая-то большая таблица примеров с символами, которую вы можете прочитать, чтобы понять больше.

Пример:

Давайте возьмем вход A:

int main()
{
     int a;
     a = 5;
     return 0;
}

И вход B:

   int main()
    {
         int a;
         b = 5;
         return 0;
    }

и предположим, что мы используем синтаксис Си для синтаксического анализа. Ваш синтаксический анализатор должен считать Input A правильным, но должен выкрикнуть «b undeclared» для Input B.