[컴파일러] 2. 구문(Syntax) 중심 컴파일

 3/9

 

컴퓨터 언어의 정의

• 언어 구문: 일반적으로 문맥자유문법(CFG: context free grammar)이나 BNF(Backus-Naur Form)으로 표현
• 언어 의미: 표현의 어려움(설명 및 예제 사용)

문맥 자유 문법의 구성 요소

• CFG: <∑, N, S, P>
• ∑: 단말 기호(토큰의 집합)
• N: 비단말의 집합
• S: 생성 규칙
• P: 출발기호(비단말의 특수한 경우)

 

생성규칙(production rule)

• 왼쪽 문법 기호가 오른쪽 문자열을 생성한다.
• ex) stmt--> if(expr) stmt else stmt
• ex) list -> list + digit | list - digit | digit
• ex) digit -> 1|2|3|4|5|6|7|8|9

 

언어: 생성 규칙에 따라 만들어진 토큰 열 ex) 9-5+2, 3-1

 

파스트리의 특징

• 루트는 출발기호를 이름으로 가진다
• leaf 노드는 토큰이나 \(\epsilon\)[1]을 가진다.
• 중간 노드들은 비단말 이름을 갖는다.
• 비단말 노드 A에 \(X_1, X_2, ...X_n\)이 왼쪽에서 오른쪽으로 붙어있다면 생성규칙 A-> \(X_1, X_2, ...X_n\)를 나타낸 것이다.

파싱: 주어진 토큰열(언어)에 대해 적절한 파스트리를 찾는 과정

생성(또는 유도): 파스트리에서 leaf는 루트노드에 있는 비 단말에서 곧바로 생성/유도된 문자열(왼쪽에서 오른쪽으로 읽는다)

 

모호성(Ambiguity): 토큰열에 대해 파스트리가 2개 이상 나오는 경우. 의미 또는 문법

 

연산자우선순위: 일반적 경우와 같음. 괄호->제곱->곱셈/나눗셈->덧셈/뺄셈

연산자 연관성(associativity): 같은 연산의 묵시적 수행 순서. 지수나 C언어의 =은 오른쪽 연관. 일반적 사칙연산은 왼쪽 연관.

 

구문 중심 변환(Syntax-directed translation): 컴파일러 전반부(분석부분)을 주로 사용하여 변환하는 기술

• 문맥자유문법을 이용하여 컴파일러가 입력문자열에 대해 구문적 분석
• 문법 기호와 속성 연결
• 생성규칙 기호와 속성 처리를 위한 의미 규칙 연결

애노테이티드 파스트리: 각 노드의 속성들의 값이 쓰여있는 파스트리. 문법기호 X에 대한 속성 a는 X.a로 표시

속성: 생성에 관련된 타입, 문자열, 할당된 메모리 등

합성 속성(Synthesized Attributes): 노드의 속성값이 그 자식 노드들의 속성값으로 계산된 것.

 

번역계획: 생성규칙의 오른쪽에 의미동작(semantic actions)이라는 프로그램 일부를 넣은 것. 문맥 자유문법의 일종

ex) rest-> + term {print('+')}rest_1

간단한 구문 중심 정의: 오른쪽 비단말의 번역결과를 원래 순서대로 연결하면서 약간의 문자열을 추가하여(또는 추가 없이) 생성규칙의 왼쪽에 있는 비단말을 정의

---

[1] NULL인 경우