Computing follow sets conservatively for a PEG grammar

Question

Given a parsing expression grammar (PEG) grammar and the name of the start production, I would like to label each node with the set of characters that can follow it. I would be happy with a good approximation that is conservative -- if a character can follow a node then it must appear in the follower set.

The grammar is represented as a tree of named productions whose bodies contain nodes representing

1. Character
2. Concatenation
3. Union
4. Non-terminal references

So given a grammar in ABNF style syntax:

A := B ('a' | 'b');
B := ('c' | 'd') (B | ());

where adjacent nodes are concatenated, | indicates union, single quoted characters match the character they represent, and upper case names are non-terminals.

If the grammar's start production is A, the annotated version might look like

A := 
  (
    (B /* [ab] */)
    (
      ('a' /* eof */)
    | 
      ('b' /* eof */)
    /* eof */
    )
  /* eof */
  );

B :=
  (
    (
      ('c' /* [abcd] */)
      |
      ('d' /* [abcd] */)
    /* [abcd] */
    )
    (
      (B /* [ab] */)
      |
      ( /* [ab] */)
    /* [ab] */
    )
  );

I want this so that I can do some simplification on a PEG grammar. Since order is important in unions in PEG grammars, I want to partition the members of unions based on which ones could accept the same character so that I can ignore order between partition elements.

I'm using OMeta's grow-the-seed scheme for handling direct left-recursion in PEG grammars, so I need something that handles that. I expect that any scheme for handling scannerless CF grammars with order-independent unions that is conservative or correct would be conservative for my purposes.

Pointers to algorithms or source code would be much appreciated.

Answer 1

Follow or lookahead sets are a standard concept in compiler theory. I would expect every textbook on the topic to contain an algorithm for them; as for online resources, try this or that one. It seems as if the choice of algorithm depended on what kind of grammar -- LL, LR, LALR, ... -- you have.

Answer 2

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