Является ли написание синтаксического анализатора правильным способом решения этой проблемы программирования?

Question

Взгляните на эту проблему программирования.

https://gist.github.com/1083219

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

Вот правила:

1. В протоколе 15 допустимых символов: нижнийсимволы от «а» до «j» и заглавные буквы «Z», «M», «K», «P» и «Q».
2. Каждый отдельный символ нижнего регистра является допустимымсообщение, например, 'a' является действительным сообщением.
3. Если σ является действительным сообщением, то также Zσ.
4. Если σ и τ являются действительными сообщениями, то таковы также и Mστ, Kστ, Pστи Qστ.
5. Все остальные сообщения недействительны.

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

Выходные данные состоят из одной строки на каждое потенциальное сообщение, за которым следует «VALID», если сообщение действительно, и «INVALID».если он недействителен.

Ниже приведен пример выходных данных.

Input    Output
Qa Zj    Qa INVALID
MZca     Zj VALID
Khfa     MZca VALID
         Khfa INVALID

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

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

Answer 1

Я думаю, вы должны сделать это с помощью довольно простой рекурсивной строковой функции f:

1. Посмотрите на первый символ строки
2. Если этострочная буква, вернуть остаток строки
3. Если это Z, вернуть f(the rest of the string)
4. Если это M, K, P, or Q, вернуть f(f(the rest of the string))
5. В противном случае вернуть всю строку

Затем обернуть это в функцию g, которая возвращает true, если f возвращает пустую строку, и false в противном случае.Сделайте это для каждого сообщения.

Это работает, потому что описанная вами грамматика является простой древовидной структурой: любой узел с двумя дочерними элементами равен M, K, P, or Q, любой узел с одним дочерним элементом - Z, а любой лист - строчная буква.f всегда использует ровно один узел в дереве, возвращает остаток дерева (включая братьев и сестер) и возвращает непустую строку в искаженном дереве.