从 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. 您可以使用 List.mem

2. < p>get_nont中的模式匹配可以组合：

   let rec get_nont sl = 将 sl 与
       | []-> []
       | Nx::tl-> x :: get_nont tl
       | T_::tl-> get_nont tl;;
   

3. 在函数式编程中，柯里化用于定义具有多个参数的函数。请参阅范围、柯里化和列表，“柯里化”部分函数”。

4. 使用模式匹配的力量，例如，为 get_rea_nont 演示的：

   let rec get_rea_nont_old nr = n ::（将 r 与
       | []->[]
       | (a, b) :: t 当 a = n -> (get_nont b) @ (get_rea_nont_old nt)
       | _ :: t - >获取_rea_nont_old nt
   );;
   

5. 尝试模块化您的代码，例如针对 get_rea_nont：

   • 第一个过滤器元素等于n（请参阅List.filter）。
   • 对于过滤后的元素，应用函数get_nont（请参阅List.map)
   • 考虑List.flatten 得到预期的结果。

   因此，...

   让 get_rea_nont nr =
       让filtered = List.filter(fun(a,_) -> a = n) r in
       let nonterminals = List.map(fun(_, b) -> get_nont b) 过滤进去
       n :: (List.展平非终结符);;