寻找不同的终端和非终端符号

Question

我目前正在编写两个函数，用于返回出现在给定语法中的所有不同终端的列表。

这是语法的类型：

data Grammar = Grammar [Prod]
               deriving (Show, Eq)

这是我到目前为止：

terminals :: Grammar -> [String]                                          
terminals ts = nub [ x | x <-ts]

nonterms  :: Grammar -> [String]
nonterms nt = nub [ x | x <- nt]

放在函数中的语法就是这样的（3个例子）：

g4 = "P -> true ; P -> false; P -> not P ; P -> P and P"
g5 = "P -> P & N; P -> N; N -> ~ N; N -> t"                                   
g6 = "P -> N & P; P -> N; N -> ~ N; N -> t"

但是，我使用的函数不起作用，因为GHCI无法将预期类型'[String]'与实际类型'Grammar'匹配。

我将介绍无上下文语法（CFG）的基本原则，即无上下文语法

 G = (T,N,P,S)

其中T是终端符号的集合T（“令牌”），非终结符号的集合N，集合的生产集合P和起始符号S.

我怎么能使用/写两个函数来返回给定语法中出现的所有不同终端（分别是非终端）的列表。以上三个语法示例。谢谢。

Answer 1

terminals :: Grammar -> [String]                                          
terminals ts = nub [ x | x <-ts]

你的函数terminals被输入为返回[String]。它的实现返回nub的结果。 nub有类型Eq a => [a] -> [a]，因此它返回[String]，它的输入也必须是[String]。这意味着[ x | x <-ts]必须是[String]类型，然后x必须是String类型。在列表理解中执行x <- ts意味着ts必须是x的任何类型的列表，所以在这种情况下，ts必须是[String]。

现在问题变得明显了。给定函数输出的类型及其实现，ts必须是[String]类型，但是根据函数输入的类型，ts必须是Grammar类型。由于[String]和Grammar是不同的类型，这会导致您看到的类型错误。

旁注：[ x | x <-ts]完全等同于ts，[ x | x <- nt]完全等同于nt。