Синтаксический анализатор Конечного автомата

Для синтаксического анализа я всегда стараюсь использовать то, что уже доказано, что работает: ANTLR с ANTLRWorks , что очень помогает при разработке и тестировании грамматики. Вы можете сгенерировать код для C / C ++ (и других языков ), но вам необходимо создать среду выполнения ANTLR для этих языков.

Конечно, если вы найдете flex или bison более простыми в использовании, вы тоже можете их использовать (я знаю, что они генерируют только C и C ++, но я могу ошибаться, так как я этого не делал) не пользуюсь ими какое-то время).

Есть два этапа анализа входного потока текста для синтаксического анализа:

Лексический анализ: Здесь ваш входной поток разбивается на лексические единицы. Он просматривает последовательность символов и генерирует токены (аналогично слову в устных или письменных языках). Конечные автоматы очень хороши в лексическом анализе при условии, что вы приняли правильное проектное решение о лексической структуре. Исходя из приведенных выше данных, отдельными лексемами могут быть такие вещи, как ключевые слова (например, «глобальный»), идентификаторы (например, «побитовый», «ИСТОЧНИКИ»), символические токены (например, «{« »}», «.», «/» ), числовые значения, escape-значения (например, "\ n") и т. д.

Синтаксический / грамматический анализ: После создания последовательности токенов (или, возможно, пока вы это делаете) вам необходимо иметь возможность проанализируйте структуру, чтобы определить, соответствует ли последовательность токенов вашему языковому дизайну. Обычно для этого нужен какой-то парсер, хотя, если структура языка не очень сложна, вы можете сделать это с помощью конечного автомата. В общем (и поскольку вам нужны структуры вложенности в конкретном случае) вам нужно будет использовать один из методов, описанных Кеном Блумом.

Итак, в ответ на ваши вопросы:

Должен ли я использовать перечисление или абстрактный класс + производные для моих состояний?

Я обнаружил, что для небольших токенизаторов подходит матрица значений состояния / перехода, что-то вроде next_state = state_transitions [current_state] [current_input_char] .В этом случае next_state и current_state являются некоторыми целочисленными типами (включая, возможно, перечислимый тип). Ошибки ввода обнаруживаются при переходе в недопустимое состояние. Конец токена идентифицируется на основе идентификации состояния допустимых конечных состояний без допустимого перехода в другое состояние с учетом следующего входного символа. Если вас беспокоит космос, вы можете вместо этого использовать вектор карт. Создание классов состояний возможно, но я думаю, что это, вероятно, усложняет задачу, чем вам нужно.

При чтении списка НЕ ​​нужно игнорировать \ n.

Вы можете создать токен с именем "\ n" или более общий escape-токен (идентификатор, которому предшествует обратная косая черта. Если вы говорите об идентификации разрывов строк в исходном тексте, то это просто символы, которые вам нужно создавать переходы для в вашей матрице переходов состояний (однако следует помнить о различиях между разрывами строк в Unix и Windows; вы можете создать автомат, который будет работать с любым из них).

Достаточно ли простых состояний перечисления для многоуровневого синтаксического анализа (области видимости в пределах границ {... {...} ...}) или для этого потребуются хакерские реализации?

Здесь вам понадобится грамматический или выталкивающий автомат, если вы не можете гарантировать, что вложенность не превысит определенный уровень . Даже в этом случае это, вероятно, сделает ваш конечный автомат очень сложным.

Вот черновые положения, которые я имею в виду: ...

См. Мои комментарии по лексическому и грамматическому анализу выше.