214 - Code Generation

[Palomar]

On input:
AB+CD+-

we are supposed to generate:
L A
A B
ST $1
L C
A D
N
A $1

But why the last A $1? It would only be present *if* the input had an extra + at the end, right?

Or am I wrong?

[stubbscroll]

After reading the problem description, I don't know exactly how the output is supposed to be. I'm wondering about this phrase in the problem description:

The original order of the operands must be preserved in the assembly code.

What does it really mean? Does is say that when AB+ is to be processed, it should be processed as A+B instead of B+A? Or does it mean that the operands should be processed in the same order as in the input? If that interpretation is used, the input

Code: Select all

ABC+*

will be generated to:

Code: Select all

L A
ST $1
L B
A C
M $1

instead of the shorter

Code: Select all

L B
A C
M A

Anyone who knows the correct interpretation? I got WA when outputting the operands in the same order as in the input (as in the longer code above), I haven't tried the other way yet... It seems I'm not the only one having trouble, considering the low AC rate.

[little joey]

It means that the operands should be processed in the same order as they appear in the input. So your first code fragment is correct.
Think of it as reading the input character by character, then every time an operand is read, it's either loaded into the register (possibly followed by a store), or directly used in a mathematical instruction.

There is one other issue: for the input "XYZ--" the corrector currently only accepts

Code: Select all

L X
ST $9
L Y
S Z
N
A $9

but it rejects

Code: Select all

L X
ST $9
L Y
S Z
S $9
N 

The corrector should be updated, but AFAIK that has not happened yet.

[stubbscroll]

Thanks for the clarification, also about the case the corrector doesn't accept. My code already produces the first output, because the sample output also does it this way (except I use $1 instead of $9, which hopefully shouldn't matter). However, my code might contain many bugs, as it was very tricky to write. I might rewrite it from scratch some day after I have some more experience...

[little joey]

(except I use $1 instead of $9, which hopefully shouldn't matter)

You can use any $x, in any order, as long as x is a digit.

[stubbscroll]

I'm still struggling with WA on this problem, so I have another question. Is the following output correct?

Code: Select all

AB@-

Code: Select all

L A
ST $1
L B
N  <- @ encountered, according to restriction (4) this should be output immediately
N  <- here we prepare for the subtraction
A $1

The output looks rather silly with the two N's, but this is what I get when following the restrictions. However, according to sample input 2, it's allowed to do N, A instead of S. Is this a legal output to the above input?

Code: Select all

L A
A B

I would think no, as there is no assembly code for @, but it would be nice to get this confirmed by someone with AC.

[little joey]

Yes, your first output is correct (it will get Accepted), but I doubt that any Accepted program will exactly produce this output .

(In my postings I'm trying to give you a hint, without giving it all away).

[mf]

Is this I/O correct?

Input:

Code: Select all

A
AB@/
ABC@+DE*F-//
ABC+DE-F**/
AA+
AAA++
AAAA+++
ABABA++++

Output:

Code: Select all

L A

L A
ST $1
L B
N
ST $2
L $1
D $2

L A
ST $1
L B
ST $2
L C
N
A $2
ST $2
L D
M E
S F
ST $3
L $2
D $3
ST $2
L $1
D $2

L A
ST $1
L B
A C
ST $2
L D
S E
M F
M $2
ST $2
L $1
D $2

L A
A A

L A
ST $1
L A
A A
A $1

L A
ST $1
L A
ST $2
L A
A A
A $2
A $1

L A
ST $1
L B
ST $2
L A
ST $3
L B
A A
A $3
A $2
A $1

[stubbscroll]

Thanks little joey for your good help and mf for posting the i/o data! I just got accepted. It turned out to be a stupid error and another small mistake, I forgot to print a blank line when the expression consisted of only one letter. I also didn't realise that the same letters could be used more than once, but my code already handled this.

mf: Your output is correct.

[mf]

Oh, finally I got accepted too!
I also made a stupid mistake, I assumed "$0" didn't exist. The sample output is so misleading!

[TheKiler]

Why for a single letter (or rather letters at the end of the expression at all) there should be and output consisting of only loading them into the register? (I assume that mf's output code would be AC - and there is the "single letter" case)

It is against rule 4 - it states "assembly code must be generated for each OPERATOR...", and The Input part states "expression operands are single letters and OPERATORS are the normal arithmetic operators (+, -, *, /) and unary negation (@)."

That's why I think there should be no SIC-assembly-code output for those "lonely" letters at all until an operator comes in!


Also I found the following code to divide two values when the divisor (B) is already in the register:

Code: Select all

->state: $x == A , reg == B

D $x
-> $x == A , reg == B/A

ST $x
-> $x == B/A , reg == B/A

D $x
-> $x == B/A , reg == 1

D $x
-> $x == B/A , reg == A/B

I don't know why this would be wrong. I think that problem contents DO NOT state it is an integer division, so the above code is correct and better than:

Code: Select all

ST $x+1
L $x
D $x+1

because it uses less temporaries (rule 5).

[mf]

Why for a single letter (or rather letters at the end of the expression at all) there should be and output consisting of only loading them into the register? (I assume that mf's output code would be AC - and there is the "single letter" case)

It is against rule 4 - it states "assembly code must be generated for each OPERATOR...", and The Input part states "expression operands are single letters and OPERATORS are the normal arithmetic operators (+, -, *, /) and unary negation (@)."

But if my program printed nothing for this "single letter" case, then
if would violate "An arithmetic operation replaces the contents of the register with the expression result."

Also I found the following code to divide two values when the divisor (B) is already in the register:

I think the second piece of code is better.
If this machine were real, your first code would attempt to divide by zero when the dividend is zero.

[TheKiler]

My point is that until specification is made more specific the "lonely letters" cases should not happen to appear in the tests. Let me explain this by showing two different views:

VIEW ONE
If the expression result for "A" is A, then what is the expression result for "AB"? It would have to be B, because only B stays in the register as a result of loading. So, the only solution (taking into account that we have to use as little commands as needed and that no arithmetic operator appears in the expression) is:

Code: Select all

L B

which is nonsense.


VIEW TWO
As I have written in the last post, if we load a "lonely letter" into the register, we are assuming it is an operator, thus we have to load every letter into the register as they appear, not when an action upon them is taken. Eventually, for expression "AB+" it would be:

Code: Select all

L A
ST $1
L B
A $1

and not:

Code: Select all

L A
A B

Also, there is an error in your thinking.

it would violate "An arithmetic operation replaces the contents of the register with the expression result."

When the expression consists of only letters there is no ARITHMETIC OPERATION, since there is no ARITHMETIC OPERATOR.



As for dividing - yes, you are right that there is a "probability" of a division by zero error for my code, but when using the second code we assume that B != 0 . Neither this is covered by the problem contents and it is another argument for making the specification more specific.

[mf]

If the expression result for "A" is A, then what is the expression result for "AB"?

I think that "AB" does not qualify as a "legitimate postfix expression," and so it shouldn't appear in the input.

It seems that we interpret the rule #4 differently.
In my opinion, it does not say that it's allowed to generate the code after, and only after, an operator is encountered.
So, my program generates some code in the "lone letter" case, though I don't treat this letter as an operator.

As for dividing - yes, you are right that there is a "probability" of a division by zero error for my code, but when using the second code we assume that B != 0. Neither this is covered by the problem contents and it is another argument for making the specification more specific.

When B=0, it's impossible to compute the expression anyway.
My point was that your first division code couldn't correctly compute, for example, AB@/ when A=0, B=1.

Also, there is an error in your thinking.

When the expression consists of only letters there is no ARITHMETIC OPERATION, since there is no ARITHMETIC OPERATOR.

Sorry, I just put the wrong quote.
As I understand, the generated code needs to compute the expression and put the result into the register.
But now I see this is not explicitly stated anywhere. The problem's statement definitely has to be changed.

[TheKiler]

Indeed, let's sum the needed changes up:

-Corrector program must be updated (little joey)

The statement should claim that:
- [rule] the expression is mathematically correct and thus can be treated as calculable (so the solution author doesn't have to assume anything is correct or not - like: "the machine is real" or "an operand is not equal to zero")
-rule 4 has to be changed to be unambiguous into something like: "For each operator in the expression, assembly code must be generated as soon as the operator is encountered" - different order of the words makes it unambiguous
- [rule] the register has to contain the expression value when execution of generated code is finished