Синтаксический анализ и синтаксическое дерево - PullRequest
Новая
       81

Синтаксический анализ и синтаксическое дерево

1 голос
/ 21 ноября 2011

Я реализую компилятор для школьного класса, и у меня есть некоторые проблемы с тем, как поступить.Лексический анализ уже сделан.Лексический анализ для меня заключается в том, что у меня есть функция, которая возвращает объекты-токены, а также печатает некоторые ошибки, которые можно проверить во время лексического анализа.

Токен содержит идентификатор, строку (если текущий идентификатор является строкой, если не нулевой), номер (если токен является числом, если не нулевым) и строку, где найден токен.

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

Итак, до конца.Учитель хочет, чтобы мы поняли, что это необходимо?Если это действительно необходимо, каков наилучший способ построения синтаксического дерева?Также я пропускаю что-то, что вызовет у меня проблемы на более поздних стадиях?

1 Ответ

1 голос
/ 21 ноября 2011

По сути, ваш синтаксический анализ в конечном итоге будет представлять собой некую форму конечного автомата . Результатом этого процесса обычно является AST; синтаксический анализ кажется несколько бессмысленным, если вы не храните его результат где-либо.

В то время как существует много различных хорошо известных и устоявшихся алгоритмов для создания таблиц состояний и для реализации фактического процессора , вы можете начать думать как компилятор и определять свои состояния вручную (что возможно для действительно простых языков):

  • В самом начале, какие токены были бы приемлемы? (Начальное состояние)
  • Каждый токен приведет вас в другое состояние и, возможно, заставит вас выполнить операцию по консолидации ваших токенов в абстрактное синтаксическое дерево. (Переходы между состояниями)
  • Я предлагаю трактовать «Конец файла» как специальный токен, возвращаемый токенизатором, чтобы при анализе синтаксиса не требовался какой-либо специальный код для обработки конца файла (просто обычное изменение состояния, связанное с токеном EOF) .

Обратите внимание, что вместо использования таблиц вы также можете использовать функции для представления ваших состояний.

Какой язык вы пытаетесь реализовать?

...