컴파일러 기말

2.3 Syntax-Directed Translation

문법에 나타나는 기호들에, 속성을 부착시켜서 구문을 체크하는 파싱과 동시에 부착된 속성을 분석하여 번역

속성이 부착된 문법 - 속성 문법 Attribute grammar

1. 합성 속성 Synthesized Attribute
   • 부모의 속성을 계산하기 위해서 자식들의 속성만 필요한 경우
   • 모든 기호에 부착된 속성을 계산할 때 후손들의 속성만 필요
2. 상속 속성 Inherited Attribute
   • 자식의 속성 + 부모의 속성 + 형제자매 속성값을 다 사용하는 경우

• 속성 계산에 순환이 일어나는 경우 ( A->B->C->A), 
  • 속성 문법을 사용한 파스트리에서 기호들에 부착되어 있는 속성들의 의존성을 그래프로 표시했을 때 싸이클이 있으면, 어디서부터 계산해야 하는지를 생각해야 함
  • 하지만 합성속성만 있는 경우에는 속성들의 의존성에 사이클이 생기지 않음

Synthesized Attribute

• Depth First Search
  DFS 로 깊이 우선 탐색을 통해 자식을 먼저 계산한 뒤 부모의 속성 값을 계산함

 

• Syntax Directed Defintion
  문법 + Semantic Rules (부착된 속성들 사이의 관계)
• Translation Schemes - 동적
  문법 + Semantic Action (의미 행동)

Translation Schemes

infix 수식, 좌우선 결합(left recursive)

• 생성규칙의 좌변에 non-terminal 이 하나
• 우변의 수식 어디에나 Semantic Action 을 끼워넣을 수 있음 ^ expr ^ + ^ term ^ : ^ 위치

Annotated Parse Tree

• 주석이 붙은 파스트리를 DFS 로 순회하면서 중간에 만나는 semantic action 이 있으면 실행

Emitting a Translation

: 번역된 결과를 내보냄

• Simple 한 생성 규칙
  • 생성규칙에서 우측에 나타나는 Non-terminal 들의 순서가 바뀌지 않아야 함
• simple 한 syntax directed definition 은 Translation scheme 으로 바꾸게 되면 파싱을 하면서 semantic action 을 바로 실행 (번역결과를 중간중간 내보냄)할 수 있음
• syntax directed definition 의 경우, 문법하고 semantic rule 이 따로기 때문에 문법을 통해 파싱을 해서 파스트리를 만들고 파스트리에 나타난 기호들에 부착된 속성값을 그 뒤에 계산
• simple translation scheme 은 파스트리를 별도로 구성할 필요 없음

2.4 Parsing

• sentence: 전체 프로그램 코드 (주어진 문법의 하나의 문장)
• statement: 터미널로만 이루어진 문장

num dotdot num -> 10 .. 100

 

Topdown 파서는 효율적인 파서를 손으로 쉽게 구성할 수 있기 때문에 쉬움

Bottom up 파싱은 더 큰 클래스의 문법과 번역, 체계를 처리할 수 있으므로 문법에서 직접 파서를 생성하기 위한 소프트웨어 도구는 상향식을 사용하는 경향이 있다.

 

Top-Down Parsing

non terminal 기호를 확장하며 파싱함

• 백트래킹
  논터미널 기호를 확장할 때, 확장 가능한 것들을 다 해보며 확장
  (일반적인 방법)
  • 백트래킹으로 일일이 다 확인하는 것 보다 미리 보고 체크하는 것이 효율적
  • lookahead symbol 사용
    • lookahead 를 두고 비교할 문장을 미리 보고 비교하여 일치하는지 확인함
• Non-determinacy 비결정성
  • 비결정성을 없애면 기계적인 알고리즘이 된다.
  • lookahead symbol 을 보고 그중에 하나로 결정할 수 있으면 멀티스레드 X, 백트래킹 X
• lookahead 심볼을 보고 힌트로 삼아 어느쪽으로 확장해야 할지를 체크함

• Input: array [num dotdot num] of integer
• <type> 을 확장했을 때 나올 수 있는 첫번째 터미널 기호
  FIRST(<simple>) => { integer, char, num }
  FIRST(↑id) => {↑}
  FIRST(array [ num ,,, ) => { array }
• FIRST 집합들이 서로 겹치지 않아야 어느쪽으로 확장할지 명확하기 때문에 결정적으로(명확한 길) 확장할 수 있음
  -> 카누스의 알고리즘은 제약이 없음

Predictive Parsing

• Recursive descent parsing (재귀 하강 파싱) 은 구문분석을 위한 Top-down 방법
  그 파싱 알고리즘 내에서 우리가 입력을 처리하기 위해서 재귀적 프로시저를 거듭 실행하는 방식으로 작동
  • 조건 
    • 본질적으로 recursion 이 있을 수밖에 없고
    • 파스트리는 root 부터 leaf 쪽으로 만들어진다
    • 백트래킹도 허용
• Recursive descent parsing 중에서 lookahead 를 힌트로 삼아서 예측을 해서 백트래킹을 하지 않는 파싱을 Predictive Parsing이라고 함
• 쓸만한 언어가 되려면 그 언어에 포함된 문장은 무한개여야 하고,
  무한개의 문장을 만들어내려면 문법에 재귀가 있어야 함
• 의미 있는 언어는 포함된 문장이 무한개
  -> 무한개의 문장을 만들려면 문법의 생성규칙이 재귀적으로 정의되어야 함
      -> predictive parser 의 경우 각 non-terminal 마다 담당 프로시저가 따로 있음
  
  • predictive parser 는 재귀적 호출이 꼭 나오게 되어있음

• 프로시저가 담당하는 일
  • type, simple 이라는 문법적 구조를 인식하는 일을 담당

Pascal Input
source: var a: ... array [ 1..100 ] of integer ...
after lexical analysis: ... array [ num dotdot num ] of integer

• 구분자에 따라 어휘 분석기가 보고 토큰으로 자름 -> string
• 토큰 길이 -> 가변적
• 파서로 넘어가는 데이터의 길이가 가변적
• 구문 분석기 -> 타입 선언 명시 형태가 제대로 되어 있는지가 관심사
  array [1..100] == array [2..200] 같은 것
  -> array [num..num]
  
  • 구문 분석기에서는 실제 숫자가 중요한 것이 아니고 형태만 중요하므로 구문 분석기로 토큰을 넘길 때 심볼 테이블에 identifier 로 지정해놓고 인덱스만 키핑해둠
  • 어휘분석기에서 구문 분석기로 정보를 넘길 때 (토큰) 꼭 소스 프로그램 그대로 lexeme 형태를 넘겨주지 않아도 됌
  • 구문 분석기에서 다루기 쉬운 형태의 값으로 넘겨도 됨 -> 정수
    (정수를 컴퓨터가 가장 편하게 다룸)
• lexeme -> 실제 소스 프로그램에서의 스트링 문자열
• predictive parsing 은 recursive descent 의 특별한 경우임
  lookahead 를 이용해 예측하기 때문에 백트래킹을 하지 않음
• lookahead : 아직 파싱이 완료되지 않은 남은 부분의 제일 앞에 있는 터미널

Parse Tree

• 다음 단계로 갈때, lookahead 를 보고 어느 쪽으로 갈지 결정함
• type 에서 확장할 때, 우변에 있는 생성 규칙들 중 lookahead를 만들 수 있는 생성규칙을 보고 정함
  FIRST(<simple>)
  FIRST(↑)
  FIRST(array,,)
• 파스트리의 노드가 터미널이면 입력의 lookahead 랑 비교했을 때,
  다르면 문장이 문법적으로 틀린 것
  같으면 다음 lookahead 를 비교

procedure match(t:token);
begin
    if lookahead = t then
    	lookahead := nexttoken // 다음 토큰으로 넘어감
    else error
end;
// if 문이 생성규칙의 각각의 우변을 담당
procedure type;
begin
    if lookahead is in {integer, char, num} then
    	simple
    else if lookahead = '↑' then begin
    	match('↑'); match(id)
    end
    else if lookahead = array then begin
    	match(array); match('['); simple; match(']');match(of);type
    end
    else error
end;

procedure simple;
begin
    if lookahead = integer then
    	match(integer)
    else if lookahead = char then
    	match(char)
    else if lookahead = num then begin
    	match(num);match(dotdot);match(num)
    end
    else error
end;

• greedy 한 알고리즘
  if 문에서 한번 걸리면 바로 매칭
  terminal 이면 match 프로시저를 호출함

46p

엡실론 Productions 을 언제 사용하는가

ϵ - production

stmt_list -> stmt_list; stmt | stmt

• ϵ 엡실론 프로덕션이 대안에 포함되어 있는 경우에는, 엡실론 프로덕션이 아닌 것들이 FIRST 에 속하는 터미널들이 lookahead 에 보이면 해당되는 대안으로 확장을 하고
  FIRST(stmt_list) 에 속하는 기호가 lookahead 에 안보이면 무조건 엡실론 프로덕션으로 확장을 하는 것
• 다른 대안이 없는 경우, 엡실론 프로덕션으로 확장하는 것

Predictive Parser 설계

(46p)

predictive parser -> pascal 의 타입 문법을 위한 것

Left Recursion

infix 수식 -> left recusion 문법 (좌우선 결합법칙)

• left recursion 이 존재해야 파스 트리가 왼쪽 편향 트리가 되고, 같은 우선순위로 묶어진 수식의 경우에 앞에서부터 먼저 엮인다.
• <expr> -> <expr> + <term> | <expr> - <term> | <term>

procedure expr;
    if lookahead ∈ FIRST(<expr> + <term>) then
        begin
            expr; match('+'); term;
        end
    else if ...

• expr 을 다시 호출하면 -> lookahead 가 그대로인 상태이기 때문에 무한 반복됨
• match 를 호출해야 lookahead 가 바뀜
• FIRST() : 모든 가능한 터미널 스트링 중에 제일 앞에 나타나는 터미널 기호들만 모아둔 것
• FIRST(<term>) ⊂ FIRST(<expr>) ⊂ FIRST(<expr> + <term>)
  0..9           num + num, num - num,  ϵ   FIRST(expr)
  • FIRST(<expr> + <term>): ϵ 이 expr 자리에 올 수 있기 때문에 FIRST( + ) 가 포함될 수도 있음
  • expr 이 term 이 될 수 있기 때문에, FIRST(<expr>) 에는 FIRST(<term>) 이 포함됨
• FIRST(array) ⊂ FIRST(array [<simple>] of <type>]) = { array }
• vocabulary string
  문법의 어휘 구성
  터미널 & 논터미널에 구애받지 않고 그것들이 이어져 있는 스트링
• vocabulary string의 FIRST 에는 그 스트링의 prefix 를 이루고 있는 것의 FIRST는 당연히 포함된다
• A -> A⍺ | β
  FIRST(β) ⊂ FIRST(A) ⊂ FIRST(A⍺)
  
  • 각 FIRST 가 겹치지 않아야 predictive parsing 을 할 수 있는데, FIRST의 교집합이 공집합이 아니기 때문에 Predictive parsing을 할 수 없다.
  • left recursion 이 있으면 대안들의 FIRST 가 겹치기 때문에 Predictive parsing 을 할 수 없다.
• root 부터 잘 보고, 입력을 힌트로 삼아서 확장하면서 터미널이 나타나면 greedy 하게 앞부분부터 입력과 매치시켜 나감

2.5 A Translator for simple expressions

Left Recursion 이 나타나면 Predictive parsing 알고리즘을 사용할 수 없으므로, Left recursion 이 나타나지 않는 문법으로 변형

A -> A⍺ | β

-> right recursion 으로 변환

A -> βR

R -> ⍺R | ϵ

• Left Recursion
  • <expr> -> <expr> + <term> | <term>
• Right Recursion
  • <expr> -> <term><rest>
  • <rest> -> +<term><rest> | ϵ

좌우선 결합법칙 semantic action - translation scheme

A = expr

⍺ = '+ term {print('+')}'

• A -> A⍺1 | A⍺2 | β
• 변경
  • A -> βR
  • R -> ⍺1R | ⍺2R | ϵ
• <expr> -> <term><rest>
• <rest> -> +<term>{ print('+') }<rest> | - <term>{ print('-') }<rest> | ϵ

Input: 9 - 5 + 2

annotated parse tree

• lookahead 가 터미널 기호(+, -)와 일치하는 것이 없으면 엡실론 프로덕션
  -> else: empty
• term() 에서 match 를 먼저 하면 lookahead 가 바뀌기 때문에 출력을 먼저 해야함

번역기 최적화

• 함수 호출 줄이기
  • 부차적인 처리에 비용이 많이 들어감
  • 비용: 재귀 함수 < 반복문
  • 재귀가 더 읽기 좋은 경우, 억지로 반복 구조를 쓸 필요는 없음
• tail recursion
  함수 제일 마지막에 자기 자신을 호출하는 것

무한루프와 같은 동작 방식, lookahead 가 +, - 가 아닐 때 빠져나온다.

goto 를 쓰지 않는게 더 좋으므로

이렇게 바꿔서 최적화한다.

 

predicate - 0, 1을 돌려주는 함수

 

• non terminal이면 담당 함수 호출
• terminal 이면 인자로 해서 match 호출
  match() 는 문법과 관계 없이 항상 똑같은 코드
  • match 는 lookahead 와 토큰이 같으면 ok , 다르면 syntax error

infix 를 postfix 로 변환

2.6 Lexical Analysis

어휘 분석 -> 입력 시간이 오래 걸림

• 어휘 분석기가 해야할 일
  • 공백, 주석을 지움 (사람을 위한 것일 뿐, 기계는 필요 없음)
  • 상수 -> 값보다 상수라는 것이 중요, 나중에 코드 생성을 위해서는 어떤 값인지 필요.
    • 상수, 변수, 예약어를 구분하기 위해 심볼 테이블에 (if, while, ) 키워드를 채워넣는 방식으로 저장하고 
      튜플 형태로 키워드를 표현
      <토큰 종류, symbol table index>
      <id, 1>
      <num, 60> -> 상수, 실제 값

어휘 분석기 인터페이스

1. 입력으로부터 문자 읽어들이기
2. 어휘 분석기에서 파서에게 토큰과 부착된 속성을 넘김
   <id, 1>, <num, 60>, <+, >
3. 어휘 분석기에서 입력에게 문자를 돌려줌
   i = j + 1;
   1; 을 읽은 다음에, 1까지만 처리하고 ;은 다시 돌려줌 -> 비효율적 (한글자씩 I/O 하는게 아니라 블럭 단위로 I/O 버퍼 관리)
   다음 어휘 분석이 ; 부터 진행됨

• getchar() 로 읽기
• ungetc() 로 다시 돌려줌
  입력 파일에서 파일 포인터 위치를 마지막에 읽은데서 앞으로 돌리는 것
  표준입력으로 c 한글자를 되돌려줌
• 토큰(identifier)을 파서에게 되돌려줌(caller)
  Parser가 메인프로그램 역할 -> 어휘 분석기에게 토큰 요청함
  • 추가 속성은 tokenval 에 담아서 리턴
  • <token type, attribute> 를 리턴하려면 -> 구조체, 참조매개변수, 전역변수를 사용해서 두 정보를 리턴할 수 있음
  • tokenval -> 전역변수

factor -> ( <expr> )

                 | num { print(num.value) } //(--> value)

FIRST((<expr>)) => { '(' }

FIRST( num ) => { num }

NUM => 256 (ASCII 범위 다음 값)

• FIRST 에서 나온 값과 lookahead 를 비교해서 if 문 수행

• 어휘분석기가 소스프로그램 그대로 받음
  -> 에러 메시지를 이해하기 쉽게 출력해주기 위해 lineno 를 체크함
  에러 줄을 알 수 있는 모듈이 어휘분석기밖에 없음
• <token, 추가속성>
  추가 속성이 없는 경우, tokenval 값이 NONE
• 의미있는 토큰이 나올 때까지 무한 반복, 나오면 자신을 호출한 parser 로 복귀
  token 값과 추가 속성을 담아서 감
• 숫자면, 2자리 이상인 경우가 있으므로 뒤에 나오는 숫자를 다 합침
• while 문에서 글자를 한글자 더 읽어들였기 때문에 다시 돌려줌

2.7 심볼 테이블

• symbol table 에 lexeme 을 저장할 때, 길이가 다 다르기 때문에 테이블이 균일하지 않음
  MAX 값을 설정하면, 길이가 짧은 lexeme을 저장할 경우 공간 낭비가 생김
• 길이가 다 다르기 때문에 1차원 배열에 따로 담고, lexptr에 주소나 인덱스 값을 담아둠
• 문자열 뒤마다 End Of String 표시를 해둠
• lexptr, token 값 저장
• "div" 를 호출하면 token 값으로 div 를 반환하므로, div, mod 값은 identifier 로 사용할 수 없음
  • 이런 식으로 심볼 테이블을 초기화하여 예약된 키워드들을 이런식으로 처리할 수 있음
• 어휘분석기가 단어를 읽을 때, 문자와 숫자를 lexbuf 버퍼에 저장하기 시작함
  • 그 다음 lexbuf 에서 수집된 문자열은 심볼 테이블에서 조회됨
• 심볼 테이블에서 lookup 연산을 사용하면, 기존 테이블에 있는 어휘는 찾아주고, 없는 어휘는 새로 추가한다.

 

2.8 추상 스택 머신

• JVM -> 스택 머신
  • Java 컴파일러 -> byte 코드로 변환됨 (중간언어)
  • 다양한 플랫폼을 감당하기 위해 가장 후진 성능, 스펙을 가짐 (원시적인 플랫폼)
• 스택을 accumulator 누산기로 사용함
• 메모리를 논리적으로 나눠서 사용
  • 코드 저장: Instructions
  • 스택
  • 데이터
• 스택에 data 두개를 push, 연산자가 오면 Top 에서 두개를 Pop 해서 연산한 후, 결과를 다시 스택에 push
• 후위 연산식을 계산할 수 있음
  • 1 3 + 5 *
  • PUSH 1
  • PUSH 3
  • +
    top 두개를 꺼내 더한 후, 다시 push
  • PUSH 5
  • *
    TOP 두개를 꺼내 곱한 후, 다시 push

L-values , R-values

• L-values
  
  • 값을 저장하는 용도
  • 저장할 위치, 주소
• R-values
  
  • 값

Stack Manipulation

• push v
  v 를 스택에 push
• rvalue L
  L에 위치한 데이터를 스택에 push
• lvalue L
  L의 주소를 스택에 push
• pop
  스택 top 을 꺼냄
• :=
  stack top 에 있는 rvalue(값)를 꺼내고, 그 밑에 있던 lvalue(주소)를 꺼내서 주소 위치에 값을 저장
• copy
  stack top 을 복사해서 push

Translation of Expressions

• 후위 표기식이어야 스택 머신이 계산할 수 있다.
• a + b
  rvalue a
  rvalue b
  +
  • a, b push 한 후 다시 두개 꺼내서 더함

day := (1461 * y) div 4 + (153 * m + 2) div 5 + d

• 스택 기계어로 번역 결과

translation

semantic action -> 후위 표기식

• lexeme
  토큰이 실제 프로그램에 나온 실제 문자열(변수명, 상수 값, )

Control Flow

• label L
  레이블 생성
• goto L
  label L 로 명령 옮김
• gofalse L
  스택의 top value 가 0 이면 jmp
• gotrue L
  스택의 top value 가 0이 아니면 jmp L
• halt
  실행 멈춤

Translation of Statements

• label test
  이 명령은 실행하지도 않고, 메모리 차지도 없고, 번역되지도 않음
  이 위치가 goto test 에 반영됨

if (expr) then ....

code for expr // expr 계산 -> 결과가 top 에 저장
if (stack.top-value == 0) // gofalse 결과가 거짓이면 out
	goto out
code for stmt // 참이면 stmt 실행
label out:

emitting 번역으로 위 코드처럼 만듦

Emitting a Translation

• print 대신 emit 함수 사용

semantic actions

이 translation schemes 를 그대로 코드로 옮긴 것이 아래 코드

 

<stmt> -> id := <expr> | if <expr> then <stmt1> | while <expr> do <stmt1> | for ,,,

procedure stmt;
var test, out: integer
begin
    if lookahead = id then begin
        emit('lvalue', tokenval); match(id); match(':='); expr
        // tokenval == lexeme : 심볼테이블 엔트리 값
    end
    else if lookahead = 'if' then begin
        match('if');
        expr;
        out := newlabel;
        emit('gofalse', out);
        match('then');
        stmt;
        emit('label', out);
    end
    else if lookahead == 'while' then begin
        test := newlabel;
        emit('label', test);
        match('while');
        expr;
        emit('gofalse', out);
        match('do');
        stmt;
        emit('goto', test);
        out := newlabel;
        emit('label', out);
    end
    	// 나머지 문장들을 위한 코드
    else error;
end

<문장을 번역하기 위한 슈도코드>

• emit
  • 별도로 정의된 함수
  • 방출하는 역할