我正在尝试在Haskell中创建一个下推自动检查。基本上,一个函数
(start_state, final_state, set_of_rules) and a string
. 它应该会回来
Accepted
如果字符串被此PDA接受,并且
Rejected
否则。
这就是我目前为止所拥有的:
type Transition = ((Int,String,String),(Int,String))
type Configuration = (Int,String,String)
type PDA = (Int,[Int],[Transition])
data Result = Accept | Reject | Jj deriving Show
run :: PDA -> String -> [Result]
run (ss,fs,tr) xs = runs (ss,fs,tr) (ss,xs,"")
runs :: PDA -> Configuration -> [Result]
-- When string and stack empty accept
runs _ (_,[],[]) = [Accept]
-- If string empty and stack not empty, reject
runs _ (_,[],_) = [Reject]
runs z@(ss,fs,tt) (cs,(x:xs),st) = [runs z (d,xs,e) | m@((a,b,c),(d,e)) <- [xf | xf@((a,b,c),(d,e)) <- tt, a == cs, b == [x]]]
最后一行是我的逻辑断开的地方,我想解释一下:
[xf | xf@((a,b,c),(d,e)) <- tt, a == cs, b == [x]]
这需要一组规则(TT),并列出所有可能使用的规则,其中当前状态(CS)和字符串头匹配。这非常有效,列出了所有可能的动作。我想获取这个列表中的每个元素,并再次运行这个函数。当我到达我的基本情况时,我返回基于堆栈状态的接受或拒绝。
我想看到的是一张清单
Reject
因为我还没有真正使用堆栈。
我不断地得到
Couldn't match type â[Result]â with âResultâ
总是编译错误,我就是无法修复它。真的很感谢你的帮助
