(* l04 - expressions with constants and variables *) program = statement { ';' statement } '.' . statement = [ id ( '=' number | ':=' expression ) | '!' expression ] . expression = [ '+' | '-' ] term { ( '+' | '-' ) term } . term = factor { ( '*' | '/' ) factor } . factor = number | id | '(' expression ')' . (* terminals: number id ! = ( * / + - ) ; . 2010-04-16, v00: Same syntax and semantics as l03 but register machine (not stack-only). Some implementation trials later I found the given task to be astonishingly complicated. As a first step I'll implement the stack as variables. 2010-04-20, v01: Now, "!1." and, of course, "x=1;!x." lead to Comp.Debug: accumulator Comp.Debug: 0: Lod 1 Comp.Debug: 1: Sto [ 0] Comp.Debug: 1: Lod [ 0] Comp.Debug: 1: Out 1 and "x:=1;!x." results in Comp.Debug: accumulator Comp.Debug: 0: Lod 1 Comp.Debug: 1: Sto [ 0] Comp.Debug: 1: Lod [ 0] Comp.Debug: 1: Sto [ 3] Comp.Debug: 1: Lod [ 3] Comp.Debug: 1: Sto [ 0] Comp.Debug: 1: Lod [ 0] Comp.Debug: 1: Out 1 By keeping track of the accumulator contents, the useless sequences "Sto x; Lod x" could be easily avoided. Let's do that first -- before thinking further about the harder task of avoiding the senseless storing. 2010-04-21, v02: In v01, "x:=1;!x." produced Comp.Debug: accumulator Comp.Debug: 0: Lod 1 Comp.Debug: 1: Sto [ 0] Comp.Debug: 1: Sto [ 3] Comp.Debug: 1: Sto [ 0] Comp.Debug: 1: Out 1 Since we're using a variable, one Sto (namely, Sto[3]) is acceptable. But the other ones are relicts of the old stack machine; they must be omitted. One idea is to delay code emission until somthing is done with the data, i.e. to emit in Gen.Sto and Gen.Opr but not in Gen.Val and Gen.Lod. With other words, the stack (state) is taken from Comp (run time, interpreter) and put to Gen (compile time, compiler). Obviously, the compile time stack not only contains constants (values) but variables (references) also. Since result values are not known at compile time, they cannot be put to stack. Instead, they are saved in variables and the corresponding variables are pushed. How many variables are needed? In the worst case, the whole stack is used up with temporary variables: "!1*1+(-1)*(-1)." So we have to reserve the same space as with v01. But now, we use them for (some) results only (and not for all arguments and all results). Do these variables represent a stack also? Yes. Since a stack machine puts recent results on top (and only results may require a backup), older results (earlier allocations) must lie further down. Now, "x:=1;!x." produces Comp.Debug: accumulator Comp.Debug: 0: Lod 1 Comp.Debug: 1: Sto [ 3] Comp.Debug: 1: Lod [ 3] Comp.Debug: 1: Out 1 2010-04-28, v03: "!1+2*(3+4)." produces an stack overflow. Obviously, nesting may require storing of more than three operands, see plx03-02. The (potential) requirement for an unlimited stack also means an unlimited pool of temporary variables. Fortunately, (as found out with v02) these variables are stackable, no preallocation is required. They are just put on top of the non-temporary variables, which is possible since the operand stack must be empty whenever a non-temporary variable is requested (syntax forbids assignments inside expressions). Now, "x:=1;!x." produces Comp.Debug: accumulator Comp.Debug: 0: Lod 1 Comp.Debug: 1: Sto [ 0] Comp.Debug: 1: Lod [ 0] Comp.Debug: 1: Out 1 2010-05-01, v04: Two simple generator improvements have been done on accumulator loading: 1. Reloading with the same variable is avoided. For this, another accumulator state (ai) has been introduced; it is independend of the old one (as) and could have been put to another module (lower level generator). 2. Storing and loading for commutative operations is avoided. The operands are exchanged instead. Obviously, stack usage could be reduced by allocating an variable not before (but after) expression coding - but only by one... I'll quit the accumulator work for now; shrinking the code for xmpl.plx from [plx l04 v01 (2010-04-21)] Comp.Debug: accumulator Comp.Debug: 0: Lod 100 Comp.Debug: 100: Sti [ 0] Comp.Debug: 100: Neg Comp.Debug: -100: Sti [ 0] Comp.Debug: -100: Sti [ 3] Comp.Debug: -100: Lod 10 Comp.Debug: 10: Sti [ 0] Comp.Debug: 10: Lod 2 Comp.Debug: 2: Sti [ 1] Comp.Debug: 2: Lod [ 0] Comp.Debug: 10: Div [ 1] Comp.Debug: 5: Sti [ 0] Comp.Debug: 5: Lod 20 Comp.Debug: 20: Sti [ 1] Comp.Debug: 20: Lod [ 0] Comp.Debug: 5: Mul [ 1] Comp.Debug: 100: Sti [ 0] Comp.Debug: 100: Lod 20 Comp.Debug: 20: Sti [ 1] Comp.Debug: 20: Lod [ 0] Comp.Debug: 100: Mul [ 1] Comp.Debug: 2000: Sti [ 0] Comp.Debug: 2000: Lod [ 3] Comp.Debug: -100: Sti [ 1] Comp.Debug: -100: Lod 20 Comp.Debug: 20: Sti [ 2] Comp.Debug: 20: Lod [ 1] Comp.Debug: -100: Mul [ 2] Comp.Debug: -2000: Sti [ 1] Comp.Debug: -2000: Lod [ 0] Comp.Debug: 2000: Add [ 1] Comp.Debug: 0: Sti [ 0] Comp.Debug: 0: Lod 0 Comp.Debug: 0: Sti [ 1] Comp.Debug: 0: Lod [ 0] Comp.Debug: 0: Add [ 1] Comp.Debug: 0: Sti [ 0] Comp.Debug: 0: Sti [ 4] Comp.Debug: 0: Sti [ 0] Comp.Debug: 0: Out 0 to [plx l04 v04 (2010-05-01)] Comp.Debug: accumulator Comp.Debug: 0: Lod 100 Comp.Debug: 100: Neg Comp.Debug: -100: Sto [ 0] Comp.Debug: -100: Lod 10 Comp.Debug: 10: Div 2 Comp.Debug: 5: Mul 20 Comp.Debug: 100: Mul 20 Comp.Debug: 2000: Sto [ 2] Comp.Debug: 2000: Lod [ 0] Comp.Debug: -100: Mul 20 Comp.Debug: -2000: Add [ 2] Comp.Debug: 0: Add 0 Comp.Debug: 0: Sto [ 1] Comp.Debug: 0: Out 0 suffices for now. 2010-05-04: Just noticed a missing pair of parentheses in the ebnf definition of "statement" :-(... Fixed. - Obviously, I didn't implement the parser mechanically :-p 2010-05-10: Still wrong, man! Fixed (finally?). *)