[프로그래밍언어론📐] 3장 언어 설계와 파서 구현

출처 : 프로그래밍 언어론 : 원리와 실제 (창병모, 인피니티북스, 2021)

 

3.1 프로그래밍 언어 S

1) 샘플 프로그래밍 언어

- 대화형 인터프리터 방식으로 동작 가능
- 블록 중첩을 허용
- 실행 전에 타입 검사를 수행하는 강한 타입 언어
- 어휘분석기, 파서, AST, 타입 검사기, 인터프리터 순차 구현
 

2) 언어 S의 문법

<program> → {<command>}
<command> → <decl> | <stmt> | <function>
<decl> → <type> id [= <expr>];
<stmt> → id = <expr>;
| '{' <stmts> '}'
| if (<expr>) then <stmt> [else <stmt>]
| while (<expr>) <stmt>
| read id; | print <expr>; | let <decls> in <stmts> end;

<stmts> → {<stmt>}
<decls> → {<decls>}
<type> → int | bool | string

 

3) 프로그래밍 언어 S

- 언어 S의 프로그램 : 명령어(<command>)들로 구성
- 명령어

• 변수 선언 : <decl>
• 함수 정의 : <function>
• 실행 문장 : <stmt>

- 실행 문장

• 대입문, 조건 if문, 반복 while문
• 입력 read문, 출력 print문
• 복합문 : 괄호로 둘러싸인 일련의 실행 문장들
• let문 : 지역 변수 선언과 일련의 실행 문장들

- 변수 선언 : 정수, 부울, 스트링 타입
 

3.2 추상 구문 트리

1) 파서와 AST

- 어휘 분석기 (lexical analyzer)

• 입력 스트링을 읽어서 토큰 형태로 분리하여 반환

- 파서(parser)

• 입력 스트링을 재귀 하강 파싱
• 해당 입력의 AST를 생성해 반환

- 추상 구문 트리 (abstract syntax tree ; AST)

• 입력 스트링의 구문 구조를 추상적으로 보여주는 트리

- 인터프리터 (intepreter)

• 각 문장의 AST를 순회하면서 각 문장의 의미에 따라 해석하여 수행

2) 유도 트리

 

3) 추상 구문 트리

- 입력 스트링의 구문 구조를 추상적으로 보여주는 트리
- 실제 유도 트리에 나타나는 세세한 정보를 모두 나타내지는 않음
- 수식의 AST :  연산을 중심으로 요약해서 표현
 

4) 수식의 AST

- 이항(Binary) 수식과 단항연산(Unary) 수식으로 구분하여 구현

class Binary extends Expr { // 이항 연산 수식의 AST 구현
    Operator op;
    Expr expr1, expr2;
    
    Binary (Operator o, Expr e1, Expr e2) {
        op = o; expr1 = e1, expr2 = e2;
    }
}

 
- 식별자(Identifier), 값(Value)도 하나의 수식이 될 수 있다.
- Expr = Identifier | Value | Binary | Unary
 

5) 변수 선언의 AST

- 구문법 : <type> id = <expr>
- AST : Type type;  Identifier id; Expr expr;

6) 대입문 Assignment의 AST

- 구문법 : id = <expr>;
- AST : Assignment = Identfier id; Expr expr

class Assignment extends Stmt {
    Identifier id;
    Array ar = null;
    Expr expr;

    Assignment (Identifier t, Expr e) {
        id = t;
        expr = e;
    }
}

 
 

7) Read 문, Print 문의 AST

- 구문법

• read id;
• print <expr>;

- AST 

 

8) 복합문의 AST

- 구문법 : <stmts> → {<stmt>}
- AST : Stmts = Stmt*

class Stmts extends Stmt {
    public ArrayList<Stmt> stmts = new ArrayList<Stmt>();
}

 
 

9) If 문의 AST

- 구문법 : if (<expr>) then <stmt> [else <stmt>]
- AST : Expr expr; Stmt stmt1; Stmt stmt2

10) While 문의 AST

- 구문법 : while (<expr>) <stmt>
- AST : Expr expr; Stmt stmt;

11) Let 문의 AST

- 구문법 : let <decls> in <stmts> end
- AST : Decls decls; Stmts stmts;

3.3 어휘 분석기 구현

1) 어휘분석과 토큰

- 어휘분석 (lexical analysis)

• 소스 프로그램을 읽어들여 토큰(token)으로 분리
• 어휘 분석기(lexical analyzer) 또는 스캐너(scanner)

- 토큰

• 문법에서 터미널 심볼에 해당하는 문법적 단위
• 식별자 (identifier)
• 상수 리터럴 (constant)
• 예약어 (keyword)
• 연산자 (operator)
• 구분자 (delimiter)

 

2) 예약어

- 예약어 또는 키워드 : 언어에서 미리 그 의미와 용법이 지정되어 사용되는 단어
ex)

BOOL("bool"),TRUE("true"), FALSE("false"), IF("if"), THEN("then"), STRING("string"),
WHILE("while"), VOID("void"),  FUN("fun"), RETURN("return"), LET("let"),
IN("in"), END("end"), READ("read"), PRINT("print")

 

3) 식별자

- 식별자

• ID : 변수 혹은 함수의 이름을 나타내며 토큰 이름
• 식별자 : 첫 번째는 문자이고 이어서 0개 이상의 문자 혹은 숫자들로 이루어진 스트링

- 정규식(regular expression) 형태로 표현

• ID : letter(letter | digit)*
• letter = [a-zA-Z]
• digit = [0-9]

 

4) 정규식

-정의 1 : M과 N이 정규식이면 다음은 모두 정규식이다.

• x : 문자 x
• M | N : M 또는 N
• MN : M 다음에 N이 나타나는 집합
• M* : M이 0번 이상 반복됨
• M+ : MM*을 나타내며 M이 한 번 이상 반복
• M? : M이 0번 또는 1번 나타남
• [..] : 문자 집합

 

5) 연산자/구분자

- 연산자

ASSIGN("="), EQUAL("=="),  LT("<"), LTEQ("<="), GT(">"),  
GTEQ(">="),  NOT("!"),    NOTEQ("!="), PLUS("+"), MINUS("-"), 
MULTIPLY("*"), DIVIDE("/"), AND("&"), OR("|")

- 구분자

LBRACE("{"), RBRACE("}"), LBRACKET("["), RBRACKET("]"),
LPAREN("("), RPAREN(")"), SEMICOLON(";"), COMMA(","), EOF("<<EOF>>")

 

6) 토큰 구현

enum Token {
     BOOL("bool"),CHAR("char"), ELSE("else"), FALSE("false"), FLOAT("float"), 
     STRING("string"), IF("if"), INT("int"),  TRUE("true"), WHILE("while"), 
     RETURN("return"), VOID("void"), FUN("fun"),  THEN("then"), LET("let"), 
     IN("in"), END("end"), READ("read"), PRINT("print"), DO("do"),  FOR("for"), 
     EOF("<<EOF>>"), 
     LBRACE("{"), RBRACE("}"), LBRACKET("["), RBRACKET("]"),
     LPAREN("("), RPAREN(")"), SEMICOLON(";"), COMMA(","),
     ASSIGN("="), EQUAL("=="),  LT("<"), LTEQ("<="), GT(">"),  
     GTEQ(">="),  NOT("!"),    NOTEQ("!="), PLUS("+"), MINUS("-"), 
     MULTIPLY("*"), DIVIDE("/"), AND("&"), OR("|"), ID(""), 
     NUMBER(""), STRLITERAL(""); 

    private String value; 

    private Token (String v) {
        value = v;
    }

    public String value( ) { return value; }
}

 

7) 어휘분석기 getToken 메소드

- getToken() 메소드 : 호출될 때마다 다음 토큰(token)을 인식하여 리턴
- 읽은 문자가 알파벳 문자 : 식별자 이나면 예약어

• 다음 문자가 알파벳 문자나 숫자인 한 계속해서 다음 문자를 읽는다.
• 읽은 문자열이 식별자인지 예약어인지 구별하여 해당 토큰을 리턴한다.

- 읽은 문자가 숫자 : 정수리터럴

• 다음 문자가 숫자인 한 계속해서 읽어 정수리터럴을 인식하고 이를 나타내는 NUMBER 토큰을 리턴

- 나머지는 읽은 문자에 따라 연산자, 구분자 등을 인식하여 리턴
 

8) 어휘 분석

- Lexer

• 입력을 읽어서 호출될 때마다 하나의 토큰을 변환
• 키워드, 수, 변수 이름, 기타 문자를 처리

 

3.4 파서 구현

1) 파서

- 입력 스트링을 명령어 단위로 파싱하면서 AST를 생성해 반환

• Commond command()
  • 명령어(변수 선언, 함수 정의, 문장)를 읽고 파싱하면서 해당 AST를 구성하여 반환한다.
  • <command> → <decl> | <stmt> | <function>
• Decl decl() : 변수 선언을 읽고 파싱하면서 해당 AST를 구성하여 반환
• Stmt stmt() : 각 문장을 읽고 파싱하면서 해당 AST를 구성하여 반환
• Expr expr() : 수식을 읽고 파싱하면서 해당 AST를 구성하여 반환

public class Parser {
    Token token;   
    Lexer lexer;
    
    public Parser(Lexer scan) { 
        lexer = l;		  
        token = lexer.getToken(); 
    }
    
    public static void main(String args[]) {
        parser  = new Parser(new Lexer());
        System.out.print(">> ");
        do {
            command = parser.command();
            System.out.print("\n>> ");
        } while (true);
    }
}

 

2) 파서 구현 : 명령어

public Command command() {
    // <command> ->  <decl> | <function> | <stmt>
    if (isType()) {
	    Decl d = decl();
	    return d;
    }
    if (token == Token.FUN) {
	    Function f = function();
	    return f;
    }

    if (token != Token.EOF) {
	    Stmt s = stmt();
        return s;
    }
    
    return null;
}

 

3) 파서 구현 : 변수 선언

private Decl decl() {
    // <decl>  -> <type> id [=<expr>]; | <type> id[n]
    Type t = type();
    String id = match(Token.ID);
    Decl d = null;

    if (token == Token.ASSIGN) {
        match(Token.ASSIGN);
        Expr e = expr();
        d = new Decl(id, t, e);
    } 
    else d = new Decl(id, t);

    match(Token.SEMICOLON);
    return d;
}

 

4) Statment 파싱

private Stmt stmt() {
    // <stmt> -> <block> | <assignment> | <ifStmt> | <whileStmt> | ...
    Stmt s = new Empty();
    switch (token) {
    case ID:    // assignment
        s = assignment(); return s;
    case LBRACE:          
        match(Token.LBRACE);      
        s = stmts();
        match(Token.RBRACE);    
        return s;
    case IF:    // if statement 
        s = ifStmt(); return s;   
    case WHILE:      // while statement 
        s = whileStmt(); return s;
    case LET:  // let statement 
        s = letStmt(); return s;
    ...
    default:  
        error("Illegal stmt"); return null; 
 }
}

 

5) 파서 구현 : Assignment 문

private Stmt assignment() { 
    // <assignment> -> id = <expr>;
    Identifier id = new Identifier(match(Token.ID));
    match(Token.ASSIGN);
    Expr e = expr();
    match(Token.SEMICOLON);
    if (ar == null) return new Assignment(id, e);
    return new Assignment(ar, e);
}

 

6) match 함수

- 현재 토큰을 매치하고 다음 토큰을 읽는다.

private String match(Token t) {
    String value = token.value();
    if (token == t)
        token = lexer.getToken();
    else
        error(t);
    return value;
}

 

7) 파서 구현 : 복합문

private Stmts stmts () { // <stmts> -> {<stmt>} 
    Stmts ss = new Stmts();
    while((token != Token.RBRACE) && (token != Token.END))
        ss.stmts.add(stmt());
    return ss;
}

 

8) 파서 구현 : If 문

private If ifStmt () { // <ifStmt> -> if (<expr>) then <stmt> [else <stmt>]
    match(Token.IF);
    match(Token.LPAREN);
    Expr e = expr();
    match(Token.RPAREN);
    match(Token.THEN);
    Stmt s1 = stmt();
    Stmt s2 = new Empty();
    if (token == Token.ELSE){
        match(Token.ELSE);
        s2 = stmt();
    }
    return new If(e, s1, s2);
}

 

9) 파서 구현 : While 문

private While whileStmt () {
    // <whileStmt> -> while (<expr>) <stmt>
    match(Token.WHILE);
    match(Token.LPAREN);
    Expr e = expr();
    match(Token.RPAREN);

    Stmt s1 = stmt();
    return new While(e, s1);
}

 

10) let-문 파싱

private Let letStmt () {
    // <letStmt> -> let <decls> in <block> end
    match(Token.LET);
    Decls ds = decls();
    match(Token.IN);
    Stmts ss = stmts();
    match(Token.END);
    match(Token.SEMICOLON);
    return new Let(ds, null, ss);
}

 

11) 파서 구현 : 수식

private Expr aexp () {
    // <aexp> -> <term> { + <term> | - <term> }
    Expr e = term();
    while (token == Token.PLUS || token == Token.MINUS) {
        Operator op = new Operator(match(token));
        Expr t = term();
        e = new Binary(op, e, t);
    }
    return e;
}

 

12) 파서 구현 : term 함수

private Expr term () { // <term> -> <factor> { * <factor> | / <factor>}
    Expr t = factor();
    while (token == Token.MULTIPLY || token == Token.DIVIDE) {
        Operator op = new Operator(match(token));
        Expr f = factor();
        t = new Binary(op, t, f);
    }
    return t;
}

 

13) 파서 구현 : factor 함수

private Expr factor() { 
    // <factor> -> [-](id | id'['<expr>']' | <call> | literal | '('<aexp> ')')
    Operator op = null;
    if (token == Token.MINUS)
        op = new Operator(match(Token.MINUS));

    Expr e = null;
    switch(token) {
        case ID:
            Identifier v = new Identifier(match(Token.ID));
            e = v;
            break;
        case LPAREN:
            match(Token.LPAREN);
            e = aexp();
            match(Token.RPAREN);
            break;
        default:
            error("Identifier | Literal");
    }

    if (op != null)
        return new Unary(op, e);
    else return e;
}