XREF(AWK) Philip L. Bewig XREF(AWK)
NAME
xref(awk) - produce a cross reference listing of an awk program
SYNOPSIS
awk -f xref.awk [ file ... ]
DESCRIPTION
XREF(AWK) takes as input a valid awk program and produces as out-
put a cross-reference listing of all variables and function calls
which appear in the program.
For ordinary variables and array variables, a line of the form
count var(func) lines ...
is produced, where "count" is the number of times the variable is
used, "var" is the name of the variable, "func" is the function
name to which the variable is local (a null "func" indicates that
the variable is global), and "lines" is the number of each line
where the variable appears. Appearances of the variable in a
function's parameter list are ignored. The number of lines shown
may differ from "count" if the variable appears more than once on
the same line.
For functions, a line of the form
count func(define) lines ...
is produced, where "count" is the number of times the function is
called, "func" is the name of the function, "define" is the lime
number where the function is defined, and "lines" is the number of
each line where the function is called. As for variables, the
number of lines shown may differ from "count."
Output lines for variables and functions are intermixed and are
sorted by name. Though terse, the output is informative, easy to
read, and amenable to further processing.
EXAMPLE
The cross-reference listing produced by running xref.awk against
itself is shown below:
5 NR() 39 45 50 53 68
8 RLENGTH() 119 120 123 124 127 128 132 133
10 act() 31 34 36 40 51 54 56 63 65 67
1 arr(asplit) 90
2 arr(inarray) 93 94
1 asplit(89) 6
3 braces() 55 57 58
2 flines() 53 79
1 fs(asplit) 89
3 funcname() 42 52 61
16 i() 76 77 78 79 81 82 83 84 90
3 inarray(92) 37 43 48
6 j() 82 83 84
3 j(inarray) 93 94
3 keywords() 10 125 129
1 lex(97) 29
31 line() 103 104 107 108 109 110 112 113 114 115 116 117 118
119 120 122 123 124 126 127 128 131 132 133
6 lines() 39 45 50 83 84
4 local() 41 59 60 64
3 machine() 17 30 31
2 n(asplit) 89 90
15 names() 37 38 43 44 48 49 77 78 79 81 82 83 84
3 nextstate() 30 62 73
4 nnames() 38 44 49 76
4 state() 23 30 31 73
1 str(asplit) 89
3 symb() 29 30 31
2 temp() 59 60
2 temp_asplit() 89 90
31 tok() 37 38 39 41 42 43 44 45 47 48 49 50 52 53 64 101 105
113 115 117 119 123 125 127 129 132
1 val(inarray) 94
5 xnames() 39 45 50 77 82
For readability, some lines have been folded.
SOURCE CODE
# xref.awk - cross reference an awk program
BEGIN {
# create array of keywords to be ignored by lexer
asplit("BEGIN:END:atan2:break:close:continue:cos:delete:" \
"do:else:exit:exp:for:getline:gsub:if:in:index:int:" \
"length:log:match:next:print:printf:rand:return:sin:" \
"split:sprintf:sqrt:srand:sub:substr:system:while",
keywords,":")
# build the symbol-state table
split("00:00:00:00:00:00:00:00:00:00:" \
"20:10:10:12:12:11:07:00:00:00:" \
"08:08:08:08:08:33:08:00:00:00:" \
"08:44:08:36:08:08:08:00:00:00:" \
"08:44:45:42:42:41:08",machine,":")
# parse the input and store an intermediate representation
# of the cross-reference information
# set up the machine
state = 1
# run the machine
for (;;) {
# get next symbol
symb = lex()
nextstate = substr(machine[state symb],1,1)
act = substr(machine[state symb],2,1)
# perform required action
if ( act == "0" )
; # do nothing
else if ( act == "1" ) {
if ( ! inarray(tok,names) )
names[++nnames] = tok
lines[tok,++xnames[tok]] = NR }
else if ( act == "2" ) {
if ( tok in local ) {
tok = tok "(" funcname ")"
if ( ! inarray(tok,names) )
names[++nnames] = tok
lines[tok,++xnames[tok]] = NR }
else {
tok = tok "()"
if ( ! inarray(tok,names) )
names[++nnames] = tok
lines[tok,++xnames[tok]] = NR } }
else if ( act == "3" ) {
funcname = tok
flines[tok] = NR }
else if ( act == "4" )
braces++
else if ( act == "5" ) {
braces--
if ( braces == 0 ) {
for ( temp in local )
delete local[temp]
funcname = ""
nextstate = 1 } }
else if ( act == "6" ) {
local[tok] = 1 }
else if ( act == "7" )
break
else if ( act == "8" ) {
print "error: xref.awk: line " NR ": aborting" \
> "/dev/con"
exit 1 }
# finished with current token
state = nextstate }
# finished parsing, now ready to print output
for ( i = 1; i <= nnames; i++ ) {
printf "%d ", xnames[names[i]] |"sort +1"
if ( index(names[i],"(") == 0 )
printf "%s(%d)", names[i], flines[names[i]] |"sort +1"
else
printf "%s", names[i] |"sort +1"
for ( j = 1; j <= xnames[names[i]]; j++ )
if ( lines[names[i],j] != lines[names[i],j-1] )
printf " %d", lines[names[i],j] |"sort +1"
printf "\n" |"sort +1" }
} # END OF PROGRAM
function asplit(str,arr,fs, n) { n = split(str,temp_asplit,fs)
for ( i = 1; i <= n; i++ ) arr[temp_asplit[i]]++ }
function inarray(val,arr, j) {
for ( j in arr )
if ( arr[j] == val ) return j
return "" }
function lex() {
for (;;) {
if ( tok == "(eof)" ) return 7
while ( length(line) == 0 )
if ( getline line == 0 ) {
tok = "(eof)"; return 7 }
sub(/^[ \t]+/,"",line) # remove white space,
sub(/^"([^"]|\\")*"/,"",line) # quoted strings,
sub(/^\/([^\/]|\\\/)+\//,"",line) # regular expressions,
sub(/^#.*/,"",line) # and comments
if ( line ~ /^function/ ) {
tok = "function"; line = substr(line,9); return 1 }
else if ( line ~ /^{/ ) {
tok = "{"; line = substr(line,2); return 2 }
else if ( line ~ /^}/ ) {
tok = "}"; line = substr(line,2); return 3 }
else if ( match(line,/^[A-Za-z_][A-Za-z_0-9]*\[/) ) {
tok = substr(line,1,RLENGTH-1)
line = substr(line,RLENGTH+1)
return 5 }
else if ( match(line,/^[A-Za-z_][A-Za-z_0-9]*\(/) ) {
tok = substr(line,1,RLENGTH-1)
line = substr(line,RLENGTH+1)
if ( ! ( tok in keywords ) ) return 6 }
else if ( match(line,/^[A-Za-z_][A-Za-z_0-9]*/) ) {
tok = substr(line,1,RLENGTH)
line = substr(line,RLENGTH+1)
if ( ! ( tok in keywords ) ) return 4 }
else {
match(line,/^[^A-Za-z_{}]/)
tok = substr(line,1,RLENGTH)
line = substr(line,RLENGTH+1) } } }
TECHNICAL DISCUSSION
Broadly, XREF(AWK) parses an awk program using a symbol-state
table, in much the same way as a yacc-generated parser. The
lexical analyzer recognizes seven distinct symbols: the word
"function", the left brace, the right brace, identifiers used
as variables, identifiers used as arrays, identifiers used as
functions, and end of file. The type of symbol is returned to
the parser as the value of the "lex" function, and the global
variable "tok" is set to the text of the current token.
The symbol-state table is stored in the "machine" array. The
table can be represented as follows:
symbol | 1 2 3 4 5 6 7
|
state | "function" { } var array func eof
-- -- -- -- -- -- -- -+- -- -- -- -- -- -- -- -- -- -- -- -- --
1 any | 20 10 10 12 12 11 07
2 "function" | 08 08 08 08 08 33 08
3 "function" name | 08 44 08 36 08 08 08
4 "function" name "{" | 08 44 45 42 42 41 08
where the first digit is the state to be entered after process-
ing the current token and the second digit is an action to be
performed. The actions are listed below:
1 found a function call
2 found a variable or array
3 found a function definition
4 found a left brace
5 found a right brace
6 found a local variable declaration
7 found end of file
8 found an error
Each of the first six actions causes some information about the
target program to be stored for later processing; the structures
used will be discussed below. The seventh action causes the
parser to exit. The eighth action causes errors to be reported
to standard error and the program to abort.
Before describing the intermediate data structures, we will
discuss some of the more interesting points in the action calls.
The "braces" variable keeps track of whether we are currently
within a functions; it is positive within a function and zero
without. When the right brace which causes the value of "braces"
to go from one to zero is found, the value of "nextstate" is
changed from four (scanning a function) to one (any) and the
names of local variables are forgotten. The "local" array is
accumulated from the variables found after the function name but
before the opening left brace of the function; action two care-
fully checks whether a variable is global or local before writing
to the intermediate data structure. The variable "funcname" is
the name of the current function when within a function and null
without.
The following arrays store an intermediate representation of the
variable and function identifiers of the target program:
names[1..nnames] = list of all identifiers, both variable and
function names; for variables, the name has the form
var(func), but for functions, there are no parentheses
xnames[names[i]] = number of times names[i] is used
lines[names[i],1..xnames[names[i]]] = list of line numbers
where names[i] is used
flines[names[i]] = line number where function names[i] is
defined
These arrays are created as the parser reads the input; when the
parser is finished, the arrays are output in user-readable form.
PORTABILITY
XREF(AWK) will work with any implementation of nawk. The MKS
ToolKit implementation requires the large-model version of awk.
HISTORY
Written by Phil Bewig on February 10, 1990. Inspired by
Exercise 3-16 of the book "The Awk Programming Language" by
Alfred V. Aho, Brian W. Kernighan and Peter J. Weinberger
(Addison-Wesley: 1988).
COPYRIGHT
This program is placed in the public domain. However, the
author requests credit when distributed.