предпочтительный язык / техника для обработки последовательности или анализа

Question

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

проблема:Из возможного набора слов с данным правилом (скажем, слово может быть комбинацией A и X и всегда начинается с X, каждое слово разделено пробелом), вы должны прочитать последовательность слов ипроанализируйте входные данные, чтобы решить, какие слова являются синтетически правильными.В двух словах, это проблемы, связанные с методами синтаксического анализа.Скажем, смоделируйте логику торгового автомата в Java.

Итак, я хочу знать, каковы методы / лучший подход для решения проблем, связанных с анализом входных данных.Например, проблема с обработкой чужого языка в коде Google jam

Проблема кодирования Google в коде

Используем ли мы что-то вроде ANTLR или какую-то библиотеку в Java.Я знаю, что этот вопрос немного общий, но у меня не было другого способа выразить его.

PS: Я не хочу решения, я ищу лучший способ решения таких повторяющихся проблем.

Answer 1

Вы можете использовать JavaCC для сложного анализа.

Для относительного простого анализа и обработки событий я использую перечисления в качестве конечного автомата. esp как push-парсер.

Для очень простого синтаксического анализа вы можете использовать indexOf или split ("") с равно, переключаться или запускается с

Answer 2

Если вы хотите смоделировать логику чего-то, что по сути является автоматизацией конечного состояния, вы можете просто написать код FSA вручную. Это стандартное решение для информатики. Менее очевидный способ сделать это - использовать генератор лексеров (их много) для генерации FSA из описаний допустимых последовательностей событий (в лексер-генераторе они называются «символами», но вы можете обмануть и подставлять события в символы).

Если у вас сложные рекурсивные правила сопоставления, вам понадобится более традиционный синтаксический анализатор. Вы также можете кодировать их вручную, если грамматика не сложна; см. мой ? SO ответ на вопрос "Как создать синтаксический анализатор с рекурсивным спуском" . Если ваша грамматика сложная или она быстро меняется, вам нужно использовать стандартный генератор синтаксического анализатора. Другие ответы здесь предполагают конкретные, но есть из чего выбирать, все, как правило, очень способные.

[FWIW, я применил генераторы синтаксического анализа для распознавания действительных последовательностей транзакций в 1974 году в POS-терминалах TRW в универмаге May Company. Работал довольно хорошо.]

Answer 3

Вы можете использовать ANTLR, что хорошо, это поможет в сложной проблеме, но вы также можете использовать регулярные выражения, например: spilled ("\\ s +").