如何在 haskell 中显示派生树?
how can i show a derivation tree in haskell?
我正在做一个构建 while 语言派生树的练习。我对 while 语言的实现是由代数数据类型组成的,例如 "Aexp"(算术表达式)"Bexp"(布尔表达式)和 "Stm"(语句):
type Var = String
data Aexp = N Integer
| V Var
| Add Aexp Aexp
| Mult Aexp Aexp
| Sub Aexp Aexp
deriving (Show, Eq)
data Bexp = TRUE
| FALSE
| Eq Aexp Aexp
| Le Aexp Aexp
| Neg Bexp
| And Bexp Bexp
deriving (Show, Eq)
data Stm = Ass Var Aexp
| Skip
| Comp Stm Stm
| If Bexp Stm Stm
| While Bexp Stm
| Repeat Stm Bexp
deriving Show
在这些代数数据类型之后,我创建了更多的代数数据类型来表示while语言程序的推导树
type State = Var -> Z
data Config = Inter Stm State -- <S, s>
| Final State -- s
data Transition = Config :-->: State
data DerivTree = AssNS Transition
| SkipNS Transition
| CompNS Transition DerivTree DerivTree
| IfTTNS Transition DerivTree
| IfFFNS Transition DerivTree
| WhileTTNS Transition DerivTree DerivTree
| WhileFFNS Transition
| RepeatTTNS Transition
| RepeatFFNS Transition DerivTree DerivTree
如何展示这种推导树??
<z:=x, s> -> s' <x:=,s1> -> s''
----------------------------------
<z:=x; x:=y,s> -> s'' <y:=z,s''> -> s'''
------------------------------------------------------
<z:=x; x:=y; y:=z, s> -> s'''
每个构造函数的预期值如下所示:
这是一个使用 boxes
包生成类似派生树的东西的简单示例。您应该能够毫不费力地使其适应您的需要——通过生成 Tree String
,或者使用 pp
中的想法直接从您的派生树生成 Box
. (我在这里选择使用 Tree String
而不是您的类型,主要是为了避免必须找出具有大量构造函数的数据类型的所有漂亮打印细节。)
import Data.Tree
import Text.PrettyPrint.Boxes
pp :: Tree String -> Box
pp (Node here [] ) = text here
pp (Node here children) = vcat center1 [premises, separator, conclusion]
where
premises = hsep 4 bottom (map pp children)
conclusion = text here
width = max (cols premises) (cols conclusion)
separator = text (replicate width '-')
sampleTree :: Tree String
sampleTree = Node "<z:=x; x:=y; y:=z, s> -> s'''"
[Node "<z:=x; x:=y,s> -> s''"
[Node "<z:=x, s> -> s'" []
,Node "<x:=,s1> -> s''" []
]
,Node "<y:=z, s''> -> s'''" []
]
这是 ghci 中的示例 运行:
*Main> printBox (pp sampleTree)
<z:=x, s> -> s' <x:=,s1> -> s''
----------------------------------
<z:=x; x:=y,s> -> s'' <y:=z, s''> -> s'''
---------------------------------------------------------
<z:=x; x:=y; y:=z, s> -> s'''
我正在做一个构建 while 语言派生树的练习。我对 while 语言的实现是由代数数据类型组成的,例如 "Aexp"(算术表达式)"Bexp"(布尔表达式)和 "Stm"(语句):
type Var = String
data Aexp = N Integer
| V Var
| Add Aexp Aexp
| Mult Aexp Aexp
| Sub Aexp Aexp
deriving (Show, Eq)
data Bexp = TRUE
| FALSE
| Eq Aexp Aexp
| Le Aexp Aexp
| Neg Bexp
| And Bexp Bexp
deriving (Show, Eq)
data Stm = Ass Var Aexp
| Skip
| Comp Stm Stm
| If Bexp Stm Stm
| While Bexp Stm
| Repeat Stm Bexp
deriving Show
在这些代数数据类型之后,我创建了更多的代数数据类型来表示while语言程序的推导树
type State = Var -> Z
data Config = Inter Stm State -- <S, s>
| Final State -- s
data Transition = Config :-->: State
data DerivTree = AssNS Transition
| SkipNS Transition
| CompNS Transition DerivTree DerivTree
| IfTTNS Transition DerivTree
| IfFFNS Transition DerivTree
| WhileTTNS Transition DerivTree DerivTree
| WhileFFNS Transition
| RepeatTTNS Transition
| RepeatFFNS Transition DerivTree DerivTree
如何展示这种推导树??
<z:=x, s> -> s' <x:=,s1> -> s''
----------------------------------
<z:=x; x:=y,s> -> s'' <y:=z,s''> -> s'''
------------------------------------------------------
<z:=x; x:=y; y:=z, s> -> s'''
每个构造函数的预期值如下所示:
这是一个使用 boxes
包生成类似派生树的东西的简单示例。您应该能够毫不费力地使其适应您的需要——通过生成 Tree String
,或者使用 pp
中的想法直接从您的派生树生成 Box
. (我在这里选择使用 Tree String
而不是您的类型,主要是为了避免必须找出具有大量构造函数的数据类型的所有漂亮打印细节。)
import Data.Tree
import Text.PrettyPrint.Boxes
pp :: Tree String -> Box
pp (Node here [] ) = text here
pp (Node here children) = vcat center1 [premises, separator, conclusion]
where
premises = hsep 4 bottom (map pp children)
conclusion = text here
width = max (cols premises) (cols conclusion)
separator = text (replicate width '-')
sampleTree :: Tree String
sampleTree = Node "<z:=x; x:=y; y:=z, s> -> s'''"
[Node "<z:=x; x:=y,s> -> s''"
[Node "<z:=x, s> -> s'" []
,Node "<x:=,s1> -> s''" []
]
,Node "<y:=z, s''> -> s'''" []
]
这是 ghci 中的示例 运行:
*Main> printBox (pp sampleTree)
<z:=x, s> -> s' <x:=,s1> -> s''
----------------------------------
<z:=x; x:=y,s> -> s'' <y:=z, s''> -> s'''
---------------------------------------------------------
<z:=x; x:=y; y:=z, s> -> s'''