- 제출방법 : 작성한 프로젝트를 ‘{학번}’라는 이름으로 저장한 후 압축하여 Uclass 과제 게시판에 업로드해주세요. 채점은 스크립트로 자동으로 이루어지기에 폴더 이름이 잘못되어서 채점되지 못하면 0점을 받게 됩니다.
- 예시: 학번이 202448015인 학생은 다음과 같은 프로젝트를 202448015.zip으로 압축해서 제출해야 합니다.
202448015 ├── dune-project ├── src │ ├── ast.ml │ ├── dune │ ├── interpreter.ml │ ├── lexer.mll │ └── parser.mly └── test ├── dune └── main.ml - 제출기한 : 4월 28일 화요일 11:59pm
과제 진행 시 어려운 점이 있으면 Ed Discussion 게시판을 이용해 질문하세요. 게시판을 통해 하기 어려운 질문이라면 아래 TA 이메일을 통해 문의하시기 바랍니다.
- TA 이메일: seongminkim16@gmail.com
지난 과제에서는 여러분만의 렉서(lexer)와 파서(parser)를 직접 코딩해보는 경험을 했습니다. 사실 많은 프로그래밍 언어에서는 이런 렉서와 파서를 처음부터 다 만들지 않고, 언어의 문법 규칙만 알려주면 자동으로 렉서와 파서를 위한 코드를 생성해주는 편리한 도구들을 제공합니다.
이런 도구들의 원조 격으로는 1970년대 C언어를 위해 개발된 lex와 yacc가 있습니다. lex는 렉서를, yacc는 파서를 만들어주는 역할을 했습니다. 우리가 이번에 사용할 OCaml에도 비슷한 도구들이 있습니다. 바로 ocamllex와 menhir입니다.
K0를 위한 렉서와 파서를 라이브러리를 활용하여 만들기 (hw2_rebuild)
다시 한 번 K0에 대한 lexer와 parser를 만들어보겠습니다. K0의 문법은 다음과 같습니다.
<program> ::= <expression>
<expression> ::= <natural_number> <binary_operator> <natural_number>
<binary_operator> ::= + | - | * | /
<natural_number> ::= i, i ∈ ℕ₀ (0을 포함한 자연수)
Menhir 파서 생성기를 통한 파서 생성
이번 실습에서는 파싱(parsing) 과정을 먼저 다루겠습니다. 렉싱(lexing)에 대한 내용은 이후에 다시 살펴보겠습니다.
실습에서 사용할 Menhir 코드는 모두 parser.mly라는 단일 파일에 작성합니다. 파일 확장자 .mly는 해당 파일이 Menhir 도구의 입력 파일임을 나타냅니다. (여기서 ‘y’는 초기 파서 생성 도구 중 하나인 yacc에서 유래된 관례입니다.)
parser.mly 파일에는 우리가 파싱하고자 하는 언어의 문법(grammar definition)을 명세합니다. 즉, 해당 언어의 구조를 정의하는 규칙들의 집합입니다. 문법을 기술하는 구문(syntax)은 이어지는 예시를 통해 설명될 것입니다. 이 구문은 다소 생소하게 느껴질 수 있는데, 이는 Menhir가 yacc과 같은 오래된 도구들의 영향을 받았기 때문입니다.
Menhir는 parser.mly 파일을 입력받아 처리한 후, parser.ml 파일을 출력으로 생성합니다. 이 생성된 파일에는 해당 언어를 파싱하는 데 필요한 OCaml 코드가 구현되어 있습니다. 즉, Menhir는 문법 정의로부터 파서 코드를 자동으로 생성해주는 역할을 합니다.
parser.mly 파일 내의 문법 정의는 일반적으로 다음과 같은 네 가지 주요 부분으로 구성됩니다:
- 헤더 (Header): 파일 상단에 위치하며, 필요한 OCaml 코드나 설정을 포함합니다.
- 선언 (Declarations): 토큰(token), 타입(type), 우선순위(precedence) 등 문법 규칙에 필요한 요소들을 선언합니다.
- 규칙 (Rules): 언어의 구문 구조를 정의하는 핵심적인 생성 규칙(production rules)들을 명시합니다.
- 트레일러 (Trailer): 파일 하단에 위치하며, 추가적인 OCaml 코드를 포함할 수 있습니다.
각 부분의 구체적인 작성법과 역할에 대해서는 아래 코드와 주석을 통해 설명드리겠습니다.
헤더 (Header)
파일의 가장 앞부분에 위치하며, 여기에 작성된 OCaml 코드는 Menhir가 생성하는 parser.ml 파일의 시작 부분에 그대로 복사됩니다. 주로 필요한 모듈을 열거나(open), 파서 전반에서 사용될 유틸리티 함수 등을 정의할 때 사용합니다.
ast.ml에 정의된 Binary_Operation과 Add, Sub, Mult, Div를 사용하기 위해 Ast module을 open합니다.
%{
open Ast
%}
선언 (Declarations)
이 섹션에서는 파서가 인식해야 할 기본적인 요소들을 선언합니다.
- 토큰(Tokens): 렉서(lexer)로부터 전달받을 언어의 가장 작은 단위(어휘)들을
%token키워드로 선언합니다. 토큰이 특정 값(예: 정수 값, 문자열)을 가질 경우,<타입>과 함께 선언하여 관련 데이터를 파서 액션에서 사용할 수 있도록 합니다. - 시작 심볼(Start Symbol): 파싱을 시작할 최상위 규칙(non-terminal)을
%start키워드로 지정합니다. 이 규칙을 성공적으로 파싱했을 때 반환될 값의 타입도 함께 명시합니다. - (필요시) 연산자 우선순위 및 결합성 선언 (
%left,%right,%nonassoc등)
선언 섹션은 %% 기호로 마무리됩니다.
%token <int> INT
%token PLUS
%token MINUS
%token TIMES
%token DIVIDE
%token EOF
%start <Ast.expression> program
%%
규칙 (Rules)
이 섹션이 문법 정의의 핵심입니다. BNF(Backus-Naur Form)와 유사한 형태로, 언어의 구문 구조를 생성 규칙(production rules)들로 기술합니다.
- 규칙은
규칙이름 : 대체가능한 심볼들의 나열 { OCaml 액션 코드 }형태로 작성합니다. :기호는 BNF의::=와 같은 역할을 합니다.|기호는 여러 가능한 규칙 형태를 구분합니다.심볼은 선언된 토큰이거나 다른 규칙의 이름(non-terminal)이 될 수 있습니다.{ OCaml 액션 코드 }(Semantic Action) 부분에는 해당 규칙이 매칭되었을 때 수행할 OCaml 코드를 작성합니다. 이 코드는 주로 입력 심볼들의 값을 조합하여 결과값(예: AST 노드)을 생성하고 반환합니다.- 규칙 내에서
이름 = 심볼형태로 심볼이 매칭된 값(토큰 값 또는 하위 규칙의 결과)을 OCaml 변수(이름)에 바인딩하여 액션 코드에서 사용할 수 있습니다.
program:
| e = expression; EOF { e }
;
expression:
| i1 = INT; PLUS; i2 = INT { Binary_Operation (Add, i1, i2) }
| i1 = INT; MINUS; i2 = INT { Binary_Operation (Sub, i1, i2) }
| i1 = INT; TIMES; i2 = INT { Binary_Operation (Mult, i1, i2) }
| i1 = INT; DIVIDE; i2 = INT { Binary_Operation (Div, i1, i2) }
;
트레일러 (Trailer)
파일의 맨 마지막 부분에 위치하며, 헤더와 마찬가지로 여기에 작성된 OCaml 코드는 생성되는 parser.ml 파일의 끝 부분에 그대로 복사됩니다. 주로 규칙의 액션 코드 내부에서 사용될 헬퍼 함수 등을 정의하는 데 사용될 수 있습니다. 이 부분은 필수는 아닙니다.
Ocamllex 렉서 생성기를 통한 렉서 생성
이제 파서 생성기에 이어 렉서 생성기(lexer generator)인 ocamllex가 어떻게 사용되는지 알아보겠습니다. 파서 생성기를 다룰 때 설명했던 내용과 유사한 점이 많아 익숙하게 느껴지실 겁니다.
앞으로 작성할 모든 ocamllex 관련 코드는 lexer.mll이라는 파일에 저장할 것입니다. 파일 확장자 .mll은 이 파일이 ocamllex 도구의 입력으로 사용된다는 것을 나타냅니다. (여기서 ‘l’은 렉싱(lexing)을 의미합니다.)
이 lexer.mll 파일에는 우리가 렉싱(lexing)하고자 하는 언어의 렉서 정의(lexer definition)가 포함됩니다. 즉, 입력 문자열을 어떻게 의미 있는 토큰(token)들로 분해할지에 대한 규칙을 담고 있습니다.
ocamllex는 이 lexer.mll 파일을 입력으로 받아 처리한 후, lexer.ml이라는 OCaml 파일을 출력으로 생성합니다. 이 생성된 파일 안에는 해당 언어의 텍스트를 읽어 토큰 스트림으로 변환하는 OCaml 렉서 프로그램이 들어있습니다.
렉서 정의 파일(lexer.mll)은 일반적으로 다음과 같은 네 가지 주요 부분으로 구성됩니다:
- 헤더 (Header): 생성될
lexer.ml파일 상단에 포함될 OCaml 코드. - 식별자 (Identifiers) / 이름 정의 (Named Definitions): 규칙(rules) 섹션에서 재사용할 수 있는 정규 표현식(regular expressions)에 이름을 부여하는 부분.
- 규칙 (Rules): 입력 문자열에서 어떤 패턴(정규 표현식)이 어떤 토큰(token)에 해당하는지를 정의하는 핵심 부분.
- 트레일러 (Trailer): 생성될
lexer.ml파일 하단에 포함될 OCaml 코드.
이제 각 부분을 어떻게 구성하는지 더 자세히 살펴보겠습니다.
헤더 (Header)
파일의 가장 앞부분으로, 여기에 작성된 OCaml 코드는 ocamllex가 생성하는 lexer.ml 파일의 시작 부분에 그대로 복사됩니다. 주로 렉서의 액션 코드에서 필요한 모듈(특히, 파서에서 정의한 토큰 생성자들을 사용하기 위해 Parser 모듈)을 열거나(open), 렉싱 과정에 필요한 헬퍼 함수 등을 정의하는 데 사용됩니다.
parser.ml에서 정의한 토큰 타입들인 INT, PLUS, MINUS, TIMES, DIVIDE, EOF를 사용하기 위해 Parser 모듈을 open합니다.
{
open Parser
}
이름 정의 (Named Definitions / Identifiers)
이 섹션에서는 자주 사용될 정규 표현식에 let 이름 = 정규표현식 형태로 이름을 붙여 정의합니다. 이렇게 정의된 이름은 이후 ‘규칙(Rules)’ 섹션에서 해당 정규 표현식 대신 사용할 수 있어, 규칙의 가독성을 높이고 반복을 줄여줍니다.
let whitespace = [' ' '\t']+
let int = ['0'-'9']+
규칙 (Rules)
렉서 정의의 핵심 부분으로, 실제 입력 문자열을 어떤 패턴(정규 표현식)과 매칭시켜 어떤 토큰을 반환할지를 명시합니다.
rule 엔트리포인트_이름 = parse키워드로 규칙 정의를 시작합니다.엔트리포인트_이름은 생성될 렉서 함수의 이름이 됩니다 (여기서는read).| 정규표현식 { OCaml 액션 코드 }형태로 규칙들을 나열합니다.ocamllex는 입력 스트림을 읽어 현재 위치에서 나열된 순서대로 각 정규 표현식과 매칭을 시도합니다.- 가장 먼저 매칭되는 정규 표현식을 찾으면, 해당
{ OCaml 액션 코드 }를 실행합니다. 이 액션 코드는 보통 매칭된 문자열에 해당하는 토큰 생성자(예:PLUS,INT (값))를 반환합니다. - 액션 코드 내에서
Lexing.lexeme lexbuf함수를 사용하면 현재 매칭된 문자열(lexeme)을 얻을 수 있습니다. 이를 이용해 토큰에 값(예: 정수 값)을 실어 보낼 수 있습니다. eof는 입력 스트림의 끝(End Of File)과 매칭되는 특별한 정규 표현식입니다.
rule read =
parse
| whitespace { read lexbuf }
| "+" { PLUS }
| "-" { MINUS }
| "*" { TIMES }
| "/" { DIVIDE }
| int { INT (int_of_string (Lexing.lexeme lexbuf)) }
| eof { EOF }
트레일러 (Trailer)
파일의 맨 마지막 부분으로, 헤더와 마찬가지로 여기에 작성된 OCaml 코드는 생성되는 lexer.ml 파일의 끝 부분에 그대로 복사됩니다. 주로 규칙의 액션 코드 내에서 사용될 헬퍼 함수 등을 정의하는 데 사용될 수 있습니다. 이 부분은 필수는 아닙니다.
새로운 프로젝트 구성
.
├── dune-project
└── src
├── ast.ml
├── dune
├── interpreter.ml
├── lexer.mll
└── parser.mly
dune-project
(lang dune 2.9)
(using menhir 2.1)
src/dune
(library
(name K0))
(menhir
(modules parser))
(ocamllex lexer)
Interpreter
Lexing.from_string 함수는 문자열을 받아서 표준 라이브러리의 Lexing 모듈을 사용하여 렉서 버퍼(lexer buffer)를 생성합니다. 이 버퍼를 토큰 스트림(token stream)으로 생각할 수 있습니다. 그런 다음 이 함수는 Lexer.read와 Parser.program을 사용하여 문자열을 렉싱하고 파싱하여 AST로 만듭니다. Lexer.read 함수는 렉서 정의의 read 규칙에 해당하고, Parser.program 함수는 파서 정의의 program 규칙에 해당합니다.
Lexing.from_channel은 똑같은 기능을 문자열이 아닌 파일에서 수행합니다.
open Ast
let eval = function
| Binary_Operation (Add, left, right) -> left + right
| Binary_Operation (Sub, left, right) -> left - right
| Binary_Operation (Mult, left, right) -> left * right
| Binary_Operation (Div, left, right) -> if right <> 0 then left / right else failwith "Division by zero"
let execute (s : string) =
let lexbuf = Lexing.from_string s in
let ast = Parser.program Lexer.read lexbuf in
let program_result = eval ast in
Printf.printf "Result: %d\n" program_result
Debug / Test
dune utop src
utop ### K0.Interpreter.execute "3 + 2 + 3";;
Exception: K0.Parser.MenhirBasics.Error.
utop ### K0.Interpreter.execute "3 + 2";;
Result: 5
- : unit = ()
생성된 렉서와 파서가 궁금하다면?
_build/default/src에 있는 lexer.ml과 parser.ml을 확인해봅시다.
정규표현식 튜토리얼
이 장에서는 lexer를 위해 정규표현식을 작성할 때 필요한 간단한 문법들을 배우겠습니다.
캐릭터 클래스
캐릭터 클래스는 여러 문자들의 집합을 나타냅니다. 가령 [' ' '\t']는 공백 문자나 탭 문자의 집합을 의미합니다. 이런 캐릭터 클래스는 하이픈을 통해서 정의할 수도 있습니다. 가령 ['0'-'9'] 같은 경우는 0부터 9까지의 문자들을, ['a'-'z'] 는 알파벳 소문자들을, ['A'-'Z'] 를 의미합니다.
반복자
반복자는 반복자 앞에 있는 것이 반복되도록 합니다.
+반복자: 이는 반복자 앞에 있는 것이 최소 한 번은 반복되도록 합니다. 즉,['0'-'9']+는 최소 하나의 숫자가 있어야 합니다.?반복자: 이는 반복자 앞에 있는 것이 나올 수도 있고 안 나올수도 있음을 나타냅니다. 가령'-'?같은 경우는 음수 부호가 나올수도 안 나올수도 있음을 표시합니다.
캐릭터
캐릭터들도 그 자체로 정규표현식입니다. 자기 자신과 매칭됩니다.
Calculator 만들기 (calculator)
이번에는 K0 보다 많은 프로그램을 포함하는 계산기 언어를 구현해보겠습니다.
<program> ::= <expression>
<expression> ::= <integer>
| <expression> <binary_operator> <expression>
| (<expression>)
<binary_operator> ::= + | - | * | /
<integer> ::= i, i ∈ ℕ
이 언어로 표현 가능한 프로그램들은 다음이 있습니다.
2211 + 11(10 + 1) + (5 + 6)2 * 112 - 2 * 102 * 2 + 102 * 2 / 10
utop ### Calculator.Interpreter.interp "22";;
- : string = "22"
utop ### Calculator.Interpreter.interp "11 + 11";;
- : string = "22"
utop ### Calculator.Interpreter.interp "(10 + 1) + (5 + 6)";;
- : string = "22"
utop ### Calculator.Interpreter.interp "2 * 11";;
- : string = "22"
utop ### Calculator.Interpreter.interp "2 - 2 * 10";;
- : string = "-18"
utop ### Calculator.Interpreter.interp "2 * 2 + 10";;
- : string = "14"
utop ### Calculator.Interpreter.interp "2 * 2 / 10";;
- : string = "0"
이 언어로 표현 불가능한 프로그램들은 다음이 있습니다.
+ 2/ 2 3“University of Seoul”
utop ### Calculator.Interpreter.interp "+ 2";;
Exception: Calculator.Parser.MenhirBasics.Error.
utop ### Calculator.Interpreter.interp "/ 2 3";;
Exception: Calculator.Parser.MenhirBasics.Error.
utop ### Calculator.Interpreter.interp "University of Seoul";;
Exception: Failure "lexing: empty token".
ast.ml
type binary_operator =
| Add
| Sub
| Mult
| Div
type expression =
| Int of int
| BinaryOperation of binary_operator * expression * expression
parser.mly
%{
open Ast
%}
%token <int> INT
%token PLUS
%token MINUS
%token TIMES
%token DIVIDE
%token LEFT_PARENTHESIS
%token RIGHT_PARENTHESIS
%token EOF
(* lower precedence *)
%left PLUS
%left MINUS
%left TIMES
%left DIVIDE
(* higher precedence *)
%start <Ast.expression> program
%%
program:
| e = expression; EOF { e }
;
expression:
| i = INT { Int i }
| e1 = expression; PLUS; e2 = expression { BinaryOperation (Add, e1, e2) }
| e1 = expression; MINUS; e2 = expression { BinaryOperation (Sub, e1, e2) }
| e1 = expression; TIMES; e2 = expression { BinaryOperation (Mult, e1, e2) }
| e1 = expression; DIVIDE; e2 = expression { BinaryOperation (Div, e1, e2) }
| LEFT_PARENTHESIS; e = expression; RIGHT_PARENTHESIS { e }
;
lexer.mll
{
open Parser
}
let whitespace = [' ' '\t']+
let digit = ['0'-'9']
let int = '-'? digit+
rule read =
parse
| whitespace { read lexbuf }
| "+" { PLUS }
| "-" { MINUS }
| "*" { TIMES }
| "/" { DIVIDE }
| "(" { LEFT_PARENTHESIS }
| ")" { RIGHT_PARENTHESIS }
| int { INT (int_of_string (Lexing.lexeme lexbuf)) }
| eof { EOF }
interpreter.ml
아래 코드 구현은 동적 의미론 (dynamic semantics)을 구현합니다. 그 중에서 연산적 의미론 (operational semantics) 중 하나인 작은 단계 의미론(small-step semantics)로 구현되어있습니다. 이 내용은 다음 과제에서 배우게 됩니다. 일단은 제공된 코드를 사용하세요.
open Ast
let parse (s : string) : expression =
let lexbuf = Lexing.from_string s in
let ast = Parser.program Lexer.read lexbuf in ast
let string_of_value (e : expression) : string =
match e with
| Int i -> string_of_int i
| BinaryOperation _ -> failwith "precondition violated"
let is_value : expression -> bool = function
| Int _ -> true
| BinaryOperation _ -> false
let rec step : expression -> expression = function
| Int i -> failwith "Does not step"
| BinaryOperation (bop, e1, e2) when is_value e1 && is_value e2 -> step_binop bop e1 e2
| BinaryOperation (bop, e1, e2) when is_value e1 -> BinaryOperation(bop, e1, step e2)
| BinaryOperation (bop, e1, e2) -> BinaryOperation (bop, step e1, e2)
and step_bop bop v1 v2 = match bop, v1, v2 with
| Add, Int a, Int b -> Int (a + b)
| Sub, Int a, Int b -> Int (a - b)
| Mult, Int a, Int b -> Int (a * b)
| Div, Int a, Int b -> if b = 0 then failwith "Division by zero" else Int (a / b)
| Add, _, _ -> failwith "precondition violated"
| Sub, _, _ -> failwith "precondition violated"
| Mult, _, _ -> failwith "precondition violated"
| Div, _, _ -> failwith "precondition violated"
let rec eval (e : expression) : expression =
if is_value e then e else
e |> step |> eval
let interp (s : string) : string =
s |> parse |> eval |> string_of_val
우선순위(precedence)와 associativity(결합성)
parser.mly에서 토큰들을 선언한 후에 우선순위(precedence)와 결합성(associativity)에 대한 추가 정보를 제공할 수 있습니다. 다음 선언에서 사칙연산들이 왼쪽 결합성(left associative)을 가짐을 선언합니다.
(* lower precedence *)
%left PLUS
%left MINUS
%left TIMES
%left DIVIDE
(* higher precedence *)
PLUS가 왼쪽 결합성을 가지므로 1 + 2 + 3은 (1 + (2 + 3))이 아닌 ((1 + 2) + 3)으로 결합됩니다.
utop ### Calculator.Interpreter.parse "1 + 2 + 3";;
- : Calculator.Ast.expression =
Calculator.Ast.BinaryOperation (Calculator.Ast.Add,
Calculator.Ast.BinaryOperation (Calculator.Ast.Add, Calculator.Ast.Int 1,
Calculator.Ast.Int 2),
Calculator.Ast.Int 3)
반대로 %right PLUS라고 선언하면, 1 + 2 + 3은 (1 + (2 + 3))으로 결합됩니다.
위에 선언할 수록 낮은 우선순위를 가집니다. 즉, 2 + 10 * 2는 (2 + 10) * 2가 아닌 2 + (10 * 2)로 계산됩니다.
utop ### Calculator.Interpreter.parse "2 + 10 * 2";;
- : Calculator.Ast.expression =
Calculator.Ast.BinaryOperation (Calculator.Ast.Add, Calculator.Ast.Int 2,
Calculator.Ast.BinaryOperation (Calculator.Ast.Mult, Calculator.Ast.Int 10,
Calculator.Ast.Int 2))
추가적으로 %noassoc 키워드를 사용해서 해당 연산자가 연속해서 사용되는 것을 문법적으로 금지할 수 있습니다. 가령 %noassoc LESS를 정의하여 1 < 2 < 3 같은 표현을 하지 못 하게 할 수 있습니다.
프로젝트 구성
.
├── dune-project
├── src
│ ├── ast.ml
│ ├── dune
│ ├── interpreter.ml
│ ├── lexer.mll
│ └── parser.mly
└── test
├── dune
└── main.ml
dune-project
(lang dune 2.9)
(using menhir 2.1)
src/dune
(library (name Calculator))
(menhir (modules parser))
(ocamllex lexer)
OUnit2를 사용한 유닛 테스트
이번 과제부터는 테스트 케이스에 따라서 점수가 부여됩니다. 이를 위해 dune을 통한 유닛 테스트를 할 수 있도록 설정하겠습니다.
test/dune
(test
(name main)
(libraries Calculator ounit2)
)
main.ml
open OUnit2
open Calculator.Interpreter
let make_i n i s =
n >:: (fun _ -> assert_equal (string_of_int i) (interp s))
let tests = [
make_i "int" 22 "22";
make_i "add" 22 "11+11";
make_i "mult" 22 "2*11";
make_i "mult of mult" 40 "2*2*10";
make_i "mult on right of add" 22 "2+2*10";
make_i "mult on left of add" 14 "2*2+10";
make_i "nested add" 22 "(10 + 1) + (5 + 6)";
]
let _ = run_test_tt_main ("suite" >::: tests)
이제 dune test 명령어를 통해서 unit test를 실시할 수 있습니다.
seongminkim@DESKTOP-J8E2UER:~/ocaml/HW3/calculator$ dune test
.......
Ran: 7 tests in: 0.11 seconds.
OK
과제 (hw3)
다음의 CFG에 대한 tokenizer와 parser를 구현하세요. 이 CFG는 변수와 조건식을 다룰 수 있습니다. 제공된 hw3.zip에 코드를 추가하세요.
parser.mly와 lexer.mll을 제외한 파일은 수정할 수 없습니다.
prog ::= e
e ::= x
| i
| b
| e1 bop e2
| if e1 then e2 else e3
| let x = e1 in e2
bop ::= + | - | * | / | <=
x ::= <identifiers>
i ::= <integers>
b ::= true | false