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