RECURSIVE-DESCENT PARSER FOR PL/0 ATTRIBUTE GRAMMAR
                        ---------------------------------------------------


          procedure PROGRAM (out TREE);
              begin
                  GET_TOKEN;
                  BLOCK (ENV, TREE);
                  if TOKEN <> "." then ERROR
              end;

          procedure BLOCK (out ENV, TREE);
              begin
                  CONST_ENV := nil;
                  if TOKEN = "const" then begin
                      repeat
                          GET_TOKEN;
                          if TOKEN <> IDENT then ERROR;
                          CONST_ID := LEXEME;
                          GET_TOKEN;
                          if TOKEN <> "=" then ERROR;
                          GET_TOKEN;
                          if TOKEN <> NUMBER then ERROR;
                          CONST_NUM := atoi (LEXEME);
                          CONST_ENV := append (CONST_ENV,
                              list (tuple (CONST_ID, const (CONST_NUM))));
                          GET_TOKEN
                      until TOKEN <> ",";
                      if TOKEN <> ";" then ERROR;
                      GET_TOKEN
                  end;
                  VAR_ENV := nil;
                  if TOKEN = "var" then begin
                      repeat
                          GET_TOKEN;
                          if TOKEN <> IDENT then ERROR;
                          VAR_ENV :=
                              append (VAR_ENV, list (tuple (LEXEME, var)));
                          GET_TOKEN
                      until TOKEN <> ",";
                      if TOKEN <> ";" then ERROR;
                      GET_TOKEN
                  end;
                  PROC_ENV := nil;
                  while TOKEN = "procedure" do begin
                      GET_TOKEN;
                      if TOKEN <> IDENT then ERROR;
                      PROC_ID := LEXEME;
                      GET_TOKEN;
                      if TOKEN <> ";" then ERROR;
                      GET_TOKEN;
                      BLOCK (BLOCK_ENV, BLOCK_TREE);
                      if TOKEN <> ";" then ERROR;
                      PROC_ENV := append (PROC_ENV,
                          list (tuple (PROC_ID,
                              procedure (BLOCK_ENV, BLOCK_TREE))));
                      GET_TOKEN
                  end;
                  ENV := append (CONST_ENV, VAR_ENV, PROC_ENV);
                  STATEMENT (ENV, TREE)
              end;









          procedure STATEMENT (in ENV; out TREE);
              begin
                  if TOKEN = IDENT then begin
                      ID := LEXEME;
                      GET_TOKEN;
                      if TOKEN <> ":=" then ERROR;
                      GET_TOKEN;
                      EXPRESSION (ENV, EXPRESSION_TREE);
                      TREE := tree (":=", ID, EXPRESSION_TREE)
                  end
                  else if TOKEN = "call" then begin
                      GET_TOKEN;
                      if TOKEN <> IDENT then ERROR;
                      TREE := tree ("call", LEXEME);
                      GET_TOKEN
                  end
                  else if TOKEN = "begin" then begin
                      GET_TOKEN;
                      STATEMENT (ENV, TREE);
                      while TOKEN = ";" do begin
                          GET_TOKEN;
                          STATEMENT (ENV, STATEMENT_TREE);
                          TREE := tree (";", TREE, STATEMENT_TREE)
                      end;
                      if TOKEN <> "end" then ERROR;
                      GET_TOKEN
                  end
                  else if TOKEN = "if" then begin
                      GET_TOKEN;
                      CONDITION (ENV, CONDITION_TREE);
                      if TOKEN <> "then" then ERROR;
                      GET_TOKEN;
                      STATEMENT (ENV, STATEMENT_TREE);
                      TREE := tree ("if-then", CONDITION_TREE, STATEMENT_TREE)
                  end
                  else if TOKEN = "while" then begin
                      GET_TOKEN;
                      CONDITION (ENV, CONDITION_TREE);
                      if TOKEN <> "do" then ERROR;
                      GET_TOKEN;
                      STATEMENT (ENV, STATEMENT_TREE);
                      TREE := tree ("while-do", CONDITION_TREE, STATEMENT_TREE)
                  else
                      TREE := nil
              end;

















          procedure CONDITION (in ENV; out TREE);
              begin
                  if TOKEN = "odd" then begin
                      GET_TOKEN;
                      EXPRESSION (ENV, EXPRESSION_TREE);
                      TREE := tree ("odd", EXPRESSION_TREE)
                  else begin
                      EXPRESSION (ENV, EXPRESSION_TREE1);
                      if TOKEN <> RELATION then ERROR;
                      RELOP := LEXEME;
                      GET_TOKEN;
                      EXPRESSION (ENV, EXPRESSION_TREE2);
                      TREE := tree (RELOP, EXPRESSION_TREE1, EXPRESSION_TREE2)
                  end
              end;

          procedure EXPRESSION (in ENV; out TREE);
              begin
                  if TOKEN = ADDING_OPERATOR then begin
                      ADDOP := LEXEME;
                      GET_TOKEN;
                      TERM (ENV, TERM_TREE);
                      TREE := tree (ADDOP, TERM_TREE)
                  end
                  else
                      TERM (ENV, TREE);
                  while TOKEN = ADDING_OPERATOR do begin
                      ADDOP := LEXEME;
                      GET_TOKEN;
                      TERM (ENV, TERM_TREE);
                      TREE := tree (ADDOP, TREE, TERM_TREE)
                  end
              end;

          procedure TERM (in ENV; out TREE);
              begin
                  FACTOR (ENV, TREE);
                  while TOKEN = MULTIPLYING_OPERATOR do begin
                      MULTOP := LEXEME;
                      GET_TOKEN;
                      FACTOR (ENV, FACTOR_TREE);
                      TREE := tree (MULTOP, TREE, FACTOR_TREE)
                  end
              end;

          procedure FACTOR (in ENV; out TREE);
              begin
                  if TOKEN = IDENTIFIER then begin
                      TREE := tree (LEXEME);
                      GET_TOKEN
                  end
                  else if TOKEN = NUMBER then begin
                      TREE := tree (LEXEME);
                      GET_TOKEN
                  end
                  else if TOKEN = "(" then begin
                      GET_TOKEN;
                      EXPRESSION (ENV, TREE);
                      if TOKEN <> ")" then ERROR;
                      GET_TOKEN
                  end
                  else ERROR
              end;

               TRACE OF RECURSIVE-DESCENT PARSER FOR PL/0 ATTRIBUTE GRAMMAR
                ------------------------------------------------------------

        vax X, Y;
        begin
          X := 0;
          Y := X + 1
        end.

        PROGRAM (out TREE)
          GET_TOKEN (TOKEN = var)
          BLOCK (out ENV, TREE)
            GET_TOKEN (TOKEN = X)
            GET_TOKEN (TOKEN = ,)
            GET_TOKEN (TOKEN = Y)
            GET_TOKEN (TOKEN = ;)
            GET_TOKEN (TOKEN = begin)
            STATEMENT (in ENV = <(X, var), (Y, var)>; out TREE)
              GET_TOKEN (TOKEN = X)
              STATEMENT (in ENV = <(X, var), (Y, var)>; out TREE)
                GET_TOKEN (TOKEN = :=)
                GET_TOKEN (TOKEN = 0)
                EXPRESSION (in ENV = <(X, var), (Y, var)>; out TREE)
                  TERM (in ENV = <(X, var), (Y, var)>; out TREE)
                    FACTOR (in ENV = <(X, var), (Y, var)>; out TREE)
                      GET_TOKEN (TOKEN = ;)
                      return TREE = (0)
                    return TREE = (0)
                  return TREE = (0)
                return TREE = (:= X 0)
              GET_TOKEN (TOKEN = Y)
              STATEMENT (in ENV = <(X, var), (Y, var)>; out TREE)
                GET_TOKEN (TOKEN = :=)
                GET_TOKEN (TOKEN = X)
                EXPRESSION (in ENV = <(X, var), (Y, var)>; out TREE)
                  TERM (in ENV = <(X, var), (Y, var)>; out TREE)
                    FACTOR (in ENV = <(X, var), (Y, var)>; out TREE)
                      GET_TOKEN (TOKEN = +)
                      return TREE = (X)
                    return TREE = (X)
                  GET_TOKEN (TOKEN = 1)
                  TERM (in ENV = <(X, var), (Y, var)>; out TREE)
                    FACTOR (in ENV = <(X, var), (Y, var)>; out TREE)
                      GET_TOKEN (TOKEN = end)
                      return TREE = (1)
                    return TREE = (1)
                  return TREE = (+ X 1)
                return TREE = (:= (+ X 1))
              GET_TOKEN (TOKEN = .)
              return TREE = (; (:= X 0) (:= (+ X 1)))
            return ENV = <(X, var), (Y, var)>, TREE = (; (:= X 0) (:= (+ X 1)))
          return TREE = (; (:= X 0) (:= (+ X 1)))

        Note: Indentation level identifies function components.