밑바닥부터 만드는 컴퓨팅 시스템 컴파일러

10장 컴파일러 1: 구문분석

컴파일러는 원본 언어에서 대상 언어로 프로그램을 번역하는 프로그램이다.
컴파일 (compilation)로 알려진 이 번역 과정을 개념적으로 두 개로 나뉜다.
1. 원본 프로그램의 구문(syntax)을 이해 => 구문 분석(syntax analysis)
2. 그 구문을 통해 프로그램의 의미(semantics)를 찾음 => 코드 생성(code generation)

구문 분석기(syntax analyzer)가 소스 프로그램을 '이해'한다는 사실을 보여줄 방법을 고안해야 한다. 이 도서에서는 구문 분석기가 XML 파일을 출력하도록 했다.

왜 이렇게 힘들게 컴파일러를 만들어 봐야 할까?

컴파일러를 직접 만들며 내부 처리 방식을 이해하면 훨씬 더 수준 높은 프로그래머가 된다.
프로그래밍 언어를 기술하는 데 사용하는 규칙이나 문법이, 컴퓨터 그래픽이나 데이터 베이스 관리, 생물 정보학의 통신 규칙에 이르기 까지 다양한 분야의 데이터 문법을 정의할 때도 동일하게 활용된다.

10.1 배경

일반적인 컴파일러는 구문 분석(syntax analysis)과 코드 생성(code generation)의 두 모듈로 구성된다.
구문 분석 작업은 대게 두 모듈로 더 나뉘어 진다.
- 토큰화(tokenizing) 모듈: 입력 문자들을 언어 기본 요소들로 분류하는 모듈
- 파싱(parsing) 모듈: 토큰화 결과로 나온 언어 기본 요소 스트림을 언어의 구문 규칙에 맞추는 모듈

이 모듈들이 하는 작업은 소스 프로그램을 번역할 대상언어와 완전히 독립적임을 유의하라.

형식언어(formal language)('언어'라고 하기 어려울 정도로 단순한 인공 언어)에 한정하면, 그 구문 구조를 정확하게 정의할 수 있다. 프로그래밍 언어는 보통 문맥 자유 문법(context-free grammar)이라는 규칙들로 기술된다. 따라서 주어진 프로그램을 이해(또는 분석) 한다는 것은 프로그램의 텍스트와 문법 규칙 사이에 정확한 대응 관계를 결정한다는 뜻이 된다. 그러려면 먼저 프로그램의 텍스트를 토큰들로 구성된 리스트로 재구성 해야 한다.

10.1.1 어휘 분석

프로그램이 구문 분석의 첫 단계는 공백이나 주석은 무시하고, 문자들을(언어 문법에 정의된) 토큰들로 분류하는 것이다.
- 이 단계는 보통 어휘 분석(lexical analysis), 스캐닝(scanning), 또는 토큰화(tokenizing)로 불린다.
프로그램이 토큰화 되면, 토큰들은 프로그램의 기본 원소가 되며, 컴파일러의 입력도 토큰 스트림이 된다.
토큰들은 각각 특정 분류 또는 유형으로 나뉜다.
- while은 키워드, count는 식별자, <=는 연산자라는 식이다.

예제

while (count <= 100) {
  count++;
}

토큰화 결과

while
(
count
<=
100
)
{
count
++
;
}

10.1.2 문법

프로그램을 어휘 분석해서 토큰 스트림으로 만들고 나면, 토큰 스트림을 분석(parse)해서 형식 구조로 만든다.
- 토큰들이 변수 선언, 명령문, 표현식 등과 같은 언어 구조 중에 어디에 해당 하는 지 알아내야 한다.
- 이 분류 작업은 토큰 스트림을 문법이라는 미리 정의된 규칙들을 맞춰보는 작업이다.

거의 대부분 프로그래밍 언어들이나, 복잡한 파일 포맷 문법을 정의하는 여타 형식 언어들은 문맥 자유 문법이라는 형식주의(formalism)를 사용한다. 문맥 자유 문법이란 어떤 언어의 구문 요소들을 더 단순한 요소들을 이용해 구성하는 규칙들을 뜻한다.

문법들은 두 가지 관점으로 볼 수 있다.

선언적 관점에서 문법, 토큰(단말이라고도 함)들을 더 높은 수준의 문법 요소들(비단말이라고도 함)로 결합하는 방법들을 정의한 것이다.
분석적 관점에서 문법, 주어진 입력(토큰들)을 받아 비단말, 더 낮은 수준의 비단말, 그리고 최종적으로 더 이상 분해되지 않는 단말까지로 분해하는 방법에 대한 규칙이라고 할 수 있다.

문법 정의

단말 요소는 홑따옴표 안의 볼드체
비단말 요소는 일반 글꼴
- 하나 이상 있을 때, '|'표기를 쓴다.

statement: whileStatement | ifStatement | '{' statementSequence '}'
whileStatement: 'while' '(' expression ')'
                    statement
ifStatement: // if 문법 정의
statementSequence: '' | statement ';'
                        statementSequence

문법에 따른 코드

while (expression) {
  statement;
  statement;
  while (expression) {
    while (expression)
      statement;
    statement;
  }
}

10.1.3 구문 분석

구문 분석(parsing)은 문법에 따라 입력 텍스트가 유효한지 '확인'해보는 행위이다. 텍스트의 분석이란, 텍스트와 문법 규칙 사이의 정확한 대응 관계를 결정하는 일이다. 문법 규칙이 계층적이기 때문에 분석기가 생성하는 출력은 파스 트리나 유도 트리(derivation tree)라고 불리는 트리 기반 데이터 구조로 기술된다.

파스 트리

statement
└─ whileStatement
   ├─ while
   ├─ (
   ├─ expression
   │  └─ count <= 100
   ├─ )
   └─ statement
      ├─ {
      └─ statementSequence
         ├─ statement
         │  └─ count++
         └─ ;

재귀적 하양 구문 분석

파스트리를 구성하는 알고리즘 중 하향식(top-down) 접근법으로 재귀적 하양 구문 분석(recursive descent parsing)이 있다.
문법에 정의된 중첩 구조를 이용해 토큰 스트림을 재귀적으로 분석하는 방법이다.
방법
- 비단말 문법의 모든 규칙마다 그 규칙을 분석하기 위한 재귀적 루틴들을 하나씩 만들 수 있다.
- 문법을 따르는 재귀적 하향 구문 분석기를 만든다고 가정하면, 문법에서 유도되는 규칙에 맞게 수정할 수 있다.
  - parseStatement(), parseWhileStatement(), parseIfStatement(), parseStatementSequence(), parseExpression()
- 시작할 때 입력의 첫 번째 토큰이 무엇인지 결정부터한다.
- 첫번째 토큰 while 식별 => parseWhileStatement() => '(' => expression => ...

10.2 명세

10.2.1 잭 언어 문법

이 문법 명세는 다음과 같은 규칙을 따른다.

'xxx': 홑따옴표 볼드체는 글자 그대로 토큰에 사용된다.(단말)
xxx: 일반 글꼴은 언어 구조 이름에 사용된다.(비단말)
(): 괄호는 언어 구조들을 하나로 묶는 데 사용된다.
x | y: x또는 y가 나올 수 있음을 가리킨다.
x?: x가 0번 또는 1번 나타내는 경우를 가리킨다.
x*: x가 0번 이상 나타내는 경우를 가리킨다.

잭 언어 구문

어휘 요소: 잭 언어에는 다섯 가지 종류의 단말 요소(토큰)가 있다.

keyword: 'class' | 'constructor' | 'function' |
         'method' | 'field' | 'static' | 'var'
symbol: '{' | '}' | '(' | ')' | '[' | ']'
integerConstant: 0..32767의 10진수 숫자
stringConstant: '"' 따옴표와 줄바꿈 문자를 제외한 유니코드 문자열 '"'
identifier: 숫자로 시작하지 않는, 영문자, 숫자, 밑줄('_')로 이루어진 문자열

프로그램 구조: 잭 프로그램은 클래스로 이루어져 있으며, 클래스들은 각각 다른 파일에 있다. 컴파일 단위는 클래스 하나다. 클래스는 다음 문맥 자유 구문을 따라 구조화된, 토큰의 연속열이 된다.

class: 'class' className '{' classVarDec* subroutineDec* '}'
classVarDec: ('static' | 'field') type varName (',' varName)* ';'
type: 'int' | 'char' | 'boolean' | className
subroutineDec: ('constructor' | 'function' | 'method')
               ('void' | type) subroutineName '(' parameterList ')'
               subroutineBody
parameterList: ((type varName) (',' type varName)*)?
subroutineBody: '{' varDec* statements '}'
varDec: 'var' type varName (',' varName)* ';'
className: identifier
subroutineName: identifier
varName: identifier

명령문

statements: statement*
statement: letStatement | ifStatement | whileStatement
           doStatement | returnStatement
letStatement: 'let' varName ('[' expression ']')? '=' expression ';'
ifStatement: 'if' '(' expression ')' '{' statement '}'
             ('else' '{' statements '}')?
whileStatement: 'while' '(' expression ')' '{' statements '}'
doStatement: 'do' subroutineCall ';'
returnStatement: 'return' expression? ';'

표현식

expression: term (op term)*
term: integerConstant | stringConstant | keywordConstant |
      varName | varName '[' expression ']' | subroutineCall |
      '(' expression ')' | unaryOp term
subroutineCall: subroutineName '(' expressionList ')' | (className |
                varName) '.' subroutineName '(' expressionList ')'
expressionList: (expression (',' expression)* )?
op: '+' | '-' | '*' | '/' | '&' | '|' | '<' | '>' | '='
unaryOp: '-' | '~'
keywordConstant: 'true' | 'false' | 'null' | 'this'

10.4 정리

구문 분석기는 독립적인 프로그램이 아니며, 밑바닥부터 구현하는 경우는 드물다는 점을 말해둬야 겠다. 실제로 프로그래머들은 보통 LEX(어휘 분석 도구)와 YACC(Yet Another Compiler Compiler)같은 '컴파일러 생성기' 도구들을 이용해서 토큰화 모듈이나 구문 분석기를 만든다. 이 도구들의 입력은 문맥 자유 문법이고, 출력은 그 문법으로 작성된 프로그램을 토큰화하고 분석하는 구문 분석 코드가 된다. 그리고 컴파일 조건에 맞춰 생성 코드를 수정할 수 있다.

11장 컴파일러 2: 코드 생성

11.1 배경

고수준 프로그램을 저수준 언어로 컴파일 할 때는 데이터 번역과 명령 번역이라는 두가지 주요 문제에 집중하게 된다.

11.1.1 데이터 번역

프로그램은 정수나 불 같은 단순한 타입에서 배열이나 객체 같은 복잡한 타입까지 여러 종류의 변수 타입들을 조작한다. 변수의 생명주기와 변수의 종류도 주요 관심사다. 즉, 변수가 지역변수인지, 전역변수인지, 인수인지, 객체필드인지에 따라 다르게 처리하는 것이 중요하다.

기호 테이블

고수준 프로그램은 다양한 식별자(identifier)들을 도입한다. 각 식별자나 소스 프로그램에서 어떤 대상을 뜻하는지, 대상 언어의 어떤 구조로 매핑되는 지를 기록할 필요가 없다. 대부분의 컴파일러들은 이 정보들을 기호 테이블을 이용해서 관리한다.

식별자들은 식별자가 인식되는 영역을 뜻하는 범위(scope)를 가진다. 범위는 보통 중첩되며, 바깥쪽 범위에서 안쪽 범위의 정의에 접근 못하는 것이 일반적이다.

이름	타입	종류	#
nAccounts	int	static	0
id	int	field	0
name	String	field	1
balance	int	field	2
sum	int	argument	0
status	Boolean	local	0

11.1.2 명령 번역

표현식 평가하기

x + g(2, y-z) * 5같은 고수준을 평가하는 것이다. 구문 분석 트리를 짚어 가가며 동일한 의미의 VM 코드를 생성한다.

x + g(2, y-z) * 5 구문 분석

+
├─ x
└─ *
   ├─ g
   │  ├─ 2
   │  ├─ y
   │  └─ -
   │     └─ z
   └─ 5

목적 코드 생성

push x
push 2
push y
push z
neg
call g
push 5
call multiply
add

표현식들을 스택 기반 VM 코드로 번역하는 전략은 간단하며, 다음과 같이 파스 트리를 재귀적인 후위 순회하는 방식을 따르면 된다.

copyWrite(exp);
if exp is a number n       then output "push n"
if exp is a variable v     then output "push v"
if exp = (exp1 op exp2)    then copyWrite(exp1), codeWrite(exp2),
                           output "op"
if exp = op(exp1)          then copyWrite(exp1), output "op"
if exp = f(exp1 ... expN)  then copyWrite(exp1), ..., codeWrite(expN),
                           output "call f"

흐름 제어 번역하기

if, while, for, switch로 컴파일하는 것이다. 제어구조가 중첩될 수 있기 때문에 재귀적인 컴파일 기법을 쓰면 쉽게 해결가능하다.

밑바닥부터 만드는 컴퓨팅 시스템 컴파일러 - ChoDragon9/posts GitHub Wiki

10장 컴파일러 1: 구문분석

왜 이렇게 힘들게 컴파일러를 만들어 봐야 할까?

10.1 배경

10.1.1 어휘 분석

예제

10.1.2 문법

문법 정의

10.1.3 구문 분석

파스 트리

재귀적 하양 구문 분석

10.2 명세

10.2.1 잭 언어 문법

잭 언어 구문

10.4 정리

11장 컴파일러 2: 코드 생성

11.1 배경

11.1.1 데이터 번역

기호 테이블

11.1.2 명령 번역

표현식 평가하기

흐름 제어 번역하기

⚠️ GitHub.com Fallback ⚠️

밑바닥부터 만드는 컴퓨팅 시스템 컴파일러 - ChoDragon9/posts GitHub Wiki

10장 컴파일러 1: 구문분석

왜 이렇게 힘들게 컴파일러를 만들어 봐야 할까?

10.1 배경

10.1.1 어휘 분석

예제

10.1.2 문법

문법 정의

10.1.3 구문 분석

파스 트리

재귀적 하양 구문 분석

10.2 명세

10.2.1 잭 언어 문법

잭 언어 구문

10.4 정리

11장 컴파일러 2: 코드 생성

11.1 배경

11.1.1 데이터 번역

기호 테이블

11.1.2 명령 번역

표현식 평가하기

흐름 제어 번역하기

⚠️ **GitHub.com Fallback** ⚠️

⚠️ GitHub.com Fallback ⚠️