Raphael gave useful pointers but nothing that works before a grammar is reduced to a state-machine. I find doing as much work as possible via parse-tree -> parse-tree transformations lets grammar authors debug familiar structures.
Below I include some OCaml that does the job purely on a parse-tree in case others are interested:
let followers (Grammar (m, prods)) start_prod_name =
let n_prods = List.length prods in
(* Maps production names to the set of characters that might follow
* a use of that production. *)
let ref_followers = IdentHashtbl.create n_prods in
(* Maps production names to the set of characters that might precede
* the start of that production. *)
let prod_preceders = IdentHashtbl.create n_prods in
(* Assume that all productions are followed and preceded by the
* empty set. Later we iterate until convergence expanding these sets. *)
List.iter
(fun (Production (_, name, _)) ->
IdentHashtbl.replace ref_followers name RangeSet.empty;
IdentHashtbl.replace prod_preceders name RangeSet.empty)
prods;
(* Assume conservatively that the start production specifies at least
* one finite-length string. *)
IdentHashtbl.replace ref_followers start_prod_name
(RangeSet.singleton end_of_file_code_point);
let iter_until_convergence f =
let rec converge f last =
let next = f () in
if next = last then
last
else
converge f next in
converge f (f ()) in
(**
* [annotated_node node followers] annotates a grammar parse-tree with
* a conservative (overly large) set of characters that can immediately
* follow any prefix that occurs before node is entered.
* @oaram followers the set of characters that can follow node.
* @return the annotated node, the preceder set of node.
*)
let rec annotate_node node followers = match node with
| CharSet (m, ranges) ->
CharSet (A.annotate m ranges, ranges), ranges
| Concatenation (m, children) ->
let annotated_children, preceders =
let rec children_backwards children =
(match children with
| [] -> [], followers
| child::rest ->
let annotated_children, followers =
children_backwards rest in
let annotated_child, preceders =
annotate_node child followers in
annotated_child::annotated_children, preceders) in
children_backwards children in
(* The set that follows the start of a concatenation is the set that
* precedes the first element. *)
Concatenation (A.annotate m preceders, annotated_children), preceders
| Reference (m, name) ->
(* Add the call site followers with those from the map for the
* next call to (annotate_prod name) to consider. *)
IdentHashtbl.replace
ref_followers name
(RangeSet.union
(IdentHashtbl.find ref_followers name)
followers);
let preceders = IdentHashtbl.find prod_preceders name in
Reference (A.annotate m preceders, name),
preceders
| Repetition (m, body) ->
(* If the last repetition of body is preceded by P and followed by F,
* then if we treat the last repetition as optional, and consider
* a previous instance of body, then that previous instance can be
* followed by P or F, so we can compute its preceders by treating
* it as followed by (P u F).
* We iterate until convergence.
*)
let rec converge annotated_body followers preceders =
let prev_instance_followers = RangeSet.union followers preceders in
let prev_annotated_body, prev_instance_preceders =
annotate_node body prev_instance_followers in
if prev_annotated_body = annotated_body
&& prev_instance_preceders = preceders then
annotated_body, preceders
else
converge prev_annotated_body followers prev_instance_preceders in
(* Repetitions always match at least once. *)
let annotated_body, preceders = annotate_node body followers in
let annotated_body, preceders =
converge annotated_body followers preceders in
Repetition (A.annotate m preceders, annotated_body), preceders
| Union (m, o, children) ->
let annotated_children, preceders =
List.fold_right
(fun child (annotated_children, preceders) ->
let annotated_child, child_preceders =
annotate_node child followers in
(annotated_child::annotated_children,
RangeSet.union preceders child_preceders))
children ([], RangeSet.empty) in
Union (A.annotate m preceders, o, annotated_children), preceders in
let annotate_prod (Production (m, name, body)) =
let followers = IdentHashtbl.find ref_followers name in
let annotated_body, preceders = annotate_node body followers in
IdentHashtbl.replace prod_preceders name preceders;
Production (A.annotate m preceders, name, annotated_body) in
let annotate_grammar () =
Grammar (
A.annotate m (RangeSet.empty),
List.map annotate_prod prods) in
iter_until_convergence annotate_grammar
