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
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
|
############################################################################
#
# File: recgen.icn
#
# Subject: Program to generate context-free recognizer
#
# Author: Ralph E. Griswold
#
# Date: January 28, 1991
#
############################################################################
#
# This file is in the public domain.
#
############################################################################
#
# This program reads a context-free BNF grammar and produces an Icon
# program that is a recognizer for the corresponding language.
#
# Nonterminal symbols are are enclosed in angular brackets. Vertical
# bars separate alternatives. All other characters are considered to
# be terminal symbols. The nonterminal symbol on the first line is
# taken to be the goal.
#
# An example is:
#
# <expression>::=<term>|<term>+<expression>
# <term>::=<element>|<element>*<term>
# <element>::=x|y|z|(<expression>)
#
# Characters in nonterminal names are limited to letters and underscores.
# An underscore is appended for the recognizing procedure name to avoid
# possible collisions with Icon function names.
#
# Lines beginning with an = are passed through unchanged. This allows
# Icon code to be placed in the recognizer.
#
############################################################################
#
# Limitations:
#
# Left recursion in the grammar may cause the recognizer to loop.
# There is no check that all nonterminal symbols that are referenced
# are defined or for duplicate definitions.
#
############################################################################
#
# Reference:
#
# The Icon Programming Language, Second Edition, Ralph E. and Madge T.
# Griswold, Prentice-Hall, 1990. pp. 180-187.
#
############################################################################
#
# See also: pargen.icn
#
############################################################################
global call # name suffix and parens
global goal # nonterminal goal name
global nchars # characters allowed in a nonterminal name
procedure main()
local line # a line of input
call := "_()"
nchars := &letters ++ '_'
while line := read() do { # process lines of input
line ? {
case move(1) of { # action depends on first character
"<": tab(0) ? transprod() # transform the production
"=": write(tab(0)) # pass through
default: error()
} # end case
} # end scan
} # end while
write("procedure main()") # write out the main procedure
write(" while line := read() do {")
write(" writes(image(line))")
write(" if line ? (",goal,call," & pos(0)) then ")
write(" write(\": accepted\")")
write(" else write(\": rejected\")")
write(" }")
write("end")
end
#
# Transform a production.
#
procedure transprod()
local sym # the symbol being defined
{
# begin the procedure declaration
write("procedure ",sym := tab(many(nchars)),call) &
=">::=" # skip definition symbols
} | error() # catch syntactic error
write(" suspend {") # begin the suspend expression
transalts() # transform the alternatives
write(" }") # end the suspend expression
write("end") # end the procedure declaration
write() # space between declarations
/goal := sym # first symbol is goal
end
#
# Transform a sequence of alternatives.
#
procedure transalts()
local alt # an alternative
writes(" ") # write indentation
while alt := tab(upto('|') | 0) do { # process alternatives
writes(" (") # open parenthesis for alternative
alt ? transseq() # transform the symbols
if move(1) then writes(") |") # if there's more, close the parentheses
# and add the alternation.
else {
write(")") # no more, so just close the parentheses
break
} # end else
} # end while
end
#
# Transform a sequence of symbols.
#
procedure transseq()
repeat {
transsym() # process a symbols
if not pos(0) then writes(",") # if there's more, provide concatenation
else break # else get out and return
} # end while
end
#
# Transform a symbol.
#
procedure transsym()
if ="<" then { # if it's a nonterminal
{ # write it with suffix.
writes(tab(many(nchars)),call) &
=">" # get rid of closing bracket
} | error() # or catch the error
} # end then
# otherwise transform nonterminal string
else writes("=",image(tab(upto('<') | 0)))
return
end
#
# Issue error message and terminate execution.
#
procedure error()
stop("*** malformed definition: ",tab(0))
end
|
