Code golf: Solve a Knights and Knaves logic problem by parsing English
Python, 491 chars

Works by converting each line to a Python expression, and eveluating it.
The knave and knight are evaluated as 0 and 1. For the two people, we try both options.
For example, Joe: Steve is a knave becomes Joe==(Steve==knave). This way, if Joe is a knave, the result is true only if he's lying.
You get ugly errors when it's impossible or undecided. If impossible, r[0] is an index error, because r is empty. If undecidable, concatenating r[1:] to a list of strings causes trouble.

import sys
def p():
    a=s.pop(0)
    try:return{"both":"(%s*%s)","either":"(%s|%s)","neither":"(1-(%s|%s))"}[a.lower()]%(p(),p())
    except KeyError:r=s[2];del s[:4];return"(%s==%s)"%((a,m)[a=="I"],r)
x=[];w=[]
for l in sys.stdin:
    m,l=l.split(":");w+=[m]
    for s in l.split("."):
        s=s.split()
        while s:x+=["%s==%s"%(m,p())]
k=("knave","knight")
r=[a for a in[{w[0]:z,w[1]:1-z}for z in(0,1)]if all(eval(l,{k[0]:0,k[1]:1},a)for l in x)]
print"\n".join(x+" is the "+k[r[0][x]]+"."for x in w+r[1:])