[Programming Language Theory] 4장 프로그래밍 언어의 구문과 구현 기법

4장 프로그래밍 언어의 구문과 구현 기법

4.0 Intro

PL = Syntax(언어 구문) + 언어 의미
Syntax(구문) : PL의 구조를 의미한다.

- 구문과 의미 모두 자연어로 기술될 수 있다. 실제로 초창기 PL의 구문과 의미 모두 영어로 기술된 형태였다.
- 구문은 오랜 기간동안 사용된 방법인 형식 시스템으로 기술된다.
- 오늘날에도 대부분의 언어 의미는 영어로 기술된다.

Context Free Grammar(문맥 자유 문법)
- 1950년 Noam Chomsky가 고안한 개념이다.
- Formal Definition이 뒷 받침되어야 하는 문법이다.
- 문맥 자유 문법을 기술하기 위한 표기법으로 BNF 표기법이 있다.

BNF 표기법
- 문맥 자유 문법을 기술하기 위한 표기법이다.
- 1963년 Algol60 구문을 기술하는데 처음 사용되었으며, 이후 Pascal, Modula, C, Ada, Java와 같은 많은 PL 정의에 사용되어왔다.
- 오늘날 표준화 된 표기법처럼 사용되고 있다.
- BNF의 변형된 형태로 EBNF, 구문 도표(Pascal에서 사용) 등이 있다.

H/W Computer (Actual Computer)
- 전선, 트랜지스터, 마그네틱 코어, IC 등 실제 눈에 보이는 장치들을 사용하여 구성한 컴퓨터이다.

S/W Simulated Computer
- 주어진 컴퓨터를 프로그램으로 구성하는 컴퓨터이다.
- 다른 컴퓨터의 프로그램으로 주어진 컴퓨터를 시뮬레이션함으로써 구성되는 컴퓨터이다.
- H/W 위에 특정 언어의 번역기와 운영체제가 합쳐저 가상의 고급 언어 컴퓨터로 간주된다.
ex) Cobol 컴퓨터 = Cobol 번역기 + OS
- 번역된 프로그램을 실행하는 컴퓨터는 대부분 S/W 컴퓨터(Virtual Computer)로 분류되나, 드물게 H/W 레벨에서 프로그램을 실행하도록 설계된 컴퓨터도 존재한다.
- H/W와 S/W를 혼용하는 가상 컴퓨터가 일반적이다.
- 이론적으로 고급 언어를 기계어로 하는 컴퓨터 구성이 가능하나, 저급 수준의 기계어로 하는 컴퓨터가 속도, 유연성(적응성), 비용 측면에서 유리하다.
※ 인간은 고급 언어로 프로그래밍을 하고, 컴퓨터는 저급 언어로 실행시키기 위해 언어 구현이 필요한 것이다.

---

4.1 언어 구문

4.1.1 PL의 어휘 구조

- 사용자가 입력할 수 있는 모든 문자가 Binary Code에 대응되어 입력에 대비한다.
- 모든 PL에서는 26개의 영문 대문자, 10개의 아라비아 숫자로 구성된 문자 집합에 기본을 둔다.
ANSI Fortran77 : 26개 영문 대문자, 10개 숫자, 13개 특수문자 (공백(\(\not{b}\))을 포함한 특수문자)
Algol 60 : 52개 영문 대소문자, 10개 숫자, 28개 특수문자

오늘날 컴퓨터에서 사용하는 대표적인 문자 코드 체계
1. EBCDIC (Extended Binary Coded Decimal Interchange Code)
- IBM에서 고안한 코드 체계이다.
- 8bits를 조합하여 최대 256개의 문자를 표현할 수 있다.

2. ASCII (American Standard Code for Information Interchange)
- ANSI(American National Standard Institute)에서 고안한 코드 체계이다.
- 7bits를 조합하여 최대 128개의 문자를 표현할 수 있다.
- 52개 영문 대소문자, 10개 숫자, 33개의 특수문자를 인쇄할 수 있다.
- I/O 장치 간 자료 전송을 제어하기 위한 33개의 제어 문자가 존재한다. (CRLF 등)

3. Uni code
- 각 국가들의 문자 코드에 관한 문제를 해결하기 위해 고안되었다.
- 16bits를 조합하여 최대 65,536개의 문자를 표현할 수 있다.
- ISO(International Organization for Standardization) 표준 규격이며, Java가 채택한 코드 체계이다.

Collating Sequence (정합 순서)
- 문자들 간의 순서를 의미한다.(0 < 1 < 2 ... < A < B < C < ...)
- 컴퓨터 내부에서 Sorting 등의 기본 동작이 이루어지는 기본 원리이다.
- 언어 Design(구현) 시에 결정하며, 문자 집합을 비트 조합으로 표현하는 순서를 결정하는 방식이다.
- 문자 처리 전용 언어 RPG, Snobol, Pearl 등에선 정합 순서를 프로그래머가 정의할 수 있다.
- ANSI Fortran 77 : 공백 문자가 문자 A나 숫자 0보다 우선시 된다.
- Snobol : 변수 &ALPHABET에 값을 배정하여 정합 순서를 사용자 임의대로 정의할 수 있다.
- Ada, Pascal : 오름차순으로 정의된 ASCII 코드 128개 전체를 CHARACTER 타입으로 제공한다.

PL 어휘 구조와 구문 구조
- Lexicon(어휘)은 문자들의 집합을 의미하는 개념이다.
- PL의 어휘구조의 최소 단위는 어휘 토큰이다.
- 어휘 토큰은 PL 알파벳*으로 구성되어 있다.
- 구문 구조와 별개의 개념이나, 서로 밀접하게 연관되어 있다.

* PL 알파벳 : 프로그래밍 언어를 구성하는 Atomic한 구성 요소로, 영문자와 숫자 특수문자등이 이에 해당될 수 있다. (단순히 영문자 알파벳만을 의미하는 것이 아니다.)

1. Lexical Analysis (Scanning, 어휘 분석)
- 번역기가 입력 프로그램의 일련의 문자들을 토큰으로 구분하는 단계이다.

2. Syntax Analysis (구문 분석)
- 구분된 토큰들의 의미를 파악하여 구문 구조를 결정하는 단계이다.

언어 구성자(Language Construct)
- 하나 이상의 Lexical Token(어휘 토큰)*으로 구성된, 구문적으로 허용된 프로그램의 일부 구조를 의미한다.
- 식별자, 구분자를 포함하는 개념이다.

Lexical Token (어휘 토큰)
- 예약어와 같이, 미리 정의된 어휘들을 한 번에 나타내는 토큰으로, 언어 구성자의 일부이다.
- Lexical Element(어휘 요소), Lexical Unit(어휘 단위)와 동의어이다.

Identifier(ID, 식별자)
- 하나의 어휘 토큰으로 구성된 언어 구성자를 의미한다.

Predefined Identifier(미리 정의된 식별자)
- 번역 속도, 프로그램 신뢰성 향상을 위해 PL이 미리 정의해놓은 식별자를 의미한다.
ex) scanf, printf, strcpy, #define, if, while, int 등
- 변수명, 함수명은 미리 정의된 식별자에 해당되는 이름으로 지을 수 없다.

Reserved Word(예약어)
- PL에서 미리 정의해놓은 단어나 기호 형태의 어휘이다.
- Predefined ID 중, 재 정의할 수 없도록 설정된 ID를 의미한다.
- 프로그램 가독성, 판독성을 높인다.
- 컴파일러의 기호 테이블 탐색 시간을 단축시킨다. (번역 시간이 감소한다.)
- 오류 회복이 가능하다.
- 일정량 이상의 예약어를 모두 기억할 수 없다.
- 기존의 언어를 확장할 때, 새로 추가된 예약어가 확장 이전에 사용했던 예약어를 Overwrite할 경우, 프로그램의 의미가 달라질 수 있다. (즉, 적절한 개수의 예약어 정의가 필요하다.)
ex) if, while, for, int 등
- 일반적으로, 최근에 설계된 PL일수록, 예약어의 수가 많은 경향을 보인다.
ex) C언어 32개, C++ 49개, Ada 62개
Algol 60 : Subprogram을 procedure만으로 구현한다.
Ada, Pascal : Subprogram을 procedure, function으로 구분지어서 구현한다.

Separator(분리자, 구분자)
- 예약어처럼 Delimiter역할(요소들 사이를 구분짓는)을 하는 특수 문자, 토큰, 공백 등의 서식 제어자를 의미한다.

4.1.2 문맥 자유 문법과 BNF

언어 구문의 형식 정의
- PL을 통해 정상적인 프로그램을 작성하는 규율들의 집합을 의미한다.
- 이 규율들은 적용되는 공식, 순서도를 통해 표현된다.
- PL 구문 형식 정의를 통해 해당 PL로 어떤 표현이 가능하고, 어떤 표현이 사용 불가한 지를 알 수 있다.
- 구문 형식을 정의하는 가장 보편적인 기법으로 BNF 표기법*, EBNF 표기법, 구문 도표를 통한 표현 방법이 있다.
- 하나의 언어 구문에 대한 BNF 정의는 Production Rule(생성 규칙)들의 집합이다.

* BNF 표기법 (Backus Naur Form Natation)
- 문법(구문 형식)을 표기하는 대표적인 방법 중 하나이다.
- 1963년 Algol 60 구문을 정의할 때 최초로 사용되었다.
- 이후 BNF를 확장한 EBNF 표기법이 많은 PL의 구문 표기에 사용되었다.
- Reduce : BNF식에서 Terminal에서 Non-Terminal로 해석하는 방향을 의미한다. (← 방향, 우변에서 좌변 방향)
(입력된 문장이 BNF 문법에 맞으면 Reduce가 반복되어 마지막 Non-Terminal 노드만 남게 된다.)
- Produce : BNF식에서 Non-Terminal에서 Terminal로 해석하는 방향을 의미한다. (→ 방향, 좌변에서 우변 방향)
(BNF 문법에서 특정 형태 문장의 문법 부합 여부를 조사하기 위해 Non-Terminal부터 Produce를 수행하여, 해당 문장의 파스트리 존재 여부를 리턴한다.)

Production Rule(생성 규칙)
- 언어에서 문장을 생성하는 규칙이다. (PL 문장은 문법에 의거하여 생성되어야 한다.)
- 이론적으로, 생성 규칙을 통해 해당 언어로 작성 가능한 모든 정상적인 프로그램을 산출하는 것이 가능하다.
- 생성 규칙은 작성된 프로그램이 구문에 부합하는 지를 판단하는 구문 규율로도 사용된다.
- 생성 규칙에서, 왼쪽에는 정의될 대상 Object, 오른쪽에는 Object에 대한 정의 내용이 위치하게 된다.

Meta* Symbol(메타 기호)
- Symbol을 정의하기 위한 Symbol이다.
- 언어의 일부가 아닌, 언어를 표현하기 위해 사용되는 특수 기호를 의미한다.
::= 기호 : "정의된다"를 의미하는 기호이다. 좌측 대상이 우측 정의 내용으로 대체될 수 있음을 의미한다.
| 기호 : 택일을 의미한다.
<> 기호 (Nonterminal, 비단말 기호) : BNF 규율로 다시 정의될 대상을 의미한다.
<>로 묶이지 않은 기호 (Terminal, 단말 기호) : 키보드에서 입력할 수 있는 기호로, 각 PL에서 사용되는 알파벳 문자 집합과 예약어들을 의미한다. 비단말 기호 내에서, 언어에서 사용하는 단말 기호와 메타 기호가 중복될 경우, 언어에서 사용하는 기호를 작은 따옴표로 감싸서 표현한다.

* Meta : 한 단계 높은 개념을 의미하는 용어이다.
ex) Meta data : 데이터에 대한 데이터
ex) Meta Structure : 구조에 대한 구조
ex) Meta Physics : 형이상학

Ex. BNF 표기를 통한 식별자 정의 예시

<identifier> ::=<letter>| <identifier><letter> | <identifier><digit>
<letter> ::=A | B | C | ... | X | Y | Z
<digit> ::=0 | 1 | 2 | ... | 8 | 9

- Recursion을 통한 정의 방법이다. (좌변, 우변에 모두<identifier>가 나온다.)
- <identifier>는 알파벳 대문자가 먼저 한 글자 나온 후, 그 뒤에 알파밧 대문자 혹은 숫자가 선택적으로 붙게된다.
- <letter>는 영문 대문자를 Produce할 수 있다.
- <digit>는 숫자를 Produce할 수 있다.

Ex. Single Quotation(작은 따옴표)를 통한 메타 기호와 언어에서 사용하는 단말 기호 구분 예시

<BNF-rule> ::=<left-part> '::=' <right-part>
<right-part> ::=<right-part-element> {'|' <right-part-element> }

Context Free Grammar(문맥 자유 문법)
- 모든 생성 규칙에서, 정의 될 Object가 하나의 <>기호(비단말 기호)만으로 구성되는 문법이다. 즉, 어떠한 Context(문맥)에서도 무조건 좌측 내용이 우측 내용으로 대치된다.

Context Sensitive Grammar(문맥 의존 문법)
- 좌측 내용이 우측 내용과 특수한 문맥에 의존하여 대치되는 문법이다.
- 일반적으로 PL에서 문맥 의존성 관련 사항은 구문론적 문제 보다는 의미론적 문제로 간주한다.

EBNF (Extended Backus Naur Form Natation)
- BNF 표기법보다 읽기 쉽고, 간결하게 표현할 수 있도록 확장된 표기법이다.
- EBNF를 사용함으로써 비단말 기호의 개수를 줄이고, 간결하게 표현할 수 있다.

{ } 기호 : 반복되는 부분을 나타낸다. {a}는 a가 0번 이상 반복될 수 있음을 의미한다. 중괄호 뒤에 두 자리 숫자를 기재함으로써 최대 반복 수와 최소 반복 수를 지정할 수 있다.
ex) {a}70 : a는 최대 7회, 최소 0회 반복될 수 있음을 의미한다. (BNF 표기에서는 복잡하게 구현되는 부분이다.)

[ ] 기호 (Optional Part, 선택적 부분 기호) : 선택적인 부분을 표시한다. [x]는 x가 0회 혹은 1회 나타날 수 있음을 의미한다.
ex) {a}10과 [a]는 같은 의미이다.

' ' 기호 : EBNF에서 사용하는 메타 기호와 언어에서 사용되는 단말 기호가 중복되는 경우, 언어에서 사용하는 단말기호는 Single Quotation(작은 따옴표)로 감싸서 Terminal로 표현한다.

Ex. EBNF 표기 예시 (영문자로 시작하여 최대 8개의 문자를 가질 수 있는 식별자 표현)

<identifier-name> ::=<letter> {<alphanumeric>}70
<alphanumeric> ::=<letter> | <digit>
<letter> ::=A | B | C | ... | X | Y | Z
<digit> ::=0 | 1 | 2 | ... | 8 | 9

Ex. if 문에서 else문이 선택적임을 표현하는 EBNF 표기 예시

<if-statement> ::=if <condition> then <statement> [else <statement>]

Ex. Subpascal 시작부에 대한 EBNF 표기 예시

<subpascal>    ::=program <ident> ; <block> .
<block>        ::=[<const_dcl>][<var_dcl>]{<proc_dcl>} <compound-st>
<const_dcl>    ::=const <ident> = <number> {; <ident> = <number>}
<var_dcl>      ::=var <ident_list> : <type> { ; <ident_list> : <type> };
<ident_list>   ::=<ident> {,<ident>}
<proc_dcl>     ::=procedure <ident>['('<formal_param>')'] ; <block> ;
<compound-st>  ::=begin <statement> { ; <statement>} end

- program, begin, end와 같은 키워드들은 추후에  토큰으로 변환되게 된다.
- Semicolon(;)을 Terminator와 Separator로 혼용하고 있음을 볼 수 있다.
- Terminator : 한 BNF 문법을 종결한다.
- 즉, 위 코드는 Terminator와 Separator를 구분하기 어려우므로 좋은 문법이라 할 수 없다.

- <const_dcl> : const <ident> = <number> 문 뒤에 <ident> = <number> 문들이 세미 콜론을 기준으로 0회 이상 반복된다.
- <var_dcl> : <const_dcl>과 비슷한 메커니즘이다.
- <ident_list> : 하나 이상의 <ident>를 Comma로 구분한다.
- <proc_dcl> : procedure키워드 뒤에 <ident>가 위치하고,(<formal_param>)가 0~1회 존재하고, 세미콜론이 붙고 <block>; 이 붙는다.(Syntax를 정의하기 위한 간접적인 Recursion)

- 이 Syntax Diagram에서 <ident_list>는 따로 표현되지 않았다.

Ex. Compound Statement(복합문)의 BNF와 EBNF 표기 예시

BNF Notation
<compound-statement> ::=begin <statement-list> end
<statement-list> ::=<statement> | <statement-list> ; <statement>


EBNF Notation
<compound-statement> ::= begin <statement> {; <statement> } end

4.1.3 Syntax Diagram (구문 도표)
- 구문 도표는 EBNF에 곧바로 대응되며, 순서도와 형태가 유사하다.
- 고급 언어의 구조를 구문 도표를 통해 표시하는 경우가 빈번하다.
- 단말은 원, 타원으로 표시한다.
- 비단말은 사각형으로 표시한다.
- 단말 혹은 비단말과 같은 Object들 사이는 지시선으로 연결한다.

구문 도표 기호

X
- Terminal X를 의미한다.

<X>
- Non-Terminal X를 의미한다.


\(\texttt{A ::=} X_{1}X_{2} \cdots X_{n}\) 일 때,

\(X_{i}\)가 단말 기호인 경우

\(X_{i}\)가 비단말 기호인 경우

\(\texttt{A ::=}a_{1}|a_{2}| \cdots |a_{n}\) (Non-Terminal \(a_{i}\))

EBNF \(\texttt{A ::=}\{a\}\)
(Non-Terminal \(a\)를 0회 이상 반복)

EBNF \(\texttt{A ::=}[a]\)
(Non-Terminal \(a\)를 0회 혹은 1회 반복)

EBNF \(\texttt{A ::=}(a_{1}|a_{2})b\)

Ex. EBNF 표기와 구문 도표 비교 예시

1. EBNF 표기

A ::=x| '('B')'
B ::=AC
C ::={+A}

조건
VN = {A, B, C} (Set of Non-Terminal)
VT = {+, x, (, )} (Set of Terminal)

2. 구문 도표

3. 구문 도표 (비단말 기호가 지칭하는 것을 대입하여 통합한 형태)

4.1.4 파스 트리와 추상 구문 트리(AST)

Parse Tree(파스 트리)
- 트리 구조로 생성되는 Parsing(구문 해석)의 결과이다.
- BNF로 작성한 표현이 설계자가 의도한대로 작성되었는가를 파스 트리와 비교하여 검증한다.
- 파스 트리의 Root는 BNF 식에서 표현한 Object에 해당하고, 단말 노드들이 Leaf에 위치하게 된다.
- 주어진 표현에 대한 파스 트리가 존재하면, "해당 표현은 주어진 BNF에 의해 작성되었다."라 표현한다. 
- 주어진 표현에 대한 파스 트리가 존재하지 않으면, "해당 표현은 주어진 BNF에 의해 작성될 수 없다."라 표현한다.
- Syntax Error는 프로그래머가 입력한 Syntax가 Parsing 불가함을 나타내는 에러이다.
- 우선 순위가 높은 연산자일수록, 파스 트리의 Leaf에 가깝게 배치된다.
- 우선 순위가 낮은 연산자일수록, 파스 트리의 Root에 가깝게 배치된다.

Abstract Syntax Tree(AST, Abstract Parse Tree, Syntax Tree, 추상 구문 트리, 구문 트리)
- 파스 트리에서 불필요한 비단말 노드를 제거한, 요약된 형태의 트리이다.
- 파스 트리의 본질적인 구조를 표현한다.

Ex. BNF 표기와 파스 트리를 통한 검증 과정

1. BNF 표기

<identifier> ::=<letter>| <identifier><letter> | <identifier><digit>
<letter> ::=A | B | C | ... | X | Y | Z
<digit> ::=0 | 1 | 2 | ... | 8 | 9

- 검증할(Reduce할) 식별자 : "TEST1", "3A1"
- 생성할(Produce할) 식별자 : "B33"

2.1 파스 트리 ("TEST1")

Parse Tree : "TEST1"

- 입력 T, E, S, T는 <letter>로 Reduce되며, 입력 1은 <digit>으로 Reduce된다.

2.2 파스 트리 ("B33")

1번 방법
<indetifier> → <indentifier><digit> → <identifier>3 → <idnetifier><digit>3 → <identifier>33 → <letter>33 → B33
(→ 는 Produce를 의미한다. 즉, Non-Terminal 노드가 Terminal 노드로 변환된다.)

2번 방법
<identifier> → <identifier><digit> → <identifier><digit><digit> → <letter><digit><digit> → B<digit><digit> → B3<digit> → B33

※ 서로 다른 방법으로 Produce해도 결과는 같다. 즉, 문법이 정확하면 서로 다른 유도과정을 거쳐도 파스 트리가 유일한 형태로 리턴된다.

2.3 파스 트리 ("3A1")
- "3A1"은 파스 트리로 표현할 수 없다. digit가 앞서는 경우는 BNF 표기에서 정의되지 않았기 때문이다.

Ex. BNF 표기를 통한 문맥 자유 문법 수식 정의 예시

1. BNF 표기

<exp>      ::= <exp> - <exp> | <exp> * <exp> | (<exp>) | <number>
<number>   ::= <number> <digit> | <digit> 
<digit>    ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9  

2. 파스 트리

3. AST

Ex. 파스 트리를 통한 BNF 문법 유추

1. Parse Tree

2. BNF Code

<term>        ::= <primary>
                | <term> * <primary>
                | <term> / <primary>

<expression>  ::= <expression> + <term>
                | <term>
                | <expression> - <term>

Ex. C언어에서의 수식에 대한 Parse Tree 예시

-
 
Ex. C언어에서의 Declaration Statement Parsing 예시

- ANSI C Yacc

declaration
	: declaration_specifiers ';'
	| declaration_specifiers init_declarator_list ';'
	;

- 입력된 문자열 \(\texttt{typedef, unsigned, long, int, ul_int, ;}\)는 Lexical Analyzer를 통해 각각 \(\texttt{TYPEDEF, UNSIGNED, LONG, INT, IDENTIFIER, ;}\) 토큰으로 매칭된다. (이 과정은 Reduce되었다고 표현하지 않는다.)
- declaration_specifiers는 Right-Rucursion으로 구현되었음을 추측해볼 수 있다.

- 
Ex. C언어에서의 \(\texttt{while}\) Statement Parsing 예시

1. ANSI C Yacc

iteration_statement
	: WHILE '(' expression ')' statement
	| DO statement WHILE '(' expression ')' ';'
	| FOR '(' expression_statement expression_statement ')' statement
	| FOR '(' expression_statement expression_statement expression ')' statement
	;

 

- 위 트리는 \(\texttt{WHILE}\)이 \(\texttt{while(x<20) x = x + y * 2}\)을 Produce한다.

4.1.5 모호성, 결합성 및 우선 순위
- 하나의 String에 대해 서로 다른 Parse 혹은 Syntax Tree가 생성되는 경우, 이를 Ambiguous Grammar(모호한 문법)이라고 표현한다.
- 모호한 문법은 모호함이 없도록 개정하거나, Disambiguating* Rule(모호성 제거 규칙)을 기술해야 한다.

*Disambiguation(모호성 제거)
- 동일한 어휘 토큰 순서를 가진 다수의 언어 구성자 중, 어떤 언어 구성자를 프로그램 내의 특정 사건이 참조하는지를 결정하는 행위이다.
- 문법을 개정하여 프로그래머가 의도한 유일의 파스 트리가 생성되도록 하는 것이다. 즉, 어떠한 경우에도 한 문장에 대해 동일한 파스 트리가 형성되도록 하는 것이다. 

Precedence Cascade(순위 폭포)
- 문법을 개정하여 모호성을 제거하는 방법 중 하나이다.

Ex. 뺄셈 보다 높은 우선순위를 갖는 곱셈을 순위 폭포 식으로 정의하는 BNF 표기 예시

<exp>    ::= <exp> - <exp> | <term>
<term>   ::= <term> * <term> | (<exp>) | <number>

- 위 표기는, 곱셈과 뺄셈 사이의 우선순위는 명백히 정의했으나, 뺄셈이 연속되는 경우(결과값에 차이는 없다)의 모호함은 해결하지 못한다. 즉, 한 문장에 대한 문법 적용 순서에 따라 서로 다른 다수의 파스 트리가 생성될 수 있다.
- "7-3-2"에 대해, Left-Associate(좌결합) : "(7-3)-2" 또는 Right-Associate(우결합) : "7-(3-2)" 두 개의 파싱 결과가 초래된다.

※ 좌결합은 Left-Recursion, 우결합은 Right-Recursion으로써 구현한다.
\(\texttt{<exp>::= <exp> - <exp>}\)  (Ambiguous)
\(\texttt{<exp> ::= <exp> - <term>}\)  (Left-Recursion → Left-Associate)
\(\texttt{<exp> ::= <term> - <exp>}\)  (Right-Recursion → Right-Associate)

Ex. 좌 순환 규칙을 적용한 순위 폭포 BNF 표기 예시

<exp>    ::= <exp> - <term> | <term>
<term>   ::= <term> * <term> | (<exp>) | <number>

- 위와 같이 개정하면, 뺄셈 연산에 대해 좌결합으로 파싱된다.
- 일반적으로, 대부분의 언어에서는 동일 연산 순위를 갖는 연산자들은 좌결합이 수행된다.
(APL 언어는 우결합이 수행되는 몇 안되는 언어이다.)

Ex. 우선순위와 좌결합을 동시에 지원하는 문법 예시

<exp>     ::= <exp> - <term> | <term>
<term>    ::= <term> * <factor> | <factor>
<factor>  ::= (<exp>) | <number>
<number>  ::= <number><digit> | <digit>
<digit>   ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

- <factor> 정의 내용은 괄호가 있는 수식은 숫자 하나만 있을 때와 우선순위가 같을 만큼 높은 우선 순위로 처리하게끔 한다.

4.1.6 구문과 프로그램 신뢰성
Spelling Error(철자 오류) : 프로그래머가 프로그램 작성 시, 철자를 잘못 기입하여 발생하는 오류이다. 변수의 선언을 명확히 하지 않는 언어(데이터형을 명시하지 않는 언어)에서는 이러한 오류를 묵시적 선언으로 간주하여 디버깅을 어렵게 하고, 신뢰성을 저하시킨다.

Dangling \(\texttt{else}\) (현수 \(\texttt{else}\))
- 다중 \(\texttt{if}\)문에서 \(\texttt{else}\)문이 어느 \(\texttt{if}\)문에 매칭되는지 명확하지 않은 경우를 해결하는 방법을 의미한다.
- Dangling \(\texttt{else}\)는 아무 작업도 수행하지 않고, 단지 \(\texttt{if}\)와 짝을 맞추기 위해 존재하는 \(\texttt{else}\)를 의미한다. 
- BNF 문법과 관계없이 언어 자체가 포함하고 있는 모호성이다.
(Syntax는 모호하고, Semantic는 애매한 문제이다.)

if cond1 then if cond2 then S1 else S2     <!-- Dangling else -->

if cond1 then (if cond2 then S1 else S2)   <!-- 1번 해결책 (두 번째 if와 묶임) -->
if cond1 then (if cond2 then S1) else S2   <!-- 2번 해결책 (첫 번째 if와 묶임) -->

Ex. 언어별 Dangling else 사용 예시

<!-- Algol60 -->
if cond1 then begin if cond2 then S1 else S2 end   <!-- 1번 해결책 -->
if cond1 then begin if cond2 then S1 end else S2   <!-- 2번 해결책 -->

<!-- Algol68 -->
if cond1 then if cond2 then S1 else S2 fi fi       <!-- 1번 해결책 -->
if cond1 then if cond2 then S1 fi else S2 fi       <!-- 2번 해결책 -->

<!-- PL/I -->
IF cond1 THEN IF cond2 THEN S1; ELSE S2;           <!-- 1번 해결책 -->
IF cond1 THEN IF cond2 THEN S1; ELSE; ELSE S2;     <!-- 2번 해결책 -->

<!-- Pascal -->
if cond1 then begin if cond2 then S1 end else S2   <!-- 1번 해결책 -->
if cond1 then if cond2 then S1 else else S2        <!-- 2번 해결책 -->

- Algol60 : if 구조가 then에 내포되는 것을 허용하지 않는다. begin-end 구문으로 삽입한다.
- Algol68 : if 구조의 끝을 명시하는 fi 식별자를 사용한다. (간결하고 명확하게 하는 효과를 보여, Ada도 이 방법을 채택했다.)
※ PL/I과 Pascal의 경우 1번 해결책을 Default로 두고, 2번 해결책으로 구현하기 위해 문장없는 else 혹은 begin-end 구문을 사용한다.

---

4.2 프로그래밍 언어 구현 기법
- 고급 언어를 사용하는 프로그래머와 저급 언어를 이해하는 컴퓨터* 사이의 문제를 해결하기 위한 프로그램 구현 방법으로 Translation(번역 기법)과 Interpretation(인터프리터 기법)이 존재한다.

* 컴퓨터 : 프로그램을 저장하여 실행할 수 있는 알고리즘과 자료의 총괄 집합이다.

4.2.1 번역 기법
- 고급 언어로 작성된 프로그램을 기계어로 번역하여 동등한 의미의 기계어 프로그램을 실행시키는 방법이다.

번역기 (Translator)
- Source Language(원시 언어) 프로그램을 입력받아 Object Language(Target, 목적 언어) 프로그램으로 출력하는 언어 처리기이다.
- 원시 언어와 목적 언어는 고급 언어가 될 수도 있고, 저급 언어가 될 수도 있다.
- 번역기의 종류는 크게 5가지로 구분된다.

1. compiler (컴파일러)
- Source = 고급 언어, Object = 저급 언어로 하는 번역기이다.
- 여기서 저급 언어는 준기계어 형태* 혹은 어셈블리어에 해당한다.

* 준기계어 형태 : Relocatable Form(재배치 형태)으로, 일반적으로 목적 코드를 의미한다.

2. Assembler (어셈블러)
- Source = 어셈블리어, Object = 준기계어 형태로 하는 번역기이다.
- 일반적으로, 어셈블러는 어셈블리 명령어 하나하나를 기계어 명령으로 단순 번역한다.

3. Linker (Linkage Editor, 링커, 링키지 에디터)
-  각각 컴파일 된 다수의 재배치 형태 기계어 프로그램(목적 모듈)들을 하나의 로드 모듈*로 만들어 어느 정도 실행 가능한 하나의 기계어로 번역한다.
- 시스템 프로그램의 일부이다.

* 로드 모듈 : 메모리에 로드만 되면 바로 실행될 수 있는 형태이다.

4. Loader (로더)
- 로드 모듈을  실행 가능한 기계어로 변환하여 메인 메모리에 Load(적재)한다.
- 로드 모듈이 메모리에 적재되기 직전에 각종 주소들이 확정되어 실행 가능해진다. 
- 로드 모듈이 메모리에 적재된 형태를 Executable(기계어)이라고 부른다.
- 일반적으로, run 명령어는 컴파일러부터 로더까지 수행되도록 지시한다.

5. Preprocessor (전처리기)
- Source, Object 모두 고급 언어로 하는 번역기이다. (보통, Source가 약간 더 고급 언어인 경향을 보인다.)
- 한 고급 언어 프로그램을 해당 컴퓨터에 구현된 고급 언어로 번역하여 이미 구현된 방식으로 실행한다.
- 출력된 언어(보다 더 고급 언어)를 해당 컴퓨터에 이미 구현된 언어(고급 언어)로 번역하기위해 사용하는 번역기이다.
- 즉, 고급 언어에 대한 확장을 구현하는 번역기이다.
ex) C의 확장형 언어 = C++, concurrent C
ex) Fortran의 확장형 언어 = RATFOR
ex) Fortran77, C의 확장형 언어 = C++, Object C

컴파일러 언어
- 고급 언어를 번역하여 Object Module(목적 모듈)을 출력시켜 그 목적 모듈을 링크, 로드하여 실행시키는 방법으로 구현하는 언어이다.
- 한 번 번역한 코드를 다시 실행시킬 때, 다시 번역할 필요가 없다.
- 기계어로 번역된 코드를 H/W 인터프리터가 Decode하여 실행하는 방식이다.
ex) Fortran, Algol, PL/I, Pascal, Cobol, C, C++, Ada 등

4.2.2 인터프리터 기법 (S/W 시뮬레이션 기법)
- 원시 코드로 입력된 프로그램을 번역과 동시에 직접 실행시킨다.
- 입력 프로그램의 논리적 순서에 따라 문장들을 처리하기 때문에 순환 부분 등은 계속 반복 처리해야한다.
- 고급 언어를 기계어로 취급하는 가상의 컴퓨터에서 프로그램을 시뮬레이션하는 방식으로 실행하는 방법이다.
- 이 가상 컴퓨터는 S/W적으로 시뮬레이션하여 구성되기 때문에 인터프리터 기법을 S/W 시뮬레이션 기법이라고 부르기도 한다.
- 번역기는 원시 코드를 목적 코드로 단순히 번역만 하는데 반해, 인터프리터는 목적 언어로의 변환과 동시에 프로그램을 실행시키는 역할까지 수행한다.

인터프리터 언어
- 고급 언어를 Intermediate Language(중간 단계 언어)로 번역하여 S/W 인터프리터가 곧바로 실행시키는 방법을 택한 언어이다.
- 컴파일러 언어보다 실행 시간 측면에서 비효율적이나, 사용자 적응성을 제공한다.
- 인기있는 인터프리터 언어의 경우, 컴파일러가 존재하는 경우도 있다.
ex) Lisp, Snobol 4, APL, Prolog, Python, Basic 등

4.2.3 인터프리터 기법과 번역 기법

※ 번역기는 Object Code를 생성하고 어셈블러가 순수히 번역만 수행하는 방식이며, 인터프리터는 직접 실행시키는 방식이다.

순수 번역 기법
- 원시 언어가 기계어에 가까운 언어일 때 주로 사용되는 기법이다.
- 실행 시간 측면에서 효율성을 제공한다.
- 반복처리되는 Loop, Subprogram을 실행할 때 유리하다.
- 한 에러만 발생되도, 전체를 다시 컴파일 해야하기 때문에 적응성이 떨어진다.
- 한 줄의 원시코드가 수 많은 Machine Code로 번역되는 경우에는 많은 메모리 공간을 필요로 하게 된다.
(번역된 프로그램이 큰 메모리 공간을 차지하게 될 수 있다.)
ex) I/O Format 명령문들은 입출력 형식 코드 이외에 기계 상태 파악 코드, 버퍼 등으로 인해 많은 메모리 공간을 요구한다. 이 경우, 라이브러리 루틴을 이용한 시뮬레이션 기법으로 처리하는 것이 유리하다.
ex) 컴파일러 언어 

순수 시뮬레이션 기법
- OS의 작업 제어 언어(JCL), APL과 같은 대화용 언어를 제외하고는 거의 사용되지 않는 기법이다.
- Flexibility(유연성) 구현에 유리한 기법이다.
- 번역 결과를 저장할 필요가 없어, 메모리 공간을 많이 차지하지 않는다.
- 프로그램 실행 중에 데이터의 동적 변화, 사용자와의 대화를 처리할 수 있다.
- 한 줄씩 번역/실행하기 때문에 적응성이 우수하지만, 실행속도가 느리다. (효율성과 거리가 멀다.)
- 프로그램의 전체를 파악하지 못하므로, 최적화 여부를 파악할 수 없다.

하이브리드 구현 기법
- 순수 번역 기법과 순수 시뮬레이션 기법을 절충하여 사용하는 기법이다.
- 대부분의 언어는 번역 기법과 시뮬레이션 기법을 함께 사용하여 컴퓨터에 구현된다.
- I/O 장치같은, 프로세서와 대비하여 처리 속도가 느린 작업을 처리할 땐, Library Code를 통해 Simulation하는 방식으로 처리한다.(Interpreter 방식)

※ 컴파일러 언어와 인터프리터 언어는 해당 언어를 구현하는 방법에 따라 구분되는 개념이다. 대표적인 컴파일러 언어인 Fortran도 인터프리터로 구현할 수 있으며, 전형적인 인터프리터 언어 Snobol4도 컴파일러로 구현시킬 수 있을 만큼 경계가 뚜렷하지는 않다.

ex) Basic은 간결성으로 인해 단말기에서 대화용 언어로 많이 사용된다. 이 경우 인터프리터로 프로그램을 실행하고, 여러 번 실행시키고자 한다면 컴파일하여 목적 모듈 혹은 로드 모듈로 만들어서 여러번 실행되기에 적합한 형태로 만든다. 이러한 특성으로 인해, 한 컴퓨터에 Basic 컴파일러와 Basic 인터프리터가 동시에 설치되는 경우가 잦다.

ex) Fortran, Algol, PL/I, Pascal, cobol, C, Ada : 컴파일러 언어 개념으로 설계되었지만, I/O와 같이 기계어와 동떨어진 부분은 Run Time Supprot Routine(실행 시간 보조 루틴) 등을 통해 시뮬레이션 기법으로 처리된다.

ex) Lisp, Snobol4, APL, Prolog : 기계어가 아닌 Intermediate Language(중간 언어)를 목적 코드로 하여, 프로그램을 번역하고, S/W 인터프리터로 실행시키는 방법으로 처리된다.

ex) Java에는 번역기가 Byte-Code라는 기계어 수준에 가까운 중간 언어로 번역하고, 이 Byte-Code를 S/W 인터프리터가 Decode하여 실행하는 방법을 채택했다.(컴퓨터 플랫폼마다 인터프리터가 상이하다.) Java 코드를 Byte-Code로 번역하기 때문에 Java 컴파일러라고 부르지만, 본질적으로 하이브리드 구현 기법을 채택한 형태이다.

---

Reference: 프로그래밍 언어 개념 (원유헌 저, 정익사, 2017)