Page 1 of 1

Writing An Interpreter - Part IIID Pseudo-code generation Rate Topic: ***** 1 Votes

#1 Martyn.Rae  Icon User is offline

  • The programming dinosaur
  • member icon

Reputation: 540
  • View blog
  • Posts: 1,406
  • Joined: 22-August 09

Posted 06 March 2010 - 02:44 PM

Writing An Interpreter - Part IIID

Pseudo-code Dictionaries

The pseudo-code generator uses a global dictionary, created when the program statement is executed (it actually exists once the Basic interpreter has been initialised).

There is also the local dictionary which is created at the start of a function or procedure block, and only exists until the end of function or end of procedure.

Pseudo-code Generation

This section look at the generation of pseudo-code from the abstract syntax tree. This is by far the most fun part of the interpreter, and certainly for myself as an assembler programmer, the most interesting. Pseudo-code can be best described as non-processor specific instructions that vaguely resemble assembler, but are at a more abstract level. The pesudo-code we will be using here does not deal with registers as such, but it does assume that we have a stack, and a single location we shall refer to as the accumulator. So, for example the Basic statement a% = a% + 3 would ultimately give us the pseudo-code shown below

                 load           a%
                 addi           3
                 store          a%



similarly the expression LEFT$(input$, 3) would produce the pseudo-code


                 stack          3
                 stack          input$
                 loadi          2
                 call           LEFT$



We shall consider each of the Basic statements in turn, and discuss the pseudo-code that is produced.

The DIM statement pseudocode

The DIM statement gives us the ability to create a one-, two-, or three-dimensional array. The pseudo-code that will be generated is as follows (assuming an array called array$).

For a one-dimensional array, 'DIM array$(20)'

                 stack          20
                 loadi          1
                 allocate
                 storeaddress   array$



For a two-dimensional array, 'DIM array$(20, f%)'

                 stack          f%
                 stacki         20
                 loadi          2
                 allocate
                 storeaddress   array$



For a three-dimensional array, 'DIM array$(20, f%, p%)'

                 stack          f%
                 stacki         20
                 stack          p%
                 loadi          3
                 allocate
                 storeaddress   array$



The FOR ... END FOR statement pseudocode

The FOR ... END FOR statement produces two blocks of pseudo-code, a prologue block and an epilogue block. For example if we take the statement FOR ix% = start% TO end% STEP stepper% ... END FOR, the prologue pseudo-code would be

                 load           start%
                 store          ix%
label_n          load           ix%
                 test_less      end%
                 jump_false     label_n+1



and the epilogue code would be

label_n+1        load           ix%
                 add            stepper%
                 store          ix%
                 jump           label_n
label_n+2        no_operation



Do not worry about the labels, as they will be explained more fully in Section IV of this tutorial.

The DO ... UNTIL statement pseudocode

The DO... UNTIL statement produces two blocks of pseudo-code, a prologue block and an epilogue block. For example if we take the statement DO ... UNTIL expression1% == expression2%, the prologue pseudo-code would be

label_n          no_operation



and the epilogue code would be

label_n+1        load           expression1%
                 test_equal     expression2%
                 jump_false     label_n
label_n+2        no_operation



The WHILE ... END WHILE statement pseudocode

The WHILE ... END WHILE statement produces two blocks of pseudo-code, a prologue block and an epilogue block. For example if we take the statement WHILE expression1% <> expression2% ... END WHILE, the prologue pseudo-code would be

label_n          load           expression1%
                 test_equal     expression2%
                 jump_true      label_n+2



and the epilogue code would be

label_n+1        jmp            label_n
label_n+2        no_operation



The PRINT statement pseudocode

The pseudo-code for the PRINT statement is simply

                 print



The accumulator will have been set up with the location of the item to be printed.

The INPUT statement pseudocode

The pseudo-code for the INPUT statement is simply

                 input



The accumulator will have been set up with the location of the item to be printed.

The IF ... ELSE ... END IF statement pseudocode

The IF ... END IF statement produces two blocks of pseudo-code, a prologue block and an epilogue block. For example if we take the statement IF expression1% == expression2% ... END IF, the prologue pseudo-code would be

label_n          load           expression1%
                 test_equal     expression2%
                 jump_false     label_n+1



and the epilogue code would be

label_n+1        no_operation



For an IF ... ELSE ... END IF statement produces trree blocks of pseudo-code, a prologue block, a mid-block and an epilogue block. For example if we take the statement IF expression1% == expression2% ... ELSE ... END IF, the prologue pseudo-code would be

label_n          load           expression1%
                 test_equal     expression2%
                 jump_false     label_n+1



the mid-block code would be

                 jmp            label_n+2
label_n+1        no_operation



and the epilogue code would be

label_n+2        no_operation



The BREAK statement pseudocode

The pseudo-code for the BREAK statement is as follows.

                 jmp           label_n+2.



The CONTINUE statement pseudocode

The pseudo-code for the CONTINUE statement is as follows.

                 jmp           label_n+1.



The FUNCTION ... END FUNCTION statement pseudocode

The pseudo-code for the FUNCTION ... END FUNCTION statement has also a prologue and epilogue section. Let us say we have a function name$ which uses three parameters, first_name$, middle_name$ and surname$. The pseudo code for this function's prologue would be

label_n          testi         3
                 jump_notequal label_n+1
                 unstack
                 store         #return_address#
                 add_entry     name$
                 dictionary
                 unstack
                 add_entry     first_name$
                 store         first_name$
                 unstack
                 add_entry     middle_name$
                 store         middle_name$
                 unstack
                 add_entry     surname$
                 store         surname$
                 stack         #return_address#



and the epilogue would be

                 undictionary
                 return
label_n+1        error        %1



The PROCEDURE ... END PROCEDURE statement pseudocode

The pseudo-code for the PROCEDURE ... END PROCEDURE statement has also a prologue and epilogue section. Let us say we have a procedure concatenate$ which uses two parameters, string1$ and string2$. The pseudo code for this procedure's prologue would be

label_n          testi         2
                 jump_notequal label_n+1
                 unstack
                 store         #return_address#
                 dictionary
                 add_entry     concatenate$
                 unstack
                 add_entry     string1$
                 store         string1$
                 unstack
                 add_entry     string2$
                 store         string2$
                 stack         #return_address#



and the epilogue would be

                 undictionary
                 return
label_n+1        error        %1



You will notice there is considerable similarity between the function pseudo-code and the procedure pseudo-code. The difference lies in which dictionary, the name of the routine is placed. For a function, the routine name is place in the global dictionary, whereas in a procedure it is stored in the local dictionary, which means that it is removed (undictionary) when the procedure ends. During the procedure code block however, it can be used just as any other variable.

Expression Pesudo-instructions

All pesudo-instructions have an equivalient immediate operation (e.g. xori, subtracti, modulusi.

[i]bitwise operations:[/i]

                 and         variable     ; bitwise and operation on the accumulator and variable
                 or          variable     ; bitwise or operation on the accumulator and variable
                 xor         variable     ; bitwise xor operation on the accumulator and variable
                 not         variable     ; bitwise not operation on the accumulator and variable

[i]arithmetic operations:[/i]

                 add         variable     ; add variable to the accumulator
                 subract     variable     ; subtract variable from the accumulator
                 multiply    variable     ; multiply variable and the accumulator
                 divide      variable     ; divide accumulator by the variable
                 modulus     variable     ; divide accumulator by the variable and set modulus in accumulator



This completes part III of the "Writing an Interperter" tutorial.

Is This A Good Question/Topic? 2
  • +

Replies To: Writing An Interpreter - Part IIID

#2 vividexstance  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 651
  • View blog
  • Posts: 2,224
  • Joined: 31-December 10

Posted 06 February 2011 - 09:54 AM

Do you have idea when this tutorial might be finished? I've read the whole thing, and got the line editor/parser working. I also understand the grammar rules, just have no idea about how to do the interpreter.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1