求职前练手编译器：后缀表示法下的类型转换问题咨询

Hey there! First off, kudos on building a compiler as practice—super solid way to prep for dev roles. Let's dig into how to tackle typecasting in post-fix (Reverse Polish) notation, using your examples as a guide.

Core Principle #

In post-fix evaluation, typecasting happens right before executing an operation. The key is to:

1. Track the type of every value on your stack (alongside the value itself—your annotated tokens like STR[1,0] are perfect for this!)
2. Define clear rules for how types should be converted based on the operator and the operands' types.

Let's break down your two examples step by step.

Example 1: String + Numeric Addition ("1.0 plus 2 equals" + 1.0 + 2) #

Your post-fix sequence: STR[1,0]:"1.0 plus 2 equals" DBL[1,22]:1.0 INT[1,28]:2 ADD[1,26]:+ ADD[1,20]:+

Most languages treat string + any value as string concatenation, so here's how to process it:

1. Push literals to stack (each entry stores type + value):

   • Stack after each push:

     [ {type: "string", value: "1.0 plus 2 equals"} ]
     [ {type: "string", value: "1.0 plus 2 equals"}, {type: "double", value: 1.0} ]
     [ {type: "string", value: "1.0 plus 2 equals"}, {type: "double", value: 1.0}, {type: "int", value: 2} ]
     

2. First + operator:

   • Pop 2 (int) and 1.0 (double). Since this is numeric addition, convert the int to double first.
   • Calculate 1.0 + 2.0 = 3.0, push {type: "double", value: 3.0} to stack.
   • Stack now: [ {type: "string", value: "1.0 plus 2 equals"}, {type: "double", value: 3.0} ]

3. Second + operator:

   • Pop 3.0 (double) and the string. Convert the double to its string representation ("3.0").
   • Concatenate: "1.0 plus 2 equals" + "3.0" = "1.0 plus 2 equals3.0"
   • Push the resulting string to stack.

Example 2: Mixed Integer/Float Arithmetic (1+2/(3-4)) #

Your post-fix sequence: INT[0,0]:1 INT[0,2]:2 INT[0,5]:3 INT[0,7]:4 SUB[0,6]:- DIV[0,3]:/ ADD[0,1]:+

Here, we need to handle integer division vs. floating-point division, and preserve precision where needed. Let's assume you want to avoid integer division truncation (adjust if your target language uses integer division by default):

1. Push literals to stack:

   • Stack: [ {type: "int", value:1}, {type: "int", value:2}, {type: "int", value:3}, {type: "int", value:4} ]

2. - operator:

   • Pop 4 and 3, subtract to get -1 (int). Push {type: "int", value: -1}.
   • Stack: [ {type: "int", value:1}, {type: "int", value:2}, {type: "int", value: -1} ]

3. / operator:

   • Pop -1 (int) and 2 (int). Since division can produce non-integers, convert both to doubles.
   • Calculate 2.0 / (-1.0) = -2.0, push {type: "double", value: -2.0}.
   • Stack: [ {type: "int", value:1}, {type: "double", value: -2.0} ]

4. + operator:

   • Pop -2.0 (double) and 1 (int). Convert the int to double.
   • Calculate 1.0 + (-2.0) = -1.0, push {type: "double", value: -1.0}.

General Rules to Formalize #

To make this scalable, define a type conversion hierarchy (adjust based on your compiler's target semantics):

• String takes precedence for +: If either operand is a string, convert the other to string and concatenate.
• Floating-point takes precedence for arithmetic ops: If any operand is a double/float, convert all operands to that type to avoid precision loss.
• Integer operations with potential non-integer results: For division, square roots, etc., decide whether to auto-convert to float (like Python) or keep integer division (like C). Document this rule in your compiler's spec!

Quick Pseudocode for Stack Processing #

Here's a simplified snippet to implement this logic:

stack = []
for token in postfix_tokens:
    if token.is_literal():
        stack.append({"type": token.type, "value": token.value})
    elif token.is_operator():
        op2 = stack.pop()
        op1 = stack.pop()
        
        if token.operator == "+" and (op1["type"] == "string" or op2["type"] == "string"):
            # String concatenation
            val1 = str(op1["value"])
            val2 = str(op2["value"])
            result = val1 + val2
            stack.append({"type": "string", "value": result})
        elif token.is_arithmetic():
            # Convert to highest precision type
            target_type = "double" if op1["type"] == "double" or op2["type"] == "double" else "int"
            if target_type == "double":
                val1 = float(op1["value"])
                val2 = float(op2["value"])
            else:
                val1 = op1["value"]
                val2 = op2["value"]
            
            # Apply operator
            if token.operator == "+":
                result = val1 + val2
            elif token.operator == "-":
                result = val1 - val2
            elif token.operator == "*":
                result = val1 * val2
            elif token.operator == "/":
                # Handle division rule here
                result = val1 / val2 if target_type == "double" else val1 // val2
            
            stack.append({"type": target_type, "value": result})

The main thing is to be consistent with your type rules—once you define them, stick to them across all operations.

内容的提问来源于stack exchange，提问作者Michael Choi