Как вы анализируете контекстно-зависимый C-код? - PullRequest
Новая
       57

Как вы анализируете контекстно-зависимый C-код?

3 голосов
/ 13 мая 2011

Одна проблема, с которой я столкнулся, заключалась в том, что C должен быть контекстно-зависимым и не может быть проанализирован одним токеном lookahead.Например, 

int main1;
int main() {}

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

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

1 Ответ

8 голосов
/ 13 мая 2011

Вы должны прочитать о парсерах LR или shift-lower.Они собирают дерево разбора снизу вверх.В случае функции main она выглядит следующим образом:

  • сдвиг int в стек в качестве токена терминала TYPE
  • сдвиг main в стек в качестве ИДЕНТИФИКАТОРАтерминальный токен
  • сдвиг ( в стек
  • сдвиг ) в стек
  • удаление ( и ) и замена на ARGLIST non-терминальный токен
  • сдвиг { в стек
  • сдвиг } в стек
  • удалить их и заменить на нетерминальный токен STMT_BLOCK
  • удалите токены TYPE, IDENTIFIER, ARGLIST и STMT_BLOCK и замените их токеном FUNCTION_DEF.

Конечно, каждый раз, когда выполняется замена, он создает новый фрагмент дерева разбора и присоединяет егона новый токен.(Я составил эти имена токенов.)

Он работает под управлением конечного автомата, который распознает шаблон токенов в стеке и вместе со следующим (единственным) токеном ввода решает, следует ли сдвигатьследующий токен или примените одно из правил грамматики, чтобы свести группу токенов в стеке в один.FSM построен генератором синтаксического анализатора из списка правил грамматики.

Он называется LR, потому что он читает входные токены слева, но применяет правила грамматики справа.Это отличается от LL, или рекурсивного спуска, который применяет грамматические правила слева.Паскаль является языком LL (1).C не является LL (1), поэтому требует анализатор LR (1).Это позволяет C, например, вставлять практически все в вложенные скобки, не путая синтаксический анализатор.

Надеюсь, это поможет вам увидеть, что происходит.

...