CODEWITHSUNDEEP
ocamlgrammar
user974036
user974036

Reputation: 91

Remove unreachable rules from a grammar in OCaml

I'm new to Ocaml and for a homework assignment I have to write a function filter_reachable that takes a grammar and returns a reduced grammar with the unreachable rules removed. The only modules I'm allowed to use are Pervasives and List modules and no other modules.

The idea I have is to first make a list of all reachable nonterminals. Then a rule is reachable if it's nonterminal part is in the list of all reachable nonterminals. All the rules that are reachable then placed into a new list and paired with the start symbol to create the reduced grammar.

My solution is below. However it doesn't work and I don't understand why. Can anyone help me fix it?

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))

Upvotes: 2

Views: 2013

Answers (2)

simon04
simon04

Reputation: 3312

Some remarks on your code:

  1. Instead of member, you could use List.mem

  2. The pattern matching in get_nont can be combined:

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

  3. In functional programming, currying is used to define functions with more than one argument. See Scope, Currying, and Lists,section "Curried functions".

  4. Use the power of pattern matching, e.g., demonstrated for 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. Try modularize your code, e.g., for get_rea_nont:

    • First filter elements being equal to n (see List.filter).
    • For the filtered elements, apply the function get_nont (see List.map)
    • Consider List.flatten to get the expected result.

    Thus, ...

    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);;

Upvotes: 1

Jeffrey Scofield
Jeffrey Scofield

Reputation: 66823

Imagine the second last recursive call to fil (st, rl). In this call rl has just one rule in it. Your code is going to try to discover whether the nonterminal of the rule is reachable by just looking at this one rule. This isn't going to work unless the nonterminal is the start symbol.

Generally speaking I'd say you have to carry around quite a bit more context. I don't want to give too much away, but this is basically a classic directed graph traversal problem. Each grammar rule is a node in the graph. Edges go from a rule R to the other rules defining the nonterminals that appear in the RHS of R. This famous graph traversal algorithm generally works with a list of "visited" nodes. You need this because the graph can have cycles.

Here is a grammar with cycles:

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

Upvotes: 3

Related Questions