Previous | Table of Contents | Next |
either moves past the separator or terminates the loop in the case of the last alternative.
To construct the required output, however, parentheses are needed around each alternative, and vertical bars are needed between them. The complete procedure, therefore, is a bit more complicated:
procedure transalts() writes( ) repeat { writes(() tab(upto(|) | 0) ? transseq() if move(1) then writes() |) else { write()) return } } end
Note that an alternation symbol is only written when there is another alternative to process.
The procedure transseq() is invoked as a matching procedure in
tab(upto(|) | 0) ? transseq()
The scanning environment for transseq() is just the current alternative. There is a question of how to terminate the loop: by checking in transseq() or having transsym() fail. To allow for the possibility of an empty alternative, which is reasonable, it is more convenient for transseq() to check when transsym() has processed the last symbol. Note that the symbols for concatenation are provided only when there is another symbol to process:
procedure transseq() repeat { transsym() if not pos(0) then writes( || ) else return } end
As noted previously, there are two kinds of symbols, and the translations are quite different in the two cases. Analysis and transformation of a nonterminal symbol involves a straightforward scanning expression with conjunction again used to bind the component subexpressions. A terminal symbol, on the other hand, requires a prefix equal sign and enclosing quotes:
procedure transsym() if =< then { { writes(tab(many(nchars)), ()) & => } | error() } else writes(=, image(tab(upto(<) | 0))) return end
The function image() is handy for producing the enclosing quotes; otherwise, escaped quotes in literal strings are required. These are hard to read and easy to get wrong.
Note that if several terminal symbols occur in a row, they are combined into a single matching expression. For example, abcd gets transformed into
=abcd
rather than
=a || =b || =c || =d
as specified formally in the transformation given earlier. The result is the same, and the first form is, of course, not only more compact but also more efficient.
There are a few more things that need to be taken care of in the complete program, such as writing out a main procedure that reads in lines and determines whether they are sentences in the grammar. It is necessary to identify the goal nonterminal symbol, which by convention is the one for the first production.
Here is the complete program:
global goal # nonterminal goal name global nchars # characters allowed in a name # # Translate a grammar into a recognizer. # procedure main() local line # a line of input nchars := &letters ++ _ while line := read() do { # process lines of input line ? transprod() # transform the production } # end while write(procedure main()) # write out the main procedure write( while line := read() do {) write( writes(image(line))) write( if line ? (, goal, () & 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 write(procedure , sym := tab(many(nchars)), ()) & =>::= # 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 return end # # Transform a sequence of alternatives. # procedure transalts() writes( ) # write indentation repeat { # process alternatives writes( () # parenthesis for alternative tab(upto(|) | 0) ? transseq() # transform the symbols if move(1) then writes() |) # if more, close the parentheses # and add the alternation else { write()) # no more, close parentheses return } # end else } # end repeat end # # Transform a sequence of symbols. # procedure transseq() repeat { transsym() # process a symbol if not pos(0) then writes( || ) # if more, provide concatenation else return # else get out and return } # end repeat end # # Transform a symbol. # procedure transsym() if =< then { # if its a nonterminal { # write it with suffix writes(tab(many(nchars)), ())& => # get rid of closing bracket } | error () # or catch the error } # end then; otherwise # transform nonterminal else writes(=, image(tab(upto(<) | 0))) return end # # Issue error message and terminate execution. # procedure error() stop(*** malformed production: , tab(0)) end
Previous | Table of Contents | Next |