1#! /usr/bin/perl 2 3################################################################# 4# 5# check_bison_recursion.pl -- check for right recursion in Bison grammars 6# 7# The standard way to parse list constructs in Bison grammars is via left 8# recursion, wherein a nonterminal symbol has itself as the first symbol 9# in one of its expansion rules. It is also possible to parse a list via 10# right recursion, wherein a nonterminal symbol has itself as the last 11# symbol of an expansion; but that's a bad way to write it because a long 12# enough list will result in parser stack overflow. Since Bison doesn't 13# have any built-in way to warn about use of right recursion, we use this 14# script when we want to check for the problem. 15# 16# To use: run bison with the -v switch, then feed the produced y.output 17# file to this script. 18# 19# Copyright (c) 2011-2017, PostgreSQL Global Development Group 20# 21# src/tools/check_bison_recursion.pl 22################################################################# 23 24use strict; 25use warnings; 26 27my $debug = 0; 28 29# must retain this across input lines 30my $cur_nonterminal; 31 32# We parse the input and emit warnings on the fly. 33my $in_grammar = 0; 34 35while (<>) 36{ 37 my $rule_number; 38 my $rhs; 39 40 # We only care about the "Grammar" part of the input. 41 if (m/^Grammar$/) 42 { 43 $in_grammar = 1; 44 } 45 elsif (m/^Terminal/) 46 { 47 $in_grammar = 0; 48 } 49 elsif ($in_grammar) 50 { 51 if (m/^\s*(\d+)\s+(\S+):\s+(.*)$/) 52 { 53 54 # first rule for nonterminal 55 $rule_number = $1; 56 $cur_nonterminal = $2; 57 $rhs = $3; 58 } 59 elsif (m/^\s*(\d+)\s+\|\s+(.*)$/) 60 { 61 62 # additional rule for nonterminal 63 $rule_number = $1; 64 $rhs = $2; 65 } 66 } 67 68 # Process rule if we found one 69 if (defined $rule_number) 70 { 71 72 # deconstruct the RHS 73 $rhs =~ s|^/\* empty \*/$||; 74 my @rhs = split '\s', $rhs; 75 print "Rule $rule_number: $cur_nonterminal := @rhs\n" if $debug; 76 77 # We complain if the nonterminal appears as the last RHS element 78 # but not elsewhere, since "expr := expr + expr" is reasonable 79 my $lastrhs = pop @rhs; 80 if ( defined $lastrhs 81 && $cur_nonterminal eq $lastrhs 82 && !grep { $cur_nonterminal eq $_ } @rhs) 83 { 84 print 85"Right recursion in rule $rule_number: $cur_nonterminal := $rhs\n"; 86 } 87 } 88} 89 90exit 0; 91