Нахождение различных терминальных и нетерминальных символов - PullRequest
Новая
       18

Нахождение различных терминальных и нетерминальных символов

1 голос
/ 07 марта 2019

В настоящее время я работаю над написанием двух функций, которые будут использоваться для возврата списков всех отдельных терминалов, которые появляются в данной грамматике.

Вот тип для грамматики: 

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]» с фактическим типом «Грамматика».

Я отказываюсь от базовых принципов контекстно-свободных грамматик (CFG), что контекстно-свободной грамматикой является 

 G = (T,N,P,S)

, где T - это набор терминальных символов ("токенов")."), набор N нетерминальных символов, набор P произведений и начальный символ S.

Как я могу использовать / написать две функции, которые могут возвращать списки всех различных терминалов (соответственно, нетерминалов), которыепоявляются в данной грамматике.Три примера грамматики выше.Спасибо.

1 Ответ

2 голосов
/ 07 марта 2019 
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.

...