)Любое предложение - набор букв. Для того, чтобы определить части речи в предложении, тебе нужно знать значение для каждого слова, так и с программой. Для нее нужны словари, где должны быть указаны все известные слова, а так же алгоритмы их склонения, словарь глаголов, местоимений и прочее. В общем написание программы будет заключаться в основном в составлении словарей, а её логика это просто поиск слов в этих словарях.
Регулярные выражения тут не причем, они служат для поиска "выражения" в строке, тебе же нужно наоборот, разбивать строку на слова, а слова искать в "выражениях" (читай словарях)