从OCaml中的语法中删除不可达规则

Question

我是Ocaml的新手，为了完成作业，我必须编写一个函数filter_reachable ，它需要一个语法并返回一个简化的语法和不可达规则。我被允许使用的唯一模块是Pervasives和List模块，没有其他模块。

我的想法是首先列出所有可到达的非终止列表。然后，如果非终结部分位于所有可到达非终结符的列表中，则可以访问规则。所有可访问的规则都放入一个新列表中，并与开始符号配对以创建简化语法。

我的解决方案如下。但它不起作用，我不明白为什么。任何人都可以帮我修复它吗？

let rec member x s= 
match s with 
[]->false 
| y::ys-> (x = y) || member x ys 
    (*the type of a symbol*) 

type ('nonterminal, 'terminal) symbol = 
    | N of 'nonterminal 
    | T of 'terminal 


let rec get_nont sl= 
match sl with 
|[]->[] 
|h::t->match h with 
     |N x-> x::get_nont t 
     |T y-> get_nont t 

let rec get_rea_nont (n,r) = 
n::(match r with 
|[]->[] 
|h::t->match h with 
    | a,b -> if a=n then (get_nont b)@(get_rea_nont (n,t)) 
      else get_rea_nont(n,t) 
    | _-> []) 

let rec fil (st,rl)= 
let x = get_rea_nont(st,rl) in 
(match rl with 
|[]-> [] 
|h::t-> match h with 
     |a,b -> if (member a x) then h::fil(st,t) 
       else fil(st,t) 
     |_->[] 
|_->[] 
) 

let rec filter(st,rl)= 
(st,fil(st,rl)) 

Answer 1

想象一下第二次递归调用fil (st, rl)。在这个电话rl只有一个规则。你的代码将试图通过查看这条规则来发现规则的非终结符是否可达。除非非终结符号是开始符号，否则这不起作用。

一般来说，我会说你必须携带更多的上下文。我不想放弃太多，但这基本上是一个经典的有向图遍历问题。每个语法规则都是图中的一个节点。边界从规则R到定义R的RHS中的非终止符的其他规则。这种着名的图形遍历算法通常与“访问”节点列表一起工作。你需要这个，因为图表可以有周期。

这里是一个循环语法：

A ::= B | B '+' A 
B :: = 'x' | 'y' | '(' A ')' 

Answer 2

在你的代码的一些言论：

1. 相反的member，你可以使用List.mem

2. 在get_nont中的图案匹配可以合并：

   let rec get_nont sl = match sl with 
       | [] -> [] 
       | N x :: tl -> x :: get_nont tl 
       | T _ :: tl -> get_nont tl;; 
   

3. 在函数式编程中，currying用于定义具有多个参数的函数。见Scope, Currying, and Lists，“咖喱功能”一节。

4. 使用模式匹配，例如电源，证明了get_rea_nont：

   let rec get_rea_nont_old n r = n :: (match r with 
       | []->[] 
       | (a, b) :: t when a = n -> (get_nont b) @ (get_rea_nont_old n t) 
       | _ :: t -> get_rea_nont_old n t 
   );; 
   

5. 尝试模块化代码，例如，用于get_rea_nont：

   • 第一过滤元件等于n（见List.filter）。
   • 对于过滤元件，应用功能get_nont（见List.map）
   • 考虑List.flatten得到预期的结果。

   因此......

   let get_rea_nont n r = 
       let filtered = List.filter (fun (a, _) -> a = n) r in 
       let nonterminals = List.map (fun (_, b) -> get_nont b) filtered in 
       n :: (List.flatten nonterminals);;