View source for 파서 생성기 활용

'''이전 페이지''': [[Compiler|Compiler]]

지난 [[구문 분석|Lecture 3]]에서는 문맥 자유 문법(CFG)의 기초부터 시작하여 대표적인 파싱 전략인 하향식 파싱과 상향식 파싱(특히 LR 파싱의 기본 원리)까지 폭넓게 살펴보았습니다. LR 파서가 어떻게 파싱 테이블을 사용하여 입력을 처리하는지, 그리고 LR(0), SLR과 같은 파서들이 어떻게 아이템 집합으로부터 오토마톤과 테이블을 구축하는지에 대해 배웠습니다.

이번 '''Lecture 4'''에서는 먼저 LR 파싱 과정에서 실제로 마주칠 수 있는 문제점, 즉 '''파싱 테이블 충돌(conflict)'''에 대해 더 깊이 알아보고, 연산자 우선순위(precedence)와 결합성(associativity) 같은 추가 정보를 활용하여 이러한 충돌을 효과적으로 해결하는 전략을 배울 것입니다. 또한, 프로그래밍 언어에서 자주 등장하는 고질적인 모호성 문제인 '''"Dangling-Else"''' 문제를 LR 파싱 관점에서 어떻게 다루는지 살펴볼 것입니다.

강의의 다음 부분에서는 이론적인 파서 구축의 복잡함을 덜어주는 강력한 도구인 '''파서 생성기(Parser Generator)'''를 소개합니다. 대표적인 파서 생성기인 '''Yacc'''(그리고 OCaml 환경에서의 '''ocamlyacc''')의 기본 작동 원리와 개발 흐름을 이해하고, 간단한 "계산기(Calculator)" 예제를 통해 실제 Yacc 명세 파일(<code>.mly</code>) 작성법, 어휘 분석기(Lexer)와의 연동, 그리고 파서 생성기가 보고하는 충돌 메시지를 해석하고 해결하는 방법까지 알아볼 것입니다.

마지막으로, 이러한 파서 생성기 활용법을 좀 더 복잡한 구조를 가진 '''"While 언어"'''라는 예제 언어에 적용해봄으로써, 변수, 다양한 종류의 표현식 및 제어 구조를 포함하는 언어에 대한 파서 명세 작성 전반을 경험하게 될 것입니다. 이를 통해 구문 분석 이론이 실제 컴파일러 개발 도구에서 어떻게 구현되고 활용되는지 구체적으로 이해하는 것을 목표로 합니다.

== LR 파싱 심화: 충돌 해결 및 주요 구문 문제 ==

LR 파싱은 매우 강력하지만, 실제 파싱 테이블을 생성하다 보면 모호하지 않은(unambiguous) 문법에 대해서도 충돌이 발생할 수 있습니다. 이는 SLR과 같은 일부 LR 파서 생성 방식이 문맥을 충분히 고려하지 못해 발생하는 한계 때문입니다.

다음과 같은 수식 문법을 다시 살펴봅시다 (이 문법 자체는 모호하지 않지만, SLR 테이블에서는 충돌을 일으킬 수 있습니다):
# <math>E' \rightarrow E</math>
# <math>E \rightarrow E+E</math>
# <math>E \rightarrow E*E</math>
# <math>E \rightarrow (E)</math>
# <math>E \rightarrow \text{id}</math>

이 문법은 <code>if E1 then if E2 then S1 else S2</code> 와 같은 입력에 대해, <code>else S2</code>가 안쪽의 <code>if E2</code>에 속하는지 (즉, <code>if E1 then (if E2 then S1 else S2)</code>) 아니면 바깥쪽의 <code>if E1</code>에 속하는지 (즉, <code>if E1 then (if E2 then S1) else S2</code>) 두 가지 다른 파스 트리를 생성할 수 있어 모호합니다.

다음은 이 문제를 간략화하고 확장한 문법 예시입니다 (<math>S' \rightarrow S</math>는 확장된 시작 규칙, <code>i</code>는 <code>if expr then</code>, <code>e</code>는 <code>else</code>, <code>a</code>는 <code>other</code>를 의미):
<math>S' \rightarrow S</math>
<math>S \rightarrow i S e S \mid i S \mid a</math>

이 문법에 대한 LR(0) 상태들을 구성해보면, 특정 상태(예: <math>I_4 = [S \rightarrow iS \cdot eS, S \rightarrow iS \cdot ]</math>)에서 다음 입력이 <code>e</code>일 때 Shift/Reduce 충돌이 발생합니다. 이 충돌은 <math>\text{FOLLOW}(S)</math>가 <code>e</code>를 포함하기 때문에 SLR 파싱 테이블에서도 해결되지 않습니다.

일반적인 프로그래밍 언어에서는 "'''else는 가장 가까운 매칭되지 않은 if에 연결된다'''"는 규칙을 따릅니다. LR 파서에서는 이러한 충돌이 발생했을 때, 관례적으로 '''Shift''' 행동을 우선시하여 이 규칙을 구현합니다. 즉, <code>else</code>를 현재의 <code>if S</code> 구문에 귀속시키는 Reduce 대신, 더 안쪽(나중)의 <code>if</code>에 귀속될 가능성을 열어두기 위해 <code>else</code>를 스택으로 Shift합니다.

이러한 모호성은 문법 자체를 수정하여 명시적으로 해결할 수도 있습니다. 예를 들어, "else를 반드시 가지는 if문 (Matched statement, M)"과 "else가 없는 if문 (Unmatched statement, U)"을 구분하는 논터미널을 도입하여 문법을 다음과 같이 명확하게 만들 수 있습니다:

<math>S \rightarrow M \mid U</math>
<math>M \rightarrow \text{if expr then M else M} \mid \text{other}</math>
<math>U \rightarrow \text{if expr then S} \mid \text{if expr then M else U}</math>

== 파서 생성기 소개 및 활용 (Introduction to Parser Generators & Example) ==

지금까지 살펴본 것처럼, LR 파싱 테이블을 직접 손으로 구축하고 충돌을 해결하는 것은 매우 복잡하고 오류가 발생하기 쉬운 작업입니다. 다행히 이러한 과정을 자동화해주는 도구들이 있으며, 이를 '''파서 생성기(Parser Generator)'''라고 부릅니다. 파서 생성기는 사용자가 문법 명세를 제공하면, 그에 해당하는 파서 프로그램(파싱 테이블 포함)을 자동으로 생성해줍니다. 대표적인 파서 생성기로는 Yacc(Yet Another Compiler-Compiler)와 그 변형인 Bison, 그리고 OCaml 환경에서 사용되는 ocamlyacc 등이 있습니다.

일반적으로 파서 생성기는 다음과 같은 작업 흐름을 가집니다:
#  사용자는 문법 규칙과 관련 동작(의미론적 액션)을 기술한 명세 파일(예: Yacc에서는 <code>parser.mly</code>)을 작성합니다.
#  파서 생성기(예: ocamlyacc)는 이 명세 파일을 입력으로 받아 파싱 로직이 담긴 프로그래밍 언어 코드(예: OCaml의 경우 <code>parser.ml</code>, <code>parser.mli</code>)를 출력합니다.
#  생성된 파서 코드는 어휘 분석기(Lexer, 예: ocamllex로 생성된 <code>lexer.ml</code>) 및 다른 프로그램 모듈과 함께 컴파일되어 실행 가능한 파서(또는 컴파일러의 일부)가 됩니다 (예: <code>a.out</code>).
#  실행 시, 이 파서는 어휘 분석기로부터 토큰 스트림을 받아 구문 분석을 수행하고, 명세된 동작에 따라 AST를 구축하거나 다른 작업을 수행합니다.

=== 예제: 계산기 ===
간단한 계산기 예제를 통해 파서 생성기(ocamlyacc 기준)의 사용법을 살펴보겠습니다. 이 계산기는 사칙연산 및 거듭제곱 연산을 수행합니다. 완전한 프로젝트는 보통 다음과 같은 파일들로 구성되지만, 본 강의에서는 파서 및 렉서 명세의 핵심에 집중하기 위해 일부 파일은 역할만 언급하고 상세 코드는 생략합니다:
* <code>ast.ml</code>: 표현식의 추상 구문 트리(AST) 데이터 타입을 정의합니다.
* <code>parser.mly</code>: ocamlyacc를 위한 문법 명세 파일입니다.
* <code>lexer.mll</code>: ocamllex를 위한 어휘 분석기 명세 파일입니다.
* <code>eval.ml</code>: 생성된 AST를 평가하는 로직을 구현합니다. 이 파일은 AST를 받아 실제 계산을 수행하는 중요한 부분이지만, 전체 코드는 생략하고 역할만 이해합니다.
* <code>main.ml</code>: 전체 프로그램을 구동하고, 입력을 받아 렉서와 파서를 호출한 뒤, <code>eval.ml</code>의 평가 함수를 통해 최종 결과를 출력하는 메인 루틴입니다. 흐름상 전체 코드는 생략합니다.
* <code>Makefile</code>: 프로젝트의 각 OCaml 모듈들을 올바른 순서로 컴파일하고 연결하여 최종 실행 파일을 만드는 과정을 자동화하는 스크립트입니다. 여기서는 생략합니다.

==== AST 정의 (ast.ml) ====
계산기 표현식의 AST는 OCaml에서 다음과 같이 정의될 수 있습니다:
<syntaxhighlight lang="ocaml">
type expr =
  | Num of int
  | Add of expr * expr
  | Sub of expr * expr
  | Mul of expr * expr
  | Div of expr * expr
  | Pow of expr * expr
</syntaxhighlight>
이는 문법 <math>E \rightarrow n | E+E | E-E | E*E | E/E | E^E</math> 에 해당합니다.

==== Yacc 문법 명세 (parser.mly) ====
<code>parser.mly</code> 파일은 크게 세 부분으로 나뉩니다: 사용자 선언부(<code>%{ ... %}</code>), 파서 선언부, 그리고 문법 규칙부(<code>%%</code> 이후).
* '''사용자 선언부:''' 파서의 의미론적 액션에서 사용될 OCaml 코드를 정의합니다 (예: <code>open Ast</code>).
* '''파서 선언부:''' 토큰 심볼, 각 토큰의 타입(값이 있는 경우), 연산자 우선순위 및 결합성, 시작 심볼, 각 논터미널이 반환할 값의 타입 등을 선언합니다.
* '''문법 규칙부:''' <code>논터미널 : 우변 { 의미론적 액션 }</code> 형태로 생성 규칙과 각 규칙이 성공적으로 인식되었을 때 수행할 OCaml 코드를 기술합니다.

다음은 계산기 예제의 <code>parser.mly</code> 일부입니다:
<syntaxhighlight lang="ocaml">
%{
  open Ast (* ast.ml에 정의된 타입을 사용하기 위해 *)
%}

/* 토큰 선언 */
%token NEWLINE LPAREN RPAREN PLUS MINUS MULTIPLY DIV POW
%token <int> NUM /* NUM 토큰은 정수 값을 가짐 */

/* 연산자 우선순위 및 결합성 선언 (충돌 해결용) */
%left PLUS MINUS       /* 낮은 우선순위, 왼쪽 결합성 */
%left MULTIPLY DIV   /* 중간 우선순위, 왼쪽 결합성 */
%right POW           /* 높은 우선순위, 오른쪽 결합성 (보통 거듭제곱은 오른쪽 결합) */

%start program       /* 시작 심볼 지정 */
%type <Ast.expr> program /* program 논터미널이 반환하는 값의 타입 */
%type <Ast.expr> exp    /* exp 논터미널이 반환하는 값의 타입 */

%%

/* 문법 규칙 및 의미론적 액션 */
program:
  | exp NEWLINE  { $1 } /* $1은 첫 번째 심볼(exp)의 값을 의미 */
;

exp:
  | NUM                { Num($1) } /* $1은 NUM 토큰의 정수 값 */
  | exp PLUS exp       { Add($1, $3) } /* $1은 첫 exp, $3은 두 번째 exp의 값 */
  | exp MINUS exp      { Sub($1, $3) }
  | exp MULTIPLY exp   { Mul($1, $3) }
  | exp DIV exp        { Div($1, $3) }
  | exp POW exp        { Pow($1, $3) }
  | LPAREN exp RPAREN  { $2 } /* $2는 괄호 안의 exp 값 */
;
</syntaxhighlight>
의미론적 액션에서 <code>$1</code>, <code>$2</code>, <code>$3</code> 등은 규칙 우변의 각 심볼에 해당하는 값(토큰의 값 또는 하위 논터미널이 반환한 AST 노드)을 참조합니다.

==== 어휘 분석기 명세 (lexer.mll) ====
<code>lexer.mll</code> 파일은 ocamllex를 사용하여 어휘 분석기를 생성하기 위한 명세입니다. 정규 표현식을 사용하여 토큰의 패턴을 정의하고, 각 패턴이 일치할 때 어떤 토큰을 파서에게 반환할지 지정합니다. <code>open Parser</code>는 <code>parser.mly</code>에서 정의된 토큰 심볼들을 사용하기 위함입니다.
<syntaxhighlight lang="ocaml">
{
  open Parser (* parser.mly에서 정의한 토큰 심볼들을 사용하기 위해 *)
  exception LexicalError of string
}

let number  = ['0'-'9']+
let blank = [' ' '\t']

rule token = parse
  | blank      { token lexbuf } (* 공백 무시 *)
  | '\n'       { NEWLINE }
  | number as n { NUM (int_of_string (Lexing.lexeme lexbuf)) } (* Lexing.lexeme lexbuf 로 일치된 문자열 가져옴 *)
  | '+'        { PLUS }
  | '-'        { MINUS }
  | '*'        { MULTIPLY }
  | '/'        { DIV }
  | '^'        { POW }    (* 거듭제곱 연산자 *)
  | '('        { LPAREN }
  | ')'        { RPAREN }
  | eof        { EOF } (* Yacc/ocamlyacc은 $end를 사용, 명시적 EOF 처리 필요할 수 있음 *)
  | _ as c     { raise (LexicalError ("Illegal character: " ^ Char.escaped c)) }
</syntaxhighlight>

==== Yacc에서의 충돌과 해결 ====
위 계산기 문법처럼 연산자 우선순위와 결합성이 초기에 명세되지 않으면, ocamlyacc로 컴파일 시 충돌 메시지가 나타날 수 있습니다. 이는 파서가 특정 상태에서 다음 행동을 유일하게 결정할 수 없기 때문입니다. <code>parser.mly</code> 파일 내의 파서 선언부에 <code>%left</code>, <code>%right</code>, <code>%nonassoc</code>과 같은 지시자를 사용하여 토큰들의 우선순위와 결합성을 명시해주면 이러한 충돌의 대부분을 해결할 수 있습니다. 예를 들어, <code>%left PLUS MINUS</code>는 <code>PLUS</code>와 <code>MINUS</code>가 왼쪽 결합성이며 동일한 우선순위를 가짐을 나타냅니다. 선언 순서상 나중에 선언된 토큰들이 더 높은 우선순위를 가집니다 (예: <code>%left MULTIPLY DIV</code>가 <code>%left PLUS MINUS</code>보다 높은 우선순위).

=== 파서 생성기 응용 - While 언어 ===

지금까지 비교적 간단한 계산기 예제를 통해 파서 생성기의 기본적인 사용법과 Yacc 명세 파일에서 우선순위/결합성 선언을 통해 충돌을 해결하는 방법을 익혔습니다. 이제 이러한 경험을 바탕으로, 변수 할당, 조건문, 반복문 등 좀 더 실제 프로그래밍 언어와 유사한 구조를 가진 가상의 예제 언어, 'While 언어'에 대한 파서를 구축하는 과정을 자세히 살펴보겠습니다.

==== While 언어 예제 코드 ====
다음은 While 언어로 작성된 간단한 프로그램들의 예입니다.
* 팩토리얼 계산:
<syntaxhighlight lang="c">
// n의 팩토리얼을 계산
n := 10;
i := 1;
fact := 1;
while (i <= n) {
  fact := fact * i;
  i := i + 1;
}
print (fact);
</syntaxhighlight>

* 짝수/홀수 합 계산:
<syntaxhighlight lang="c">
// 1부터 n까지 짝수의 합과 홀수의 합을 각각 계산
n := 10;
i := 1;
evens := 0; 
odds := 0; 
while (i <= n) {
  if (! (i % 2 == 1) && i % 2 == 0) { // 짝수 조건
    evens := evens + i;
  } else {
    odds := odds + i;
  }
  i := i + 1;
}
print (evens);
print (odds);
</syntaxhighlight>

==== While 언어 AST 정의 ====
While 언어의 추상 구문 트리(AST)는 산술 표현식(aexp), 불리언 표현식(bexp), 그리고 명령어(cmd)로 구성됩니다.
* '''산술 표현식 (aexp)''': <math>a \rightarrow n \mid x \mid a_1+a_2 \mid a_1*a_2 \mid a_1-a_2 \mid a_1/a_2 \mid a_1\%a_2</math>
* '''불리언 표현식 (bexp)''': <math>b \rightarrow \text{true} \mid \text{false} \mid a_1=a_2 \mid a_1 \le a_2 \mid \neg b \mid b_1 \land b_2</math>
* '''명령어 (cmd)''': <math>C \rightarrow x := a \mid \text{skip} \mid C_1; C_2 \mid \text{if } b \text{ then } C_1 \text{ else } C_2 \mid \text{while } b \text{ do } C \mid \text{print } a</math>

OCaml에서의 타입 정의 예시:
<syntaxhighlight lang="ocaml">
type var = string

type aexp =
  | Int of int | Var of var
  | Add of aexp * aexp | Sub of aexp * aexp
  | Mul of aexp * aexp | Div of aexp * aexp | Mod of aexp * aexp

type bexp =
  | Bool of bool
  | Eq of aexp * aexp | Le of aexp * aexp
  | Neg of bexp | Conj of bexp * bexp (* AND 연산 *)

type cmd =
  | Assign of var * aexp
  | Skip
  | Seq of cmd * cmd (* 순차 실행 *)
  | If of bexp * cmd * cmd (* if-then-else *)
  | While of bexp * cmd (* while 루프 *)
  | Print of aexp

type program = cmd
</syntaxhighlight>

==== While 언어 문법 명세 (parser.mly 일부) ====
While 언어에 대한 <code>parser.mly</code> 파일은 토큰, 우선순위, 타입, 시작 심볼 및 문법 규칙들을 포함합니다. 여기서 명령어들의 순차적 실행을 위한 <code>cmd : cmd cmd</code> 규칙은 두 명령어가 연달아 나타날 경우 <code>Ast.Seq</code> 노드로 묶어 순차 실행을 표현합니다. 많은 C-계열 언어에서는 <code>cmd SEMICOLON cmd</code>와 같이 각 명령어 사이에 명시적인 세미콜론을 두어 구문론적으로 순서를 구분하지만, 여기서 제시된 문법은 각 개별 명령어가 자체적으로 세미콜론으로 끝나는 것을 가정하고, 이러한 '완결된' 명령어들의 연속을 통해 프로그램의 흐름을 구성하는 방식을 보여줍니다.

<syntaxhighlight lang="ocaml">
%{
  open Ast (* Ast 모듈에 정의된 타입들을 사용 *)
%}

%token <string> IDENT
%token <int> NUMBER
%token <bool> BOOLEAN
%token LPAREN RPAREN LBRACE RBRACE SEMICOLON EOF
%token BAND NOT LE EQ PLUS MINUS STAR SLASH MOD ASSIGN SKIP PRINT IF ELSE WHILE

/* 연산자 우선순위 및 결합성 선언 */
%left BAND
%left EQ LE 
%left PLUS MINUS
%left STAR SLASH MOD
%right NOT 

%type <Ast.cmd> cmd
%type <Ast.aexp> aexp
%type <Ast.bexp> bexp
%type <Ast.program> program

%start program

%%

program:
  | cmd EOF { $1 }
;

cmd:
  | IDENT ASSIGN aexp SEMICOLON                { Ast.Assign ($1, $3) }
  | SKIP SEMICOLON                           { Ast.Skip }
  | cmd cmd                                  { Ast.Seq ($1, $2) } (* 보통은 cmd SEMICOLON cmd 형태이나, 명세에 따라 달라질 수 있음 *)
  | IF LPAREN bexp RPAREN LBRACE cmd RBRACE ELSE LBRACE cmd RBRACE { Ast.If ($3, $6, $10) }
  | WHILE LPAREN bexp RPAREN LBRACE cmd RBRACE { Ast.While ($3, $6) }
  | PRINT LPAREN aexp RPAREN SEMICOLON       { Ast.Print ($3) } (* aexp가 세 번째 심볼이므로 $3 사용 *)
;

aexp:
  | NUMBER             { Ast.Int $1 }
  | IDENT              { Ast.Var $1 }
  | aexp PLUS aexp     { Ast.Add ($1, $3) }
  | aexp MINUS aexp    { Ast.Sub ($1, $3) }
  | aexp STAR aexp     { Ast.Mul ($1, $3) }
  | aexp SLASH aexp    { Ast.Div ($1, $3) }
  | aexp MOD aexp      { Ast.Mod ($1, $3) }
  | LPAREN aexp RPAREN { $2 }
;

bexp:
  | BOOLEAN            { Ast.Bool $1 }
  | aexp EQ aexp       { Ast.Eq ($1, $3) }
  | aexp LE aexp       { Ast.Le ($1, $3) }
  | NOT bexp           { Ast.Neg $2 }
  | bexp BAND bexp     { Ast.Conj ($1, $3) }
  | LPAREN bexp RPAREN { $2 }
;
</syntaxhighlight>

==== While 언어 어휘 분석기 명세 (lexer.mll 일부) ====
While 언어를 위한 <code>lexer.mll</code> 파일은 키워드(<code>if</code>, <code>while</code>, <code>true</code>, <code>false</code> 등), 식별자, 숫자, 연산자, 공백/줄바꿈, 주석 등을 정의합니다.
<syntaxhighlight lang="ocaml">
{
open Parser
exception LexingError of string

let kwd_list = [
  ("true",  BOOLEAN true); ("false", BOOLEAN false);
  ("if",    IF);         ("else",  ELSE);
  ("while", WHILE);      ("skip",  SKIP);
  ("print", PRINT)
]

let id_or_kwd (s: string): Parser.token =
  match List.assoc_opt s kwd_list with
  | Some t -> t
  | None   -> IDENT s
}

let letter = ['a'-'z' 'A'-'Z']
let digit = ['0'-'9']
let ident = letter (letter | digit | '_')*
let number = digit+
let blank = [' ' '\t' '\r']+
let newline = '\n'
let comment_line_header = "//"

rule next_token = parse
  | blank                  { next_token lexbuf }
  | newline                { Lexing.new_line lexbuf; next_token lexbuf }
  | comment_line_header    { comment_line lexbuf } (* 주석 처리 *)
  | ident as s             { id_or_kwd s }
  | number as n            { NUMBER (int_of_string n) }
  | "("                    { LPAREN }
  | ")"                    { RPAREN }
  | "{"                    { LBRACE }
  | "}"                    { RBRACE }
  | ";"                    { SEMICOLON }
  | "=="                   { EQ }
  | "<="                   { LE }
  | "!"                    { NOT }
  | "&&"                   { BAND }
  | "+"                    { PLUS }
  | "-"                    { MINUS }
  | "*"                    { STAR }
  | "/"                    { SLASH }
  | "%"                    { MOD }
  | ":="                   { ASSIGN }
  | eof                    { EOF }
  | _ as c                 { Stdlib.raise (LexingError (Printf.sprintf "Illegal character: '%c'" c)) }

and comment_line = parse (* 주석 라인 끝까지 읽어 무시 *)
  | newline                { Lexing.new_line lexbuf; next_token lexbuf }
  | eof                    { EOF }
  | _                      { comment_line lexbuf }
</syntaxhighlight>

==== While 언어 평가기 (eval.ml 일부) ====
<code>eval.ml</code>은 While 언어의 AST를 입력 받아 그 의미에 따라 프로그램을 실행(평가)하는 함수들을 정의합니다. 핵심은 변수의 현재 값을 저장하고 조회/업데이트하는 '''상태(State)'''를 관리하는 부분과, 각 표현식 및 명령어 종류에 따른 평가 함수(<code>eval_a</code>, <code>eval_b</code>, <code>eval_c</code>)입니다.

상태는 변수 이름(<code>Ast.var</code>)에서 정수 값(<code>int</code>)으로의 매핑 리스트로 간단히 표현될 수 있습니다.
<syntaxhighlight lang="ocaml">
(* 상태 관리를 위한 모듈 *)
module State = struct
  type t = (Ast.var * int) list (* Ast.var 사용 *)
  let empty : t = [] (* 초기 상태는 비어있는 리스트 *)

  (* 상태에서 변수 값을 찾는 함수 *)
  let rec lookup (s: t) (x: Ast.var) : int =
    match s with
    | [] -> raise (Failure (x ^ " is not bound in state"))
    | (y,v)::s' -> if x = y then v else lookup s' x

  (* 상태에 변수 값을 업데이트(또는 추가)하는 함수 *)
  let update (s: t) (x: Ast.var) (v: int) : t = (x, v) :: s (* 기존 바인딩을 가리는 방식 *)
end

(* 산술 표현식 평가 *)
let rec eval_a (aexp: Ast.aexp) (s: State.t) : int =
  match aexp with
  | Ast.Int n -> n
  | Ast.Var x -> State.lookup s x
  | Ast.Add (a1, a2) -> (eval_a a1 s) + (eval_a a2 s)
  | Ast.Sub (a1, a2) -> (eval_a a1 s) - (eval_a a2 s)
  | Ast.Mul (a1, a2) -> (eval_a a1 s) * (eval_a a2 s)
  | Ast.Div (a1, a2) -> 
      let v2 = eval_a a2 s in
      if v2 = 0 then raise (Failure "Division by zero") else (eval_a a1 s) / v2
  | Ast.Mod (a1, a2) -> 
      let v2 = eval_a a2 s in
      if v2 = 0 then raise (Failure "Modulo by zero") else (eval_a a1 s) mod v2

(* 불리언 표현식 평가 *)
let rec eval_b (bexp: Ast.bexp) (s: State.t) : bool =
  match bexp with
  | Ast.Bool b_val -> b_val
  | Ast.Eq (a1, a2) -> (eval_a a1 s) = (eval_a a2 s)
  | Ast.Le (a1, a2) -> (eval_a a1 s) <= (eval_a a2 s)
  | Ast.Neg b_exp -> not (eval_b b_exp s)
  | Ast.Conj (b1, b2) -> (eval_b b1 s) && (eval_b b2 s)

(* 명령어 평가 *)
let rec eval_c (cmd: Ast.cmd) (s: State.t) : State.t =
  match cmd with
  | Ast.Assign (x, a) -> State.update s x (eval_a a s)
  | Ast.Skip -> s
  | Ast.Seq (c1, c2) -> let s' = eval_c c1 s in eval_c c2 s'
  | Ast.If (b, c1, c2) -> if eval_b b s then eval_c c1 s else eval_c c2 s
  | Ast.While (b, c_body) as while_cmd -> (* while_cmd로 전체 루프를 참조하여 재귀 호출 *)
      if eval_b b s then
        let s' = eval_c c_body s in
        eval_c while_cmd s' (* 루프 몸체 실행 후 다시 while 평가 *)
      else
        s (* 조건이 거짓이면 현재 상태 반환 *)
  | Ast.Print a -> 
      print_endline (string_of_int (eval_a a s)); 
      s (* print 후 상태는 변하지 않음 *)

(* 프로그램 전체 평가 *)
let eval_program (program: Ast.program) : State.t =
  eval_c program State.empty
</syntaxhighlight>

이처럼 파서 생성기를 사용하면 복잡한 문법을 가진 언어에 대해서도 비교적 쉽게 파서를 개발하고, AST를 구축하여 다양한 후속 작업(의미 분석, 코드 생성, 인터프리터 구현 등)을 진행할 수 있습니다.

다음에는 이렇게 정의된 While 언어의 형식적인 의미론(Semantics)에 대해 더 자세히 알아보겠습니다.