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.


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.

  • $\begingroup$ Links seem dead. $\endgroup$
    – ggorlen
    Feb 9 '20 at 21:01
  • $\begingroup$ @ggorlen Seems so, yes. :/ If you have the time to track down their new homes, feel free to suggest and edit. Thanks! $\endgroup$
    – Raphael
    Feb 10 '20 at 14:13

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. *)
    (fun (Production (_, name, _)) ->
      IdentHashtbl.replace ref_followers name RangeSet.empty;
      IdentHashtbl.replace prod_preceders name RangeSet.empty)

  (* 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
        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. *)
        ref_followers name
           (IdentHashtbl.find ref_followers name)
      let preceders = IdentHashtbl.find prod_preceders name in
      Reference (A.annotate m preceders, name),

    | 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
          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 =
          (fun child (annotated_children, preceders) ->
            let annotated_child, child_preceders =
              annotate_node child followers in
             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
  • 1
    $\begingroup$ Please don't post only code. A good answer includes the algorithmic idea and clear (pseudo) code if necessary. More complete sources can be included via pastebin.com or similar. $\endgroup$
    – Raphael
    Jun 17 '12 at 13:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.