reachability.ml 2.32 KB
Newer Older
1 2 3 4 5 6 7 8 9 10 11 12 13
(******************************************************************************)
(*                                                                            *)
(*                                   Menhir                                   *)
(*                                                                            *)
(*                       François Pottier, Inria Paris                        *)
(*              Yann Régis-Gianas, PPS, Université Paris Diderot              *)
(*                                                                            *)
(*  Copyright Inria. All rights reserved. This file is distributed under the  *)
(*  terms of the GNU General Public License version 2, as described in the    *)
(*  file LICENSE.                                                             *)
(*                                                                            *)
(******************************************************************************)

14
open BasicSyntax
15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31

let rec visit grammar visited symbol =
  try
    let rule = StringMap.find symbol grammar.rules in
    if not (StringSet.mem symbol visited) then
      let visited = StringSet.add symbol visited in
      List.fold_left (visitb grammar) visited rule.branches
    else
      visited
  with Not_found ->
    (* This is a terminal symbol. *)
    assert (symbol = "error" || StringMap.mem symbol grammar.tokens);
    visited

and visitb grammar visited { producers = symbols } =
  List.fold_left (visits grammar) visited symbols

32 33
and visits grammar visited producer =
  visit grammar visited (producer_symbol producer)
34 35 36 37 38 39 40

let trim grammar =
  if StringSet.cardinal grammar.start_symbols = 0 then
    Error.error [] "no start symbol has been declared."
  else
    let reachable =
      StringSet.fold (fun symbol visited ->
41
        visit grammar visited symbol
42
      ) grammar.start_symbols StringSet.empty
43 44 45
    in
    StringMap.iter (fun symbol rule ->
      if not (StringSet.mem symbol reachable) then
46 47 48 49
        Error.grammar_warning
          rule.positions
             "symbol %s is unreachable from any of the start symbol(s)."
               symbol
50
    ) grammar.rules;
51 52 53 54 55
    { grammar with
      rules = StringMap.restrict reachable grammar.rules;
      types = StringMap.restrict reachable grammar.types;
      on_error_reduce = StringMap.restrict reachable grammar.on_error_reduce;
    }