Mazi 프로그램 해석기(Interpreter) – (3)

• • Leave a reply

Copyright (c) 2015-, All Rights Reserved by Kwanghoon Choi
(아래 자바 프로그래밍 강의 교재의 내용을 자유롭게 이용하되 다른 웹 사이트 등을 통한 배포를 금합니다.)

  1. Mazi 해석기 프로그램

Mazi 해석기 프로그램의 전체 구조는 다음의 함수(정적 메소드)들로 구성되어 있다.

  • void main(String[] args)
    • void repl(Scanner scanner)
      • int evalExp(HashMap<String,Integer> env, int operand1, String operator1, StringTokenizer stz)
        • int evalOperand(HashMap<String,Integer> env, String operand)
        • int evalExpr(int operand1, String operator, int operand2)
        • int precedence(String operator)
        • Associativity associativity(String operator)

Mazi 해석기 프로그램을 작성하기 위해 사용하는 몇가지 메써드들을 먼저 설명한다.

  • evalOperand
  • evalExpr
  • precedence
  • associativity

3.1 evalOperand

메써드 evalOperand는 첫번째 인자는 변수와 값의 매핑 테이블이고 두번째 인자는 피연산자이다. 피연산자는 숫자로 구성된 문자열이거나 변수 이름이 가능하다.

  • 피연산자가 숫자 문자열이면 숫자로 바꾸어 리턴하고,
  • 변수 이름이면 매핑 테이블을 참고해서 해당 숫자를 찾아 리턴한다.

evalOperand를 사용하는 Java 코드 예를, 피연산자(operand)가 숫자인 경우와 변수인 경우 최소 두 가지를 작성하면 다음과 같다.

public static int evalOperand(HashMap<String,Integer> env, String operand) {
  int result = 0;
        
  if ( Character.isLetter(operand.charAt(0)) ) { // operand is a variable
        Integer d = env.get(operand);
        if ( d == null ) {
                System.err.println("Undefined variable: " + operand);
        } else {
                result = d;
        }
  } else { // operand is a number
        result = new Integer(operand);
  }
        
  return result;
}

[연습문제 1] 변수도 아니고 숫자도 아닌 경우 (예: "1abc") 오류 메시지를 출력하도록 위의 프로그램을 수정하시오.

3.2 evalExpr

메써드 evalExpr은 int 형의 두 피연산자와 연산자를 받아 계산하고 그 결과를 리턴한다. Mazi의 연산자 +, -, *, /를 고려한다.

public static int evalExpr(int operand1, String operator, int operand2)
{
  int result = 0;

  switch ( operator.charAt(0) ) {
  case '+':
        result = operand1 + operand2;
        break;
  case '-':
        result = operand1 - operand2;
        break; 
  case '*':
        result = operand1 * operand2;
        break;
  case '/':
        result = operand1 / operand2;
        break;  
  default:
        System.err.println("Unsupported operator: " + operator);
  }
    
  return result;
}

[연습문제 2] evalExpr 메소드를 호출해서 사용하는 Java 코드 예를 한가지 작성하시오. 나머지 연산자 %를 지원하도록 이 메소드를 수정하시오. 이 메소드를 호출해 나머지 연산을 사용하는 Java 코드 예를 한가지 작성하시오.

3.3 precedence와 associativity

Mazi 식은 서로 다른 연산자로 구성될 수 있다. 예를 들어 1 + 2 * 3 / z의 식에서 3개의 연산자 +, *, /를 사용하는데 어느 우선 순위가 높은지에 따라 계산 순서를 결정한다. Java와 같이 *와 /는 우선 순위가 같고 +는 우선 순위가 낮다. 이때 *와 / 연산자를 + 연산자보다 먼저 계산한다. 이 규칙을 우선 순위(precedence) 규칙이라고 한다.

하지만 *와 /는 우선순위가 같은 연산자이므로 우선 순위 규칙만으로 계산 순서를 정할 수 없고 결합 규칙(associativity)에 의해 결정한다. Java와 같이 *와 /는 왼쪽부터 차례대로 계산하는 순서로 정한다.

따라서 예로 주어진 식에서 *, /, + 순서대로 계산한다.

메써드 predecence와 associativity는 인자로 연산자를 받아 우선순위와 결합순서를 리턴한다.

public static int precedence (String operator) {
  switch ( operator.charAt(0) ) {
        case '+': 
        case '-':
                return 2;
        case '*':
        case '/':
                return 4;
        default:
                System.err.println("Unsupported operator: " + operator);
                return 0;
        }
}

enum Associativity {
     LeftToRight, RightToLeft;
}

public static Associativity associativity(String operator) {
  switch ( operator.charAt(0) ) {
        case '+': 
        case '-':
        case '*':
        case '/':
                return Associativity.LeftToRight; // Left to Right
        default:
                System.err.println("Unsupported operator: " + operator);
                return Associativity.LeftToRight;
        }
}

[연습문제 3] precedence 메소드의 코드를 보고 + 연산자와 * 연산자의 우선 순위가 무엇으로 정의되어 있는지 살펴보시오.

[연습문제 4] + 연산자가 * 연산자 보다 우선순위가 낮도록 정의되어 있다. precedence 메소드가 리턴하는 숫자가 높으면 우선 순위가 높은지 아니면 리턴하는 숫자가 낮으면 우선 순위가 높은지 판단하시오.

[연습문제 5] 나머지 연산자 %를 이 메소드에 추가하시오. 우선순위는 Java에서의 나머지 연산자의 우선 순위를 참고하시오.

[연습문제 6] 만일 식으로 x = y = z = 123+456과 같이 대입문을 연결해서 사용하는 것을 허용한다고 가정하자. 대입 연산자의 우선순위와 결합성을 Java언어를 기준으로 조사하여 위의 코드에 대입 연산자를 처리하는 방법에 대한 아이디어를 간단히 기술하시오.

3.4 Mazi 해석기 주 모듈

앞에서 정의한 여러 메써드들을 활용하여 Mazi 프로그램 해석기의 주 모듈을 작성한다.

  • main, repl
  • int evalExpr(HashMap<String,Integer> env, int operand1, String operator1, StringTokenizer stz)

main 메소드에서 repl을 호출하고, repl 메소드는 다음과 같은 Read-Eval-Print를 반복한다.

  • 변수 이름과 값의 매핑 테이블을 표현하는 객체를 만들고 다음 과정을 반복한다.
    • 사용자로 부터 한 라인을 입력 받고
    • 이 라인으로부터 연산자와 피연산자를 분리할 StringTokenizer 객체를 만들고
    • (앞으로 설명할) evalExpr 메써드를 호출하여 식을 계산하고
    • 그 결과를 출력한다.
public static void main(String[] args) {
  Scanner scanner = new Scanner(System.in);
  repl(scanner);
}

public static void repl(Scanner scanner) {      
  HashMap<String,Integer> env = new HashMap<String,Integer>();
  env.put("x", 123);  // 필요한 변수의 값을 미리 저장
  env.put("y", 123);  // 나중에 x = Expr 문장을 실행해서 env에 값을 추가

  while ( scanner.hasNext() ) {
        String line = scanner.nextLine();
        StringTokenizer stz = new StringTokenizer(line);
        if (stz.countTokens() > 0) {
            int result = evalExpr(env, 0, "+", stz);
            System.out.println("Evalute " + line + " to " + result);
        }
  }
}

evalExpr 메써드는 변수 이름과 값의 매핑 테이블과 사용자가 입력한 식을 담고 있는 StringTokenizer 객체를 인자로 받는다. 추가로 int 형의 인자와 String형의 연산자를 하나 추가로 받는다. 이들 추가 인자는 메써드를 간략하게 작성하기 위해 도입한 것이다.

예를 들어, 사용자가 입력한 라인이 "1 + 2"라면 main 메써드에서

evalExpr ( 매핑 테이블 env,
           0,
           "+",
           StringTokenizer 객체 ===> "1", "+", "2"
)

을 호출하고, 그 결과 0 + 1 + 2를 해서 3이라는 결과를 얻는다. 0과 "+" 인자는 evalExpr 메써드를 간단하게 만들기 위한 추가 인자이다. 참고로 임의의 식에 0을 더해도 원래 식의 결과와 동일한 결과를 낸다.

evalExpr 메써드의 실행 과정은 다음과 같다.

  • (1) StringTokenizer 객체가 0개의 토큰을 담고 있다면 사용자는 아무것도 입력하지 않은 경우이고 에러 메시지를 출력한다.
  • (2) 1개의 토큰을 담고 있다면 변수 이름이거나 숫자이므로 evalOperand 메써드를 통해 그 값을 구해 결과(result)로 리턴한다.

evalExpr (env, 0, "+", ["123"]) ===> 0 + 123 ===> 123
evalExpr (env, 0, "+", ["x"]) ===> 0 + env(x)

  • (3) 3개 이상의 토큰을 담고 있다면 evalExpr의 두번째 인자 operator1로 주어진 연산자와 3개의 토큰 중 두번째 토큰으로 주어진 연산자가 있는, 즉 (적어도) 2개의 연산자를 포함하는 식이다.
evalExpr (env, 0, "+", ["1", "*", "2", "+", "3"])
===> 0 + evalExpr (env, 1, "*", ["2", "+", "3"])
===> 0 + evalExpr (env, 1 * 2, "+", ["3"])
===> 0 + (2 + 3)
===> 5

evalExpr (env, 0, "+", ["1", "+", "2", "*", "3"])
===> evalExpr (env, (0 + 1), "+", ["2", "*", "3"])
===> 1 + evalExpr (env, 2, "*", ["3"])
===> 1 + (2 * 3)
===> 1 + 6
===> 7
  • (3.1) 이때 두 연산자 중 연산순위에 따라 어떤 연산자를 먼저 계산할지 정해서 계산을 진행해야 한다. 예를 들어, 1 * 2 + 3과 같은 식이라면 1 * 2를 먼저하고 3을 나중에 더한다.
  • (3.1)의 예:
  • oeprand1 ==> 1
  • operator1 ==> "*"
  • operand2 ==> 2
  • operator2 ==> "+"

evalExpr(operand1, operator1, operand2)를 계산하면 1 * 2로 2를 얻고, 다시

evalExpr (매핑 테이블 env,
        2,
        "+",
        StringTokenizer 객체 stz ===> "3"
)

와 같이 호출해서 나머지 계산 2 + 3으로 최종 식의 결과 5를 얻는다.

  • (3.2) 만일 1 + 2 * 3과 같이 +와 *가 차례대로 나타나면 *를 먼저 계산하고 +를 나중에 계산한다.
  • (3.2)의 예:
  • oeprand1 ==> 1
  • operator1 ==> "+"
  • operand2 ==> 2
  • operator2 ==> "*"
evalExpr(매핑 테이블 env,
        2,
        "*",
        StringTokenizer 객체 stz ===> "3"
)

를 호출해서 2*3을 먼저 계산한다. 그 다음에 1을 더해 7을 얻는다.

  • (3.3) 만일 1 + 2 + 3과 같이 동일한 연산자가 나타나면 결합 규칙에 따라 왼쪽부터 계산하는지 오른쪽부터 계산하는지 판단한다. 왼쪽부터 오른쪽으로 계산하면 (3.1)과 같은 순서로 계산하고 (3.3.1) 오른쪽부터 왼쪽으로 계산하면 (3.2)의 순서로 계산한다 (3.3.2).

 

  • (4) 2개의 토큰을 담고 있다면 Mazi 식에서 2개의 토큰으로 구성된 식은 정의되어 있지 않으므로 에러 메시지를 출력한다.
public static int evalExpr(HashMap<String,Integer> env, int operand1, String operator1, StringTokenizer stz) {
  int result = 0;

  // (1)        
  if (stz.countTokens() == 0) {
        System.err.println("Tokens not available.");
  } 
  // (2)
  else if (stz.countTokens() == 1) {
        String token = stz.nextToken();
        int operand2 = evalOperand(env, token);
            
        result = evalExpr (operand1, operator1, operand2);
  } 
  // (3)
  else if (stz.countTokens() >= 3) {
        String tokenOperand2 = stz.nextToken();
        int operand2 = evalOperand(env, tokenOperand2);
            
        String operator2 = stz.nextToken();

       // (3.1)         
        if ( precedence(operator1) > precedence(operator2) ) {
                int d = evalExpr(operand1, operator1, operand2);
                result = evalExpr(env, d, operator2, stz);
        } 
        // (3.2)            
        else if ( precedence(operator1) < precedence(operator2) ) {
                int d = evalExpr(env, operand2, operator2, stz);
                result = evalExpr(operand1, operator1, d);
        } 
        // (3.3)            
        else {
                // (3.3.1)
                if ( associativity(operator1) == Associativity.LeftToRight ) {
                        int d = evalExpr(operand1, operator1, operand2);
                        result = evalExpr(env, d, operator2, stz);
                } 
                // (3.3.2)
                else { // Associativity.RightToLeft
                        int d = evalExpr(env, operand2, operator2, stz);
                        result = evalExpr(operand1, operator1, d);
                }
        }
  }
  // (4)
  else {
        System.err.println("Something wrong:");
        while ( stz.hasMoreTokens() ) {
                System.err.print( stz.nextToken() + " ");
        }
        System.err.println();
  }
    
  return result;
}

[연습문제 7]  위의 evalExpr 메소드를 통해 1 * 2 + 3을 계산하기 위한 Java 코드의 예를 작성하시오.

[연습문제 8] 앞의 연습문제에서 1 * 2 + 3을 계산하기 위해 evalExpr 메소드를 호출하고, 이 메소드 안의 코드를 실행하는 순서대로 (1), (2), (3), (3.1), (3.2), (3.3), (4) 나열하시오.

[연습문제 9] 이번에는 1 + 2 * 3을 계산하기 위한 Java 코드의 예를 작성하시오.

[연습문제 10] 1 + 2 * 3을 계산하기 위해 evalExpr 메소드를 호출하고, 이 메소드 안의 코드를 실행하는 순서대로 (1), (2), (3), (3.1), (3.2), (3.3), (4)를 나열하시오.

 

지금까지 만든 메써드들을 Interpreter 클래스에 선언해서 .java 파일을 만들고 컴파일해서 실행한다.

// Interpreter.java


import java.util.HashMap;
import java.util.Scanner;
import java.util.StringTokenizer;

public class Interpreter {

  // 위의 모든 메써드들

}

$ javac Interpreter.java

$ java Interpreter

1 <=== 사용자가 입력한 Mazi 프로그램의 식
Evalute 1 to 1

1 + 2 * 3 <=== 사용자가 입력한 Mazi 프로그램의 식
Evalute 1 + 2 * 3 to 7

1 * 2 + 3 <=== 사용자가 입력한 Mazi 프로그램의 식
Evalute 1 * 2 + 3 to 5

x + 1 <=== 사용자가 입력한 Mazi 프로그램의 식
Evalute x + 1 to 1
Undefined variable: x

사용자 입력은 각 연산자와 피연산자 사이에 공백을 두어야 StringTokenizer로 하여금 독립된 토큰으로 분리할 수 있다. 즉 1+ 2 * 3으로 입력하면 1+를 하나의 토큰으로 잘못 오인하게 되어 에러가 발생한다.

main 메써드에서 변수 이름과 값의 매핑 테이블을 만들어 놓고 특별히 추가한 것이 없으므로 사용자가 식 x + 1을 입력하면 변수 x가 정의되지 않았다는 에러가 발생한다. main 메써드에서 미리 적절한 변수의 값을 지정하여 이런 에러가 발생하지 않고 지정된 x값으로 식을 계산할 수 있다.

[연습문제 11] 위의 Interpreter 클래스에서 각 연산자의 계산 순서를 화면에 출력하도록 출력 문장을 추가하시오.

[연습문제 12] 위의 Interpreter 클래스를 다음 세가지 종류의 문장을 지원하도록 확장하시오.

Stmt ::= variable = Expr
      | READ variable
      | PRINT Expr

힌트. 아래의 evalStmt 메써드만 추가하고, repl에서 이 메써드를 호출하게 수정.

public static void repl(Scanner scanner) {       
        HashMap<String,Integer> env = new HashMap<String,Integer>();
        
        while ( scanner.hasNext() ) {
                String line = scanner.nextLine();
                StringTokenizer stz = new StringTokenizer(line);

                // [이전 코드]
                // int result = evalExpr(env, 0, "+", stz);
                // System.out.println("Evalute " + line + " to " + result);

                // [새로운 코드]
                evalStmt(env, stz);
        }
}

public static void evalStmt(HashMap<String,Integer> env, StringTokenizer stz) {

  // ???

}

힌트:

입력 받은 문장의 첫번째 토큰이 변수이면 할당문(variable = Expr)으로, READ이면 입력문(READ variable)으로, PRINT이면 출력문(PRINT Expr)으로 구분한다.

할당문: 첫번째 토큰은 변수, 두번째 토큰은 "="이고, 나머지 토큰은 식을 구성한다. 따라서 세번째 이후의 토큰을 갖는 StringTokenizer 객체를 가지고 evalExpr 메소드를 호출하면 이 식의 값을 계산할 수 있다. 그 값을 첫번째 토큰인 변수와 쌍으로 환경(env)에 put 메소드로 추가(또는 없데이트)한다.

입력문: 첫번째 토큰은 READ 키워드, 두번째 토큰은 변수이다. 먼저 Scanner 객체의 nextInt 메소드로 사용자로 부터 int 타입의 값을 입력받는다. 두번째 토큰인 변수와 입력받은 값을 쌍으로 환경(env)에 put 메소드로 추가(또는 업데이트) 한다.

출력문: 첫번째 토큰은 PRINT 키워드, 두번째 이후의 토큰들은 식을 구성한다. 두번째 이후의 토큰들을 갖는 StringTokenizer 객체를 가지고 evalExpr 메소드로 이 식의 값을 계산한다. 식의 계산 결과 값을 println 메소드를 이용하여 화면에 출력한다.

Leave a Reply

Your email address will not be published. Required fields are marked *