формальный подход для обработки текста

Question

Во время интервью кодирования я задал следующий вопрос:

Написать программу, которая подсчитывает количество слов и строк во входном потоке.
Предположим, у вас есть читатель с методом nextChar().

На первый взгляд это выглядит просто. Но тогда вы понимаете, что вам нужно обрабатывать множество состояний, как:

• последовательное слово/линия разделители
• разного истекшее слова условия - слова разделителей или разделитель строки или EOF
• новая строка, которая начинается со словами сепараторов
• и т.д.

на интервью я придумал sortof код с спагетти многие, если-то еще и флаги.

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

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

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

Answer 1

Finite state machines.

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

curState <- NONE 
while(c <- getChar) 
    switch(curState) { 
     case NONE: 
      switch(c) { 
       // .... 
      } 
      break; 
     // ..... 
    } 
} 

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

... не забывайте о кодировке текста! UTF-16, правильно? :)

Вы можете посмотреть в реализации Unix wc утилиты:

• Busybox
• GNU
• DragonFly BSD
• Mac OS X (from FreeBSD)

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