Split View: [컴파일러] 03. 간단한 구문 지시 번역기 만들기

expr   -> expr + term | expr - term | term
term   -> term * factor | term / factor | factor
factor -> ( expr ) | num | id

Grammar:
  list -> list + digit | list - digit | digit
  digit -> 0 | 1 | 2 | ... | 9

Leftmost Derivation:
  list
  => list + digit
  => list - digit + digit
  => digit - digit + digit
  => 9 - digit + digit
  => 9 - 5 + digit
  => 9 - 5 + 2

         list
        / | \
       /  |  \
     list '+' digit
    / | \       |
   /  |  \      2
 list '-' digit
  |         |
digit       5
  |
  9

string -> string + string | string - string | 0 | 1 | ... | 9

Interpretation 1: (9 - 5) + 2 = 6    Interpretation 2: 9 - (5 + 2) = 2

     string                    string
    / | \                     / | \
   /  |  \                   /  |  \
 string + string          string - string
 / | \      |               |      / | \
/  |  \     2               9     /  |  \
string - string              string + string
  |        |                   |        |
  9        5                   5        2

// Ambiguous grammar
expr -> expr + expr | expr * expr | num

// Disambiguated grammar (multiplication first, left-associative)
expr   -> expr + term | term
term   -> term * factor | factor
factor -> num

Precedence (low -> high):
  ||  (logical OR)
  &&  (logical AND)
  ==  !=
  <   >   <=  >=
  +   -
  *   /   %
  !   -   (unary)

Left-Associative:
  a - b - c = (a - b) - c
  Grammar: expr -> expr - term | term

Right-Associative:
  a = b = c  is  a = (b = c)
  Grammar: right -> letter = right | letter

Production                   Semantic Rule
----------------------------------------------
expr -> expr1 + term        expr.val = expr1.val + term.val
expr -> term                expr.val = term.val
term -> num                 term.val = num.lexval

         expr        (val = 14)
        / | \
       /  |  \
     expr + term     (val = 9, val = 5)
      |        |
    term      num
      |       (5)
    num
    (9)

Infix Notation              Postfix Notation
-------------------------------------------
9 - 5 + 2              9 5 - 2 +
9 - (5 + 2)            9 5 2 + -
a * b + c              a b * c +
a + b * c              a b c * +

Input: 9 5 - 2 +

Stack changes:
  Read 9 -> [9]
  Read 5 -> [9, 5]
  Read - -> [4]       (9 - 5 = 4)
  Read 2 -> [4, 2]
  Read + -> [6]       (4 + 2 = 6)

Result: 6

Production                   Semantic Action
----------------------------------------------
expr -> expr1 + term        print('+')
expr -> expr1 - term        print('-')
expr -> term                (none)
term -> 0                   print('0')
term -> 1                   print('1')
...
term -> 9                   print('9')

public class PostfixTranslator {
    private String input;
    private int pos;
    private char lookahead;

    public PostfixTranslator(String input) {
        this.input = input;
        this.pos = 0;
        this.lookahead = input.charAt(0);
    }

    // expr -> term rest
    // rest -> + term { print('+') } rest
    //       | - term { print('-') } rest
    //       | (epsilon)
    void expr() {
        term();
        while (true) {
            if (lookahead == '+') {
                match('+');
                term();
                System.out.print('+');
            } else if (lookahead == '-') {
                match('-');
                term();
                System.out.print('-');
            } else {
                return;
            }
        }
    }

    // term -> 0 { print('0') } | 1 { print('1') } | ... | 9 { print('9') }
    void term() {
        if (Character.isDigit(lookahead)) {
            System.out.print(lookahead);
            match(lookahead);
        } else {
            throw new RuntimeException("Syntax error");
        }
    }

    void match(char expected) {
        if (lookahead == expected) {
            pos++;
            if (pos < input.length()) {
                lookahead = input.charAt(pos);
            } else {
                lookahead = '\0'; // End of input
            }
        } else {
            throw new RuntimeException("Expected " + expected);
        }
    }

    public static void main(String[] args) {
        PostfixTranslator translator = new PostfixTranslator("9-5+2");
        translator.expr();
        // Output: 95-2+
    }
}

Input: 9-5+2

expr() called
  term() -> prints '9', lookahead = '-'
  lookahead == '-':
    match('-'), lookahead = '5'
    term() -> prints '5', lookahead = '+'
    not '+', so prints '-'
  lookahead == '+':
    match('+'), lookahead = '2'
    term() -> prints '2', lookahead = '\0'
    prints '+'
  lookahead == '\0': return

Final output: 95-2+

Parse Tree:                    AST:
      expr                      +
     / | \                     / \
   expr + term                -   2
  / | \     |                / \
expr - term num:2           9   5
  |      |
term   num:5
  |
num:9

abstract class ASTNode {
    abstract int eval();
}

class NumNode extends ASTNode {
    int value;
    NumNode(int value) { this.value = value; }
    int eval() { return value; }
}

class BinOpNode extends ASTNode {
    char op;
    ASTNode left, right;

    BinOpNode(char op, ASTNode left, ASTNode right) {
        this.op = op;
        this.left = left;
        this.right = right;
    }

    int eval() {
        switch (op) {
            case '+': return left.eval() + right.eval();
            case '-': return left.eval() - right.eval();
            case '*': return left.eval() * right.eval();
            default: throw new RuntimeException("Unknown op: " + op);
        }
    }
}