How to map a function over 2 lists? [Syntactic Analysis]

You were very close. All it takes is turning your function to be mapped into a pure function:

Map[lexicalRules[grammarTerminal, #] &, words]
(* {{{D, "the"}}, {{N, "man"}}, {{V, "hit"}}, {{D, "the"}}, {{N, "table"}}} *)

Here's another pure function tutorial.

 Extract[grammarTerminal, Map[Position[grammarTerminal[[All, 2]], #] &, words]]

{{D, "the"}, {N, "man"}, {V, "hit"}, {D, "the"}, {N, "table"}}