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 it’s 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