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

ProgramBox

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

Post author:admin
Запись опубликована:29 апреля, 2023
Post category:Вопросы по программированию

#c #parsing #lexical-analysis

#c #синтаксический анализ #лексический анализ

Вопрос:

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

 int main1;
int main() {}

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

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

1. «Контекстно-зависимый» не имеет ничего общего с тем, сколько вам нужно предвидения. «Контекстно-зависимый» означает, что вы должны изучить другие части входных данных, чтобы выяснить, что означает ваш код. Итак, » x * y; » может означать «умножить x на y » или это может означать «объявить переменную y с типом x* » — вы не можете определить это, не зная, x является ли это значением или типом — это «контекст» в «контекстно-зависимый». Предварительный просмотр — это нечто другое.

2. Достаточно справедливо. Полагаю, я неправильно использовал термин «контекстно-зависимый». Я знаю, что GCC использует анализатор рекурсивного спуска, и мне просто интересно, как они справляются с этой двусмысленностью.

3. Если вы интересуетесь компиляторами, в этой области есть очень богатый набор базовых теорий, и я рекомендую приобрести книгу. «Компиляторы: принципы, техники и инструменты» Ахо, Сети и Ульмана — хороший выбор, даже если вы никогда не работали над компилятором.

Ответ №1:

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

переместите int в стек в качестве токена терминала ТИПА
сдвиг main в стек в качестве идентификатора терминального токена
переместите ( в стек
переместите ) в стек
удалите ( и ) и замените нетерминальным маркером ARGLIST
переместите { в стек
переместите } в стек
удалите их и замените нетерминальным токеном STMT_BLOCK
удалите токены TYPE, IDENTIFIER, ARGLIST и STMT_BLOCK и замените их токеном FUNCTION_DEF.

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

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

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

Я надеюсь, это поможет вам понять, что происходит.

1. У вас интересный момент. Однако я слышал, что GCC в какой-то момент переключился на анализатор рекурсивного спуска. Очевидно, что они ДОЛЖНЫ столкнуться с этой проблемой, верно?

2. @Scott: Так говорит Википедия . Если да, то я бы подумал, что это довольно сложно, как при синтаксическом анализе (((*((int *f())[])((some_expression))))) или что-то в этом роде. Когда вы погружаетесь в скобки, вы не знаете, анализируете ли вы тип, или массив типов, или выражение (и является ли это l-значением или r-значением), поэтому вам приходится как-то отложить это решение.

3. В этом сообщении содержится ряд ошибок. 1: C отсутствует в LR (1). LR (1) строго нечувствителен к контексту, а C чувствителен к контексту. Однако вы можете взломать синтаксический анализатор C, добавив таблицу символов в более простой анализатор (LALR или LL), отложив принятие определенных решений и написав свой токенизатор вручную. 2. Почти никто не использует синтаксические анализаторы LR (1), гораздо чаще встречается LALR (1). Синтаксические анализаторы LR (1) сложнее генерировать. Продолжение…

4. Продолжение: 3: LL — это не то же самое, что рекурсивный спуск. LL — это класс языков, рекурсивный спуск — один из возможных способов анализа языков LL. 4. Машина, используемая синтаксическим анализатором с уменьшением сдвига, называется «pushdown automaton», который не является FSM. Конечный автомат может анализировать только обычные языки, а автомат с принудительным выводом имеет потенциально неограниченное количество состояний. 5: То, что это не LL (1), не означает, что LR (1) достаточно хорош. Некоторые языки являются LL (2) или LL (k) или даже более сложными.

5. @Dietrich: Просто проверяю dragon book, похоже, что называть это FSM не совсем неправильно, потому что PDA — это FSM, который может считывать свой стек так же, как и входные данные. В любом случае, спасибо за ваши разъяснения. (Для меня это было давно.)