컴파일러 필기

a = b + 5;는 a, b, 5, =, +, ; 로 분류된다. 총 6개의 어휘로 구성되며 a, b는 식별자이고 5는 상수, =,+는 연산자이고 ;는 구분자이다. 이렇게 어휘(token)으로 구분되는 것들이 정규 언어(regular language)다. 이렇게 나눠줄 수 있는 얘들을 어휘 분석기(인식기)라고 부른다. 쉽게 표현해서 finite automata(FA)는 인식기, (RG)정규문법 -> 어휘를 분석, 정규 표현(RE) -> 어휘를 표현하는 방법이다. *좋은 프로그래밍 언어의 요건

  1. 언어의 개념이 명료해야 한다. 문법적인 구조(Syntax)와 그에 따른 의미(semantic)가 일관성이 있으며 단순해야 한다.
  2. 프로그래머의 생각을 자연스럽게 표현할 수 있어야 한다.
  3. 프로그램의 호환성, 신뢰성, 모듈화, 효율성 등이 좋아야 한다.
  4. 언어의 확장성이 우수해야 한다.
  5. 좋은 프로그래밍 환경을 갖고 있어야 한다.

번역기란 한 프로그래밍 언어로 작성된 프로그램을 입력으로 받아 그와 동등한 의미를 갖는 다른 프로그래밍 언어로 된 프로그램을 출력하여 주는 시스템 프로그램을 말한다. 이 때 입력되는 프로그램을 ‘소스 프로그램’이라 하고 이 프로그램을 기술한 언어를 ‘소스 언어’라고 한다. 그리고 출력되는 프로그램을 ‘목적 프로그램’이라 하고 이 프로그램을 기술한 언어를 ‘목적 언어’라 한다.

만약 소스 언어가 C언어와 같은 고급 언어이고 목적 언어가 어셈블리어나 기계어일 경우, 번역기를 컴파일러라고 한다. 즉, 고급 언어를 저급 언어로 바꿔주는 것.

컴파일러의 일반적인 구조 컴파일러는 고급 언어로 쓰여진 프로그램을 어떤 특정한 컴퓨터에서 직접 실행 가능한 형태의 프로그램으로 번역해주는 컴퓨터 프로그램이다. 컴파일러는 크게 5단계로 나누어진다. 처음 3단계가 전단부(Frontend)이고 뒤 2단계가 후단부(backend)이다.

어휘 분석기(token) -> 구문 분석기(tree) -> 중간 코드 생성(여기까지가 전단부) -> 코드 최적화 -> 목적 코드 생성

이렇게 5단계다. 말 그대로 해석하면 된다.

  1. 어휘 분석기(Lexical Analyer)는 문법적으로 의미가 있는 최소 단위로 나눈다는 것이니 변수, 연산자, 상수, 구분자 이렇게 나누면 된다. 가령 a = b + 5 ; 라고 하면 하나하나 나눠서 output인 token은 총 6개다. Scanner라고 생각하자. 문장을 간단히 훓어본 거라고. 구문이 어떻게 짜여질지 보는 거다. 그리고 다음의 효율적인 처리를 위해서 고유의 내부번호(token number)를 정수 형태로 갖는다. 당연하게도 output인 token들은 다음 단계인 구문 분석기의 input이 된다.

  2. 구문 분석기(Syntax Analyer)는 parser라고도 하는데 얘네들은 전 단계에서 토큰을 받아 소스 프로그램에 대한 에러를 체크하고 올바른 문장에 대해서 구문 구조를 만든다. 참고로 의미 체크는 안 한다. 에러가 나면 에러 메세지를 출력하고 올바른 문장이면 프로그램 구조의 tree를 출력한다. 즉, output이 tree이다.

  3. 중간 코드 생성(intermediate code generation)에서는 전 단계의 tree를 입력으로 받아서 의미 검사를 하고 그에 해당하는 중간 코드를 생성한다. 여기서 의미 검사란 자료형 검사같은 일들을 말하는데 int a; a=10;이라면 자료형이 int니까 a에 정수가 들어갔나 안 들어갔나 확인하는 것이다. 중간 코드 생성이라하면 자바에서 .class를 만드는 거라고 생각하면 쉽다.

  4. 코드 최적화(code optimization)는 전 단계의 중간 코드를 입력으로 받는다. 이 과정은 여러 단계에서 사용되기 때문에 없어도 된다. 마치 자동차에 옵션을 다는 격이다. 자동차에 옵션을 달면 성능이 좋아지듯이, 코드 최적화를 하면 성능이 좋아진다. 즉, 코드의 사이즈를 줄이거나, 실행 시간을 개선시켜서 효율을 높이는 것이다. (메모리에 불러오는 구문을 두 번 썼다든지… 그런 일들) 당연히 코드의 의미는 유지되면서 최적화를 해야된다.

최적화에서는 범위를 정하는데 local과 global이 있다. local은 basic block단위이고 global은 흐름 분석 기술이란 걸 이용해서 basic block 사이에 최적화를 하는 것이다.

local에서 예를 들자면 c = a + a; 와 c = 2 * a; 둘 중에 누가 효율적인 코드일까? 당연하게도 c = a + a;이다. 곱셈보다는 덧셈이 연산 강도가 낮으니까. 이런 식이다. 참고로 a * 5;와 5 * a;는 5 * a;다.

  1. 목적 코드 생성기(target code generator)는 최적화된 중간 코드를 입력으로 받아 그와 의미적으로 동등한 목적 기계에 대한 코드를 생성하는 일을 한다. 목적 코드를 생성하기 위해서 크게 4가지 과정을 거치는데 목적 코드 선택 및 생성, 레지스터의 운영, 기억 장소 할당, 기계 의존적인 코드 최적화이다. 레지스터와 가까워야 함은 당연하고 기계로 들어가는 마지막 부분이니 기계에 맞는 코드 최적화도 당연한 일이다. 효율적인 면에서는 많은 알고리즘이 개발되었다고 하니 굳이 걱정할 필요는 없겠다.

  2. 끝난 줄 알았겠지만 아니다. 처음에 hello world를 쳤을 때 오류가 떴던 것처럼 컴파일러는 에러를 발견해서 사용자에게 알려줘야된다. 오류를 Recovery하는 컴파일러가 있고, Repair하는 컴파일러가 있는데 말 그대로다. error recovery는 다른 문장에 영향을 미치지 않도록 수정하는 것이고 error repair는 error가 발생하면 복구해주는 것이다. error handling도 있는데 C는 없고 C#, JAVA, C++는 있다. 말 그대로 에러를 다룰 수 있는 try catch를 말한다.

컴파일러 자동화 도구

세월이 지나면서 프로그래밍 언어와 컴퓨터 구조가 다양해짐에 따라 많은 컴파일러가 필요하게 되었다. 프로그래밍 언어가 N개고 컴퓨터가 M개 있으면 컴파일러는 N*M개가 있어야 된다. 귀찮은 개발자들은 컴파일러의 각 단계를 자동적으로 생성하는 도구들에 대한 연구를 했다.

이러한 도구들을 총칭해서 컴파일러 생성기(Complier generator)라고 부른다. 프로그래밍 언어를 위한 언어 명세서(language description)와 목적 기계에 대한 기계 명세서(machine description)을 입력으로 받아 하나의 컴파일러를 출력한다.

  1. 어휘 분석 생성기 -> 토큰을 받아서 토큰을 구분해내는 일을 한다. 토큰 표현 방법에는 regular expression을 사용한다. 대표적인 예는 Lex라는 생성기이다.

  2. 파서 생성기 -> 파서 생성기(parser generator)란 언어의 문법 표현으로부터 구문 분석기(parser)를 자동으로 생성하는 도구를 말한다. 언어의 문법 표현으로부터 파서 생성기는 파서를 제어하는 테이블을 생성하고 문법적인 검사를 하며 다음 단계에서 필요한 의미 정보를 만든다. 모든 언어에 대하여 파서 부분은 동일하고 테이블만 다르다. 그러므로, 새로운 언어에 대한 파서를 만들기 위해서는 단지 문법 표현만 바꾸면 된다. 대표적인 예는 YACC이 있다.

  3. 코드 생성의 자동화 -> 중간 언어를 목적 기계 언어로 바꾸는 컴파일러 과정으로 기계 정형화를 통하여 자동적으로 구성하려 한다. 기계 명세서로부터 자동적으로 유도하는 것을 말한다.

  4. 컴파일러 컴파일러 시스템 -> 세분화된 각 단계를 통합하는 과정이다. 대표적인 예로 PQCC와 ACK가 있는데 PQCC는 전단부가 괜찮지만 후반부가 미미하다. ACK는 컴파일러의 후단부를 자동화하기 위한 도구다.

자동화는 매력적이다. 2.1 언어

  1. 알파벳(alphabet) : 문장을 이루는 기본적인 심벌(글자) ex) T1 = {ㄱ,ㄴ,ㄷ,…,ㅎ,ㅏ,ㅑ, …,ㅡ,ㅣ} T2 = {A,B,C, …,Z} T3 = {auto, break, case, …, while} T는 심벌들의 유한집합이다.

  2. T에 대한 String : 알파벳 T에 속하는 심벌이나 T에 속하는 하나 이상의 심벌들을 나열한 것이다. ex) T1 = {0} -> T1에 대한 스트링 = 0, 00, 000, 0000 … T2 = {a,b} -> T2에 대한 스트링 = a, b, ab, ba, bb, aaa …

  3. String의 length : 스트링을 이루는 심벌들의 개수. w 로 표기한다.        
    ex) w = a1a2a3a4a5…ak 이면, w = k이다.        
    스트링의 접속은 스트링끼리 연속으로 연결한 것이다. u=a1a2a3, v=b1b2b3 일 때, uv = a1a2a3b1b2b3가 된다. 물론 개수는 당연히 나눠질 수 있다. 그냥 더하기니까. uv = u + v 다.
  4. String의 length가 0인 것을 empty String이라 하며 ε(epsilon)으로 표기하고, 어떤 스트링 u, v에 대하여 uε = u = εu거나 uεv = uv다. 항등원과 같은 역할이며 |ε| = 0이다. a^n = aaaaa…(n개), a^0 = ε이다. 즉, 지수가 연결된 알파벳 수를 표시한다. w^R은 스트링의 역순이다. ex) w=a1a2a3 이면, w^R=a3a2a1이다.
  5. T^(티 스타 - T star)는 empty 스트링을 포함하여 T로부터 만들 수 있는 모든 스트링의 집합이다. 또한 T^+(티 대거 - T dagger)는 T^에서 empty 스트링을 제외한 스트링의 집합이다. Ex) T = {0} 일 때, T^* = { ε, 0, 00, 000, …}이고 T^+ = { 0, 00, 000, …} 가 된다. 알파벳 T는 항상 유한 집합이며 그에 해당하는 T^는 항상 무한 집합이 된다. 즉, ∀u,v∈T, uv∈T가 된다. 결국 T^눈 알파벳 T에 속하는 심벌로부터 만들 수 있는 스트리의 전체 집합을 의미한다.
  6. 알파벳 T에 대하여 언어 L은 T^의 부분 집합이다. L⊆T 이다. T^*에 속하는 스트링 중에 특정한 형태만을 모아 놓은 집합이 언어라고 생각할 수 있다. 언에 속하는 스트링의 수가 유한 개일 때 유한 언어라 하며, 무한 개일 때 무한 언어라 한다. 그래서 언어라고 한다면 맞지만 유한 언어인지 무한 언어인지는 구분된다.

몇 가지 정의들 두 언어 L과 L’의 곱(product) LL’은 L에 속하는 스트링과 L’에 속하는 스트링을 접속한 것으로 간단히 LL’로 나타낸다. LL’ = {uv | u∈L 그리고 v∈L’ } L0={ε}, L^n=LL^n-1 for n≥1. L^ = L^0∪L^1∪L^2∪…∪L^n∪… L^+ = L^1∪L^2∪…∪L^n∪… = L^* - L^0

각 언어마다 고유의 알파벳 T가 존재하며 T로부터 만들 수 있는 스트링 전체의 집합이 T^*이며, 어떤 규칙에 맞는 특정한 형태의 스트링을 모아 놓은 집합이 언어로 정의된다. 일반적으로 한 언어에 속하는 스트링을 그 언어의 문장(Sentence)라 부른다.

2.2 문법 언어를 어떻게 표현할까? 유한 언어는 그냥 모든 스트링을 열거하면 되지만 무한 언어는 그 언어의 유한 표현을 찾아야 한다. 이와 같은 무한 언어의 유한 표현으로는 조건 제시법, 문법, 인식기 등이 있다. 여기서는 문법을 다룬다.

언어를 정의하기 위한 문법은 심벌의 분리된 두 집합, Vn으로 표시되는 nonterminal 심벌과 Vt로 표시되는 terminal 심벌의 집합을 사용한다. terminal 심벌은 정의된 언어의 알파벳이고, nonterminal 심벌은 문법에서 스트링을 생성하는데 사용되는 중간 과정의 심벌로 언어의 구조를 정의하는데 사용된다. terminal 심벌과 nonterminal 심벌을 합해서 문법 심벌(grammar symbol)이라 하며 보통 V(vocabulary)로 나타낸다.

문법은 다음과 같이 네 가지 요소로 정의된다. G = (Vn, Vt, P, S) Vn : nonterminal 심벌의 유한 집합 Vt : terminal 심벌의 유한 집합 Vn ∩ Vt = ∅ , Vn∪ Vt = V P : 생성 규칙(production rule)의 유한 집합 α → β, α∈ V+, β∈ V* //여기서 α를 left hand side, β를 right hand side라 부른다. →는 단순히 대치를 뜻한다. S : Vn에 속하는 심벌로서 다른 nonterminal들과 구별하여 시작 심벌(start symbol) 혹은 문장 심벌(sentence symbol)이라 한다.

각 생성 규칙 α → β는 α 구조를 β구조로 정의한다는 것이며 유도 과정에서 α가 나타날 때마다 β로 대치할 수 있다는 의미이다.

Ex) G = ( {S, A}, {a, b}, P, S ) //여기서 nonterminal 집합은 {S, A}이고, terminal 집합은 {a, b}이며, 시작 심벌은 S, 생성규칙(P)의 개수는 5개다. P : S → Aas S → a //P는 생성규칙이고 S가 a로 대치될 수 있다는 뜻이다.
A → SbA A → ba A → SS

⇒S → aAS a // 는 or의 뜻이고 위와 완전 동일하다.
A → SbA ba SS

⇒는 ‘직접 유도된다’고 말하며 한 스트링에서 생성 규칙을 한 번 적용해서 다른 스트링으로 바뀌는 것을 나타낸다. S⇒Aas⇒SbAas 처럼 계속 유도시킬 수 있다.

문장 형태중 nonterminal 심벌을 포함하지 않은 것이 문장이다. 유도 과정중에 있는 S, Aa, abS, abbB 등 은 모두 문장 형태이다. 이 중 모든 심벌이 terminal로만 구성된 abba는 문장이다. 문법 G에 의해 생성되는 언어는 G에 의해 생성되는 문장의 집합이며 L(G)로 표기한다. w에 S, A가 포함되어있으면 문장형이다. (Sentential form - 문장형)

Ex) G = ({S}, {a}, P, S) P : S -> a | aS라면 계속 하다보면 a, aa, aaa… 가 나오는 것을 알 수 있다. L(G) = {a^n | n >= 1} 문법 ->(생성) 언어, 언어 ->(고안) 문법.

문법으로부터 생성되는 언어를 찾는 과정은 일정한 규칙이 없기 때문에 반복적인 연습이 필요하다. 일반적으로 시작 심벌로부터 문장의 길이 순으로 문장을 생성한다.

일반적으로 반복되는 부분은 생성규칙을 순환적으로 작성함으로써 가능하다. a^n을 생성하는 규칙의 형태는 A -> Aa가 된다. a^n | n >= 0의 형태를 생성하는 문법은 A -> aA | ε이고 (입실론이기 때문에 0부터.) a^n | n >= 1의 형태를 생성하는 문법은 A -> aA | a

a^nb^n n >= 1의 형태를 생성하는 문법은 S-> aSb ab 이다. 이게 바로 embedded 생성 규칙이다. 안에 넣으니까.

주어진 문법으로부터 생성되는 언어는 유일하지만 주어진 언어를 생성하는 문법은 다양한 형태가 될 수 있다. 즉, 한 언어를 생성하는 문법은 문법 고안자에 따라 달라질 수 있다. 예를 들어, a^n을 생성하는 생성 규칙의 형태는 A -> aA(right - recursive) 또는 A -> Aa(left - recursive)가 될 수 있다. 즉, 문법이 두 개다.

일반적으로, 문법 G가 어떤 언어 L을 생성한다는 것을 증명하기 위해서는 반드시 L(G) = L임을 보여야 한다.

2.3 문법의 분류

type 0 문법(unrestricted grammar, ug) : 생성 규칙 a -> b에서 a는 empty 스트링이 될 수 없다.

type 1 문법(context - sensitive grammar, csg) : 생성 규칙 a -> b에서 b의 길이가 a의 길이보다 길다.

type 2 문법(context-free grammar, cfg) : 모든 생성 규칙은 A -> a의 형태를 갖는다. 생성 규칙의 좌측은 nonterminal이며(길이가 1이어야 함.) 우측은 terminal과 nonterminal로 이루어진 스트링이다.

type 3 문법(regular grammar, rg) : 정규 문법(regular grammar)의 생성 규칙은 두 가지 행태로 표현될 수 있는데 A -> tB형태, 우선형이거나 A ->Bt형태, 좌선형이거나다. 왼쪽 오른쪽 intermixed되면 안 된다. 왼쪽이면 다 왼쪽, 오른쪽이면 다 오른쪽 이렇게 되야한다. 섞여있으면 not regular다.

정규 언어란 정규 문법에 의해 생성될 수 있는 언어를 말한다. context-free 언어란 context-free 문법에 의해 생성될 수 있는 언어를 말한다.

정규 문법은 context-free 문법의 형태를 만족한다. 따라서, 모든 정규 언어는 또한 context-free 언어가 될 수 있다. 그래서 포함 형태는 정규언어 < context-free 언어 < context-sensitive 언어 < recursively enumerable 언어가 된다.

언어 표현의 다른 방법으로 인식기(recognizer)가 있는데 인식기에 의해 정의되는 언어는 이 인식기가 받아들이는(accept) 스트링의 집합이다.

  1. 정규언어

3.1 정규 문법과 정규언어

정규 언어(regular language)는 토큰의 형태를 기술하는데 사용하며 이를 표현하는 방법으로는 정규 문법(regular grammar), 정규 표현(regular expression), 그리고 유한 오토마타(finite automata)가 있다.

정규 문법의 형태는 생성 규칙의 nonterminal의 위치에 따라 우선형 문법(RLG-대문자가 오른쪽)과 좌선형 문법(LLG-대문자가 왼쪽)으로 구분된다. RLG : A → tB, A → t LLG : A → Bt, A → t where, A,B ∈ Vn and t ∈ Vt*.

모든 RLG는 그와 동등한 LLG로 만들 수 있으며 마찬가지로 LLG도 RLG로 만들 수 있다. 그래서 RLG와 LLG가 나타낼 수 있는 언어의 종류가 같다는 의미이며 그 언어를 정규 언어라 부른다. 그러나 한 문법의 생성 규칙이 우선형과 좌선형이 혼합되어 있으면 정규 문법이 아니다. G : S → aR S → c R → Sb L(G) = {a^ncb^nn | n ≥ 0} 위처럼 된다면 L(G)는 nonterminal과 terminal로 이루어져 있으므로 CFL(Context free language)가 됩니다.

우선형 문법을 그에 따른 정규 문법 형태로 변환할 수 있다. A -> a1A1, A1 -> a2A2, A2 -> a3A3 이런 식으로 늘려 나갈 수 있다. 우선형 문법에서 t = ε인 경우, 생성 규칙의 형태가 A -> B 또는 A -> ε의 형태가 된다. 전자를 단일 생성 규칙이라 부르고 후자를 ε생성 규칙이라 부른다.

이러한 형태로 다음은 모두 동등한 의미를 갖는다. 언어 L은 우선형 문법에 의해 생성된다. 언어 L은 좌선형 문법에 의해 생성된다. 언어 L은 정규 문법에 의해 생성된다.

어떤 언어(L)가 정규 언어냐고 물었을 때 L을 생성하는 정규 문법이 존재하면 정규 언어라고 할 수 있다.

정규 문법은 컴파일러의 어휘 분석 단계에서 입력 프로그램을 구성하고 있는 토큰의 구조를 정의하는데 사용된다.

주어진 문법 G로부터 언어 L(G)를 찾는 일은 일반적으로 쉬운 일이 아니나, G가 정규 문법이라면 다행히도 대수학적인 성질을 갖는 정규 표현식으로 바꾸어 이것으로부터 언어의 표현을 체계적으로 구할 수 있다.

3.2 정규 표현

정규 표현(regular expression)은 정규 언어를 표현하기 위한 한 방법으로 정규 언어에 속해 있는 스트링의 모양을 직접 기술하는 형태를 갖는다.

정규 표현은 다음과 같이 정의된다. 정규 표현의 기본 소자는 Ф(공집합), ε(집합 ε), 그리고 terminal 심벌(그냥 터미널들)이다. 만일 e1과 e2가 정규 언어 L1과 L2를 나타내는 정규 표현이라면, e1 + e2는 L1∪L2(union)를 나타내고 e1’(그냥 점이다)e2은 L1’L2(concatenation)를 나타낸다. 그리고 (e1)은 L1(L1, L2, L3…의 합집합, closure)을 나타낸다. 이렇게 위에 정의된 것 이외에는 어떠한 것도 정규 표현이 될 수 없다.

정규 표현이 나타내는 스트링의 형태가 몇 가지 있다. ab* = abbbbb…을 나타낸다. (0+1)은 언어 {0, 1}을 나타낸다. 즉, ε을 포함하여 0과 1로 이루어지는 모든 스트링을 의미한다. 정규 표현 (0+1)00은 0과 1로 이루어진 스트링 뒤에 00이 나오는 형태의 스트링으로 구성된 언어를 표현한다. ex) L(a(a+b)) = {ε, a, aa, aaa, …}{a,b} = {a, aa, aaa, …, b, ab, aab} 가 된다.

두 개의 정규 표현이 같은 언어를 표현할 때 그 정규 표현은 같다고 말한다. ex) a(ba)이면 ababababa..이므로 (ab)a도 abababa…라서 같은 형태를 표현한다.

정규 표현식은 다음과 같은 대수학적인 성질을 만족한다.

A10번에서 a-ε = a’a이므로 aa*=a+가 된다.

X = aX + b에서 X = ab를 대입함으로써 ab가 해 임을 쉽게 알 수 있다. X = aX + b = a = aab + b = a+b + b= b(a+ + ε) = ab가 된다.

이제 주어진 정규 문법 G가 생성하는 언어 L(G)를 나타내는 정규 표현을 구하는 과정을 살펴보자. 즉, 정규 문법을 정규 표현으로 변환하는 방법이다.

정규 문법으로부터  일련의 정규 표현식을 구성한다. X -> a | b | r이면 a + b + r 로 변환한다.
구성된 정규 표현식 중에서 X = aX + b 형태의 식은 X = a*b로 푼다. 
시작 심벌에 대한 정규 표현식을 X = aX + b의 형태로 고친 후 식을 X = a*b로 또 고치면 정규 언어가 된다.  ex) S = (a + ba)S + ε = (a+ab)*가 된다. //이거 만들 때 곱하는 거랑 *랑 절대 헷갈리면 안 된다. b^2이 아니고 bb다. 정말 그대로 해주기만 하면 된다.

문법이 주어졌을 때, 대부분의 경우 그 문법이 생성하는 언어를 구하는 것은 쉬운 일이 아니다. 그러나, 주어진 문법이 정규 문법일 경우, 그 문법이 생성하는 언어를 구하는 체계적인 방법이 존재한다. 즉, 정규 문법으로 부터 일련의 정규 표현식을 유도하고 해를 구함으로써 가능하였다. 결론적으로 정규 문법과 정규 표현은 같은 종류의 언어를 나타낸다.

3.3 유한 오토마타(Finite Automata - 인식기) - 가장 중요하다!

일반적으로 언어에 대한 인식기(recognizer)는 입력으로 스트링을 받아 스트링이 그 언어의 문장이면 “yes”를 답하고 그렇지 않으면 “no”를 답하는 기능을 수행한다. 이와 같은 인식기 중에 가장 간단한 형태가 유한 오토마타(FA : Finite Automata)이며 어휘 분석기를 고안하고 구현하는 방법에 사용된다.

FA는 5개의 요소로 정의된다.

Q : 상태들의 유한 집합
Σ : 입력 심벌의 유한 집합
δ : 사상 함수
q0 : 시작 상태(q0 ∈ Q)
F : 종결 상태의 집합을 의미한다.

여기서 사상 함수의 형태는 δ(q, a) = {p1, p2, p3…}이다. 이것은 q상태에서 입력 a를 본 다음 상태는 p1부터 pn중에 하나를 선택할 수 있다는 의미를 갖는다. 이와같이 사상함수는 입력 심벌을 보고 다른 상태로 이동하는 것을 나타낸다. 그 형태에 따라 결정적 유한 오토마타(DFA : Deremininistic FA)와 비결정적 유한 오토마타(NFA : Nondeterministic FA)로 나누어진다.

결정적 유한 오토마타(DFA : Deremininistic FA) FA의 전이 함수 δ(q, a)가 한 상태만을 갖는 경우에 DFA라고 부른다. 즉, DFA의 다음 상태는 항상 하나이다. δ(q, a) = p의 의미는 q 상태에서 입력 심벌 a를 본 다음 상태는 p가 된다는 것이다.

간단하게 나타내주기 위해서 FA의 전이 함수를 매트릭스 형태로 간단히 나타낼 수도 있다. 스트링이 나타날 수도 있다. 그럴 때는 확장시켜주면 된다. δ(q, aba) = δ(δ(q, ab), a)이런 식으로. 그리고 나서 차근차근히 대입시켜주면 된다.

만약 δ(q, a) = p인 경우에 q으로부터 x를 다 본 상태가 p가 되며 p가 종결 상태에 속하면 ‘스트링 x는 유한 오토마타에 의해 인식된다’고 한다.

가령, 유한 오토마타 M(Machine) = ( {p, q, r}, {0, 1}, δ, p, {r} )이 있고 1001 ∈L(M) 이냐? 이렇게 물어본다면 차근차근 대입해보면 된다.

δ(p,1001) = δ(p,001) = δ(q,01) = δ(r,1) = r ∈F 위 처럼 r이 F에 속하므로 인식된다.

상태 전이도 : 상태 전이도는 유한 오토마타의 각 상태를 노드로 나타내고, 전이 함수 δ(q, a) = p에 대해서 상태 q에서 p로 가고 레이블이 a인 지시선으로 나타낸다. 또한 종결 상태들은 이중 원으로 표시하고 시작 상태는 start 지시선으로 표시한다. 즉, 쉽게 표현하기 위해 그림으로 그린 것이다.

이런 식으로 그릴 수 있다. 그리는 방법을 알아보자. 상태들을 노드로 만든다. start 지시선을 그린다. 종결상태는 이중 원으로 그린다. 전이 함수에 따라 화살표로 표기되는 레이블이 있는 지시선을 그린다.

비결정적 유한 오토마타(NonDeremininistic FA) NFA는 다음 상태가 여러 개가 될 수 있다. 여러 가지 가능성을 고려해야하기 때문에 비 결정적이다. 그리고 다음 상태가 비결정적일 수 있다. 그리고 δ(q, a) = Ф인 경우에 undefined라고 하며 q상탱서 a라는 입력 심벌이 나올 수 없다는 것을 의미한다.

δ(q, xa) = ∪ δ(p, a)… q상태에서 스트링 xa를 본다는 것은 x를 다 본 각각의 상태에서 a를 본 상태들의 합집합과 같다는 걸 의미한다.

1011 ∈L(M) ?

δ(q0, 1011) = δ({q1,q3}, 011) = δ({q1,q2},11) = δ({q1,q3},1) = {q1,q3,qf} //공집합이면 없는 셈 치면 된다.

∴1011 ∈L(M) ( ∵{q1,q3,qf} ∩{qf} ≠Φ) 종결 상태가 하나라도 속해 있으면 그 스트링은 NFA에 의해 인식된다고 말한다.

NFA에서 DFA로의 변환 일반적으로 NFA는 언어의 구조를 쉽게 표현할 수 있는 반면에 DFA보다 프로그램으로 구현하기가 어렵다. DFA는 구현하기가 쉽고. 그래서 NFA를 DFA로 변환할 수 있는 방법을 만들어냈다.

DFA의 상태 집합은 공집합을 제외한 NFA의 상태 집합의 부분 집합으로 구성되며 입력 심벌의 집합은 모두 같다. 그리고 DFA의 시작 상태는 NFA의 시작 상태와 같으며 DFA의 종결 상태의 집합은 NFA의 종결 상태를 적어도 하나를 포함하는 상태들로 구성된다. 마지막으로, DFA의 전이 함수는 NFA의 전이 함수로부터 계산하게 된다.

위 사진을 NFA에서 DFA로 바꾸어보면 Q : q0, q1, {q0, q1} //2^Q라고 말하는데 Q의 부분집합을 말한다. Σ : {0,1} (입력 심벌의 집합은 모두 같다.) δ : 사상 함수 이건 직접 해봐야 된다. 하나하나 다 해보자. q0 : q0 (시작 상태도 같다.) F : q1(종결상태)을 포함하는 집합이니까 q1, {q0, q1}이 된다.

사상함수를 구해보자

위의 과정을 거쳐서 [q0] = A, [q1] = B, [q0,q1] = C로 변환시키면

이런 결과를 얻을 수 있다. 얘네도 그림을 그릴 수 있는데 B상태와 같이 나가는 지시선만 갖는 상태는 제거할 수 있다. 왜냐면 B는 시작 상태에서 도달할 수 없는 상태이기 때문에 문장을 인식하는데는 아무 필요가 없기 때문이다. 즉, start가 A에서 시작하는데 B로 갈 수 없기 때문이다.

ε - NFA에서 DFA로의 변환 ε 전이란 ε를 보고 한 상태에서 다음 상태로 이동하는 것을 의미하며 ε을 레이블로 갖는 지시선으로 표시한다. ε전이를 갖는 NFA를 ε-NFA라 부르며 전이 함수를 제외한 모든 정의는 NFA와 같다. 입력으로 ε이 올 수 있으며, ε을 보고 한 상태로부터 다음 상태로의 이동이 가능한 NFA이다. ε-NFA를 DFA로 바꾸기 위해서는 한 상태에서 ε을 보고 갈 수 있는 상태들을 모두 구하는 작업이 필요하다. 이러하나 작업은 ε-CLOSURE라 한다. ε-NFA에서 ε-CLOSURE의 정의는 다음과 같다. S가 한 개의 상태인 경우, ε-CLOSURE(S)는 S와 S로부터 레이블이 ε인 지시선으로 도달할 수 있는 모든 상태들을 포함한다. //그냥 가는 걸 다 해주면 되는듯?하다. T가 하나 이상의 상태 집합으로 된 경우, ε-CLOSURE(T)는 T속의 각 상태에 대해 과정 1과 같은 방법으로 상태들을 구하여 합집합한 것이다.

DFA의 상태수 최소화(state minimiztion -> Minimization of FA) DFA의 상태수 최소화는 DFA를 이용하는 어휘 분석기의 상태 전이표의 크기를 줄임으로써 기억 공간을 적게 차지하도록 하고 또한 어휘 분석 프로그램을 간단히 하는데 큰 도움을 준다. 상태수를 최소화하는 방법은 동치 관계를 이용하여 상태들을 합침(state merge)으로써 상태수를 최소화하는 것이다. 최소화의 정의 ω ∈ Σ* 에 대해 만약 q1에서 ω를 다 본 상태가 q3이고 q2에서 ω를 다 본 상태가 q4일 때, q3, q4중 하나만 종결 상태에 속하면 ‘q1은 q2로부터 구별된다’고 말한다. 구별되지 않는 상태들을 하나의 상태로 합치는 방법 초기의 동치 관계를 구성한다. 즉, 전체 상태를 종결 상태와 미종결 상태의 두 동치류로 분할한다. 같은 입력 심벌에 대해 서로 다른 동치류로 가는 지시선이 존재하면, 또 다른 분할을 하여 새로운 동치류를 만든다. 이를 그 입력에 의해 구별된다고 한다. 2번 과정을 반복하여 더 이상 분할이 일어나지 않을 때, DFA M’ 를 구성한다. 상태수를 최소화한다. -> 상태가 합병된다. 즉, q0, q1 … qn까지 있었는데 최소화를 해서 유도하다보니 q0, q1, … ,q(n-k)가 된다. 합칠 수 있냐 없냐의 기준은 구별된다 아니다의 기준이다. 구별되면 합칠 수 없다.

정규 언어의 속성
정규 문법과 유한 오토마타 주어진 정규 문법에 대해서 동등한 언어를 인식하는 유한 오토마타를 구성하는 방법은 유한 오토마타의 각 요소들을 대응되는 문법의 요소를 이용하여 정의해주는 것이다. 유한 오토마타의 상태 집합은 nonterminal 심벌의 집합에다 새로운 종결 상태를 더한 것이 된다. 문법의 nonterminal 심벌 집합에는 종결 상태에 해당하는 것이 없으므로 새로운 종결 상태를 하나 도입하게 된다.  Given rg, G = (VN, VT, P, S) , construct M = (Q, Σ, δ, q0, F). (1) Q = VN U {f}, where f is a new final state. //종결상태가 추가된다.  (2) Σ = VT. (3) q0 = S. 그대로 (4) F = {f} if ε ∉ L(G) = {S, f} otherwise. (5) δ : if A → aB ∈ P then δ(A,a) ∋ B. if A → a ∈ P then δ(A,a) ∋ f.

DFA를 정규 문법으로 바꿀 때는 다 그래도 써주면 되는데 여기에서 종결상태에 생성규칙 r -> ε을 꼭 추가해줘야 한다. 정규 표현으로 갈 때도 마찬가지

유한 오토마타에서 정규표현으로 갈 때도 마찬가지로 문법에서 더하고 계산해주면 된다.

  1. 어휘분석 4.1 서론 어휘분석이란 소스 프로그램을 하나의 긴 문자열로 보고 차례대로 문자를 검조하여 문법적으로 의미있는 최소의 단위로 분할해 내는 것을 말한다. 여기서 문법적인 최소의 단위로 token이라고 부른다. 이러한 작업은 컴파일러의 어휘 분석기(간단히 scanner)에서 처리한다. 토큰은 유한 오토마타에 의해 인식될 수 있으며, 토큰의 구조는 프로그래밍 언어 설계자나 컴파일러 구현자에 의해 결정되는데 대개의 프로그래밍 언어는 다음과 같은 종류의 토큰을 갖는다. 특수 형태의 토큰 -> 언어 설계자 지정어 : const, if, else, int 등 연산자 기호 : +, -, * 등 구분자 : ;, ,등 일반 형태의 토큰 -> 컴파일러 설계자 명칭 : stk, ptr, sum1 등 상수 : 255, 2.55 등 Token : if ( a > 10 ) Token Number : 32 7 4 25 5 8
    Token Value : 0 0 ‘a’ 0 10 0 토큰 번호는 토큰을 대표하는 정수 번호이다. 효율성을 위해서 존재한다. Mini C에서 정의한 고유 번호로 C언어의 열거형으로 정의되어 있다. 토큰 값은 스트링 값이나 수치 값이다. 특수형태의 토큰은 토큰 값을 갖지 않는다. 토큰 a와 b는 토큰 번호가 4로 똑같지만 토큰 값으로 구별된다. 그리고 특수형태의 토큰은 토큰 값을 갖지 않지만 편의상 0으로 표시했다. 어휘 분석기가 구문 분석기에게 넘겨 주는 토큰의 정보는 일반적으로 토큰 번호와 토큰 값의 순서쌍으로 구성된다. 예를 들어, 입력 : a = b + 3 ; 순서쌍 : (4, a), (23, 0), (4, b), (11, 0), (5, 3), (20, 0) 의 식이다. 프로그래머가 사용한 명칭에 대한 토큰은 토큰 값은 물론이고 그 속성을 나타내는 정보를 심벌 테이블에 보관한다. 새로운 명칭의 토큰을 인식하면 심벌 테이블에 명칭을 삽입하고 구문 분석기에는 명칭에 대한 토큰 값으로 스트링 값이 아닌 심벌 테이블의 index를 전달한다. 이렇게 구문 분석기가 심벌 테이블을 검색하는데 드는 시간을 경감시켜 줄 수 있다. 이 이외에도 어휘 분석기는 소스 프로그램의 줄 번호를 기억하여 필요할 때 소스 프로그램을 줄 별로 출력할 수 있게 해주며, 소스 프로그램의 불필요한 공백과 주석을 처리하는 일을 한다.

4.2 토큰 인식 Characters(alphabet, 특수문자, 숫자) -> words -> 어휘s(Regular Grammar, FA) -> 문장s(Pushdown automata) -> P/G 토큰의 구조는 RE로 구현되고 다이어그램(상태 전이도)로 디자인된다.

문자의 분류 letter : a | b | c… | z | A | B | C |…| Z //편의상 l로 표현한다. digit : 0 | 1 | 2… | 9 //편의상 d로 나타낸다. special character : + | - | * | / | . | , | … //얘네들은 terminal symbol로 표현한다.

명칭(변수)의 인식 일반적으로 C언어에서 명칭의 구조는 먼저 문자나 _가 나오고 그 다음에 문자나 숫자 또는 _가 반복되는 형태이다. 명칭의 길이에 관계없이 인식한다. RG. RE. FA에게는 상호 변환이 가능하다. 동치 관계에 있다. 명칭의 상태전이도 이다.

RG : S -> lA | _A A -> lA | dA | _A | ε RE : S = lA + _A = (l + _)A A = lA + dA + _A + ε = (l + d + _)A + ε = (l + d + _)* ∴S = (l + _)( l + d + _)* 예를 들어, a나 a35, a_34 모두 명칭으로 인식된다. if(a>b);에서 a도 이렇게 명칭으로 인식된다. 이 식은 C언어에서 명칭의 일반적인 구조와 일치한다.

정수 상수의 인식 정수를 생각해보자. 정수에도 여러 가지 표현 방식이 있는데 바로 진수다. 보통은 10진수로 표기하지만 컴퓨터에서는 16진수도 쓰고 8진수도 쓰기 때문이다. 이 같은 진수들을 인식하려면 어떻게 해야 할까? 정수는 10진수, 8진수, 16진수로 구분되어진다. 10진수 : 0이 아닌 수 시작 8진수 : 0으로 시작 16진수 : 0x, 0X로 시작

처음에 0이 아닌 수들, 즉 n이 나오면 A로 가서 10진수 정수가 되는 것이고 맨 앞에 0이 나온다면 일단은 8진수로 가는 길로 인식한 후, 그 뒤에 숫자가 나오면 C(8진수)로 인식하고 X나 x가 나오면 16진수로 인식한다. n : non-zero digit o : octal digit (0/1/…/7) h : hexa digit( 0/1../9, A/B/..F) d : digit( 0/1/2 …/9) 상태 A, B : 10진수 정수 상태 C : 8진수 정수 상태 E : 16진수 정수 RG : S -> nA | 0B A -> dA | ε B -> oC | xD | XD | ε C -> oC | ε D -> hE E -> hE | ε RE : E = hE + ε = hε = h D = hE = hh* = h+
C = oC + ε = o* B = oC + xD + XD + ε = o+ + (x + X)D = o+ + (x + X)h+ + ε A = dA + ε = d*

   S = nA + 0B = nd* + 0(o+ + (x + X)h+ + ε)
      = nd* + 0 + 0o+ + 0(x + X)h+

 ∴  S = nd* + 0 + 0o+ + 0(x + X)h+

실수 상수의 인식 실수의 형태는 지수 부분의 유무에 따라 고정소수점과 부동소수점으로 구분된다. 지수를 가지고 있으면 부동소수점(0.35E02), 지수가 있으면 고정소수점(25.4)이다. C까지 와서야 고정 소수점으로 끝난다. 여기서 e는 E로 쓸 수도 있다. 0.253E02는 0.253E+02와 같다. +는 부호를 생략해도 된다. 0.253E-01은 0.253*10^-1과 같다.

RG : S  dA D  dE | +F | -G A  dA | .B E  dE |ε B  dC F  dE C  dC | eD |ε G  dE RE :

여기서 d+.d+는 고정소수점이고 + d+.d+e(ε + ‘+’ +’-’) d+은 부동소수점

스트링 상수의 인식 일반적으로 스트링 상수는 일련의 문자를 “(double quote)와” 사이에 나타낸다. 특히 “를 스트링 상수 안에 넣기 위해서는 이스케이프 문자열을 사용한다. 여기서, a는 “와 \이외의 문자를 나타내고 c는 이스케이프 문자나 어떤 문자도 될 수 있다. C언어에서 문자형은 1바이트로 표현되며, 한글과 같은 2바이트 문자는 표현할 수 없다. 특수문자 및 제어문자는 확장문자열(escape sequence)로 표현한다.( ", \b, \0 등)

RG : S  “A A  aA | “B | \C B  ε
C  cA RE :

주석의 처리 보통 주석은 각 프로그래밍 언어에 따라 그 표현 방법이 다르지만 이 책에서는 /*와 */ 사이에 표현한다고 가정하여 이것을 인식하는 오토마타와 정규 문법, 그리고 정규표현을 고려해 보자.

여기서 a는 이외의 문자, b는 *, / 이외의 문자를 나타낸다. 즉, a = char_set - {} 그리고 b = char_set - {, /} 이다. 시작 상태 S에서 /를 만나면 A 상태를 거쳐 상태 B로 이동하고 이 상태에서 주석의 내용을 처리하게 된다. 그리고 * 을 만나면 C 상태로 이동하고 이 상태에서 입력이 /이면 주석의 끝이고 *이면 같은 상태를 유지한다. 상태 C에서 *, / 이외의 문자를 만나면 다시 B 상태로 돌아와 계속 주석의 내용을 처리한다.

RG : S  /A A  *B B  aB | *C C  *C | bB | /D D  ε

RE : C = *C + bB + /D = (bB + /) B = aB + **(bB + /) = aB + **bB + **/ = (a + ** b)B + **/= (a + **b)/ A = B = *(a + **b)/  S = /A = /* (a + **b)*/

정규 표현에서 알 수 있듯이 주석의 형태는 /와 */ 사이에 표현되며 주석의 내용은 */를 포함할 수 없다. 프로그램으로 작성한다면 아래가 된다. do {
while (ch != ‘’) ch = getchar(); ch = getchar(); } while (ch != ‘/’); 컴파일러를 위한 어휘 분석기는 주어진 입력을 선행 시간 내에 처리해야 하기 때문에 반드시 결정적 유한 오토마타로 구현해야 한다. 따라서, 정규 표현으로 기술된 토큰을 인식하는 어휘 분석기를 구현하는 방법은 다음과 같다. 먼저 정규 표현으로부터 비 결정적 유한 오토마타를 구성하고 비결정적 유한 오토마타를 결정적 유한 오토마타로 변환한다. 그리고 이것으로부터 최소화된 결정적 유한 오토마타를 얻어 프로그래밍하면 효율적인 어휘 분석기를 구현할 수 있다.

4.3 어휘분석기의 구현 어휘는 누가 만들까? 보통 두 사람으로 나뉜다. 언어 설계자와 프로그래머. 아래와 같이 나뉜다. 어휘(토큰) 언어 설계자 키워드(명령어) : int, void, if … 연산자 : +, -, <, *, not 구분자 : ;, :, , {, }, … 프로그래머 명칭 : sum, i, j, point 리터럴 : 10, 10.25, ‘A’ … 자 그럼 이제부터 Compiler의 전단부에 해당하는 어휘분석기를 직접 만들어보자! 예를 들어, int a = 500;인 경우, int(키워드), a(명칭), =(연산자), 500(리터럴), ;(구분자)로 나누는 분석을 해주는 어휘 분석기이다. 어휘 분석기를 구현하기 위해서는 먼저 문법표현으로부터 terminal 심벌들의 형태인 토큰의 구조를 결정한다. 보통, PGS(Parser Generating System)가 문법 표현으로부터 terminal 심벌을 가려내 주고 그 내부 번호를 지정해 준다. 이 내부 번호가 토큰 번호이며 파싱 테이블과 밀접한 관계를 가지고 있다. 일단, 토큰이 결정되면 이 토큰들을 인식할 수 있는 프로그램을 작성해야 한다. 프로그램을 작성할 때는 두 가지 방법이 있다. Programming the lexical analyzer using conventional programming language. //프로그래밍 언어를 이용해서 어휘 분석기를 구현할 수 있다. (such as C language) Generating the lexical analyzer using compiler generating tools such as LEX. //LEX같은 자동화 도구를 이용해서 자동으로 만드는 생성할 수 있다. 어휘 분석기를 프로그래밍으로 구현하기 위해서는 먼저 토큰들을 인식하기 위한 유한 오토마타를 상태 전이도로 나타내고 그 상태 전이도로부터 실제의 프로그래밍 언어로 각 상태에 대한 프로그램을 작성하면 된다. 실제로 Mini C 언어에 대한 어휘 분석기를 구현해보자. Mini C 언어에 대한 문법은 아래와 같다. The Tokens of Mini C Special symbols (30개 - 구분자나 논리연산자) ! != % %= && ( ) * *= + ++ += , - – -= / /= ; < <= = == > >= [ ] { ∥ } Reserved symbols (7개) const else if int return void while 위 토큰들을 인식하는 Mini C의 전체적인 상태 전이도는 아래 그림과 같다.

상태 1이 시작 상태이며, b에 /가 있는 것은 공백이 있을 때이다. l,_가 나오면 명칭으로 인식하는 상태이다. 5상태에는 정수 상수를 인식하는 상태, 10상태는 주석을 처리하는 상태이다. 함수 scanner가 입력 소스에서 한 개의 토큰을 분할해서 복귀하는 루틴이다. 그리고 토큰을 인식할 때 읽어 들인 문자가 더 이상 그 토큰에 속하지 않는 경우에, 이 문자는 다음 번의 토큰을 인식할 때 다시 처리되어야 하므로 입력으로 되돌려져야 한다. 이와 같은 과정을 retract라 부르며 C언어에서는 함수 ungetc()가 그와 같은 기능을 한다. 위 그림과 같이 정의된 Mini C에 대한 상태 전이도에 따라 어휘 분석기를 C프로그램으로 작성하면 아래와 같다.

/* main function */

void main() { tokenType token; //page 149쪽 (3) 참조. FILE fp; if((fp=fopen(“prime.mc”, “r”))==NULL) //파일 여는 것. { printf(“File open error!”); } / 소스코드(prime.c)에 대한 어휘분석기의 출력형태 const int max = 100; */ while (token.number !=teof) { token=scanner(fp); //ppt 145~149참조 if(token.number == tnumber) //토큰이 상수일 때 printf(“Token:%12d:( %2d,%7d)\n”, token.value.num, token.number, token.value.num); // (5) 출력형태: Token: 100 : (5, 100) //ppt 149? else if(token.number == tident) //토큰이 명칭일 때 printf(“Token:%12d:( %2d,%7d)\n”, token.value.id, token.number, token.value.id); // (3) 출력형태: Token: max : (4, max) else if(token.number == teof) break; //토큰이 Keyword(명령어, 연산자) 일때 else printf(“Token:%12s:( %2d,%7d)\n”, token.value.id, token.number, 0); // (1) 출력형태: Token: const : (30, 0) // (2) 출력형태: Token: int : (33, 0) // (4) 출력형태: Token: = : (23, 0) // (6) 출력형태: Token: ; (20, 0) } getchar(); fclose(fp); } 각 토큰의 토큰 번호를 나타내는 tsymbol의 형은 열거형으로 다음과 같은 내용으로 정의된다. enum tsymbol { tnull=-1, … ID_LENGTH는 유효한 명칭의 길이를 정의하는 상수이고 NO_KEYWORDS는 단어 심벌의 개수를 나타내며 Mini C에서는 7개의 단어 심벌이 있다. #define NO_KEYWORDS 7 #define ID_LENGTH 12 tokenType은 파서에게 넘겨주는 형태로 구조형으로 정의된다. 여기서 number는 토큰 번호를 갖는 필드이고 토큰 값을 갖는 명칭과 상수의 값은 각각 id와 num의 필드에 저장된다. 파서가 토큰을 요구할 때 스캐너는 이 구조체의 값을 배정하여 리턴해준다. keyword는 각 지정어의 스트링 값을 갖는 배열이며, tnum은 각 지정어에 해당하는 토큰 번호를 갖는 배열이다. keyword와 tnum 배열은 다음과 같은 초기 값을 갖는다. 함수 lexicalError()/superLetter()/superLetterOrDigit()의 의미는 다음과 같으며 getIntNum() 함수는 4.2.2절을 참조하기 바란다. 함수 scanner()는 위에서 언급한 변수와 함수들을 함께 작성한 후, 8장에서 설명하는 파서와 함께 Mini C 컴파일러를 위한 실질적인 전단부로 사용할 수 있다.

4.4 렉스 4.4.1 렉스 소개 렉스(LEX)는 어휘 분석기 생성기이다. 이것은 입력 스트림(input stream)에서 정규 표현으로 기술된 토큰들을 찾아내는 프로그램을 작성하는데 유용한 도구이다. 렉스의 기능은 사용자가 정의한 정규 표현과 액션 코드(action code)를 입력으로 받아 C 언어로 쓰여진 프로그램(yylex)을 출력한다. 그러면, 이 프로그램은 입력 스트림에서 정규 표현에 해당하는 토큰을 찾았을 때 그와 결합된 액션 코드를 실행한다.

lex.yy.c라는 프로그램에 들어가보면 yylex라는 함수가 들어가 있다. 여기에서 표현을 인식할 수 있다.

4.4.2 렉스 소스(LEX Source) 렉스의 입력을 렉스 소스(lex source)라 부르며, 다음과 같이 세 부분으로 구성되어 있다.

<정의 부분=""> %% <규칙 부분=""> %% <사용자 부프로그램="" 부분=""> 여기서, %%가 각 부분을 구분하는 구분자이며 각 부분은 반드시 순서적으로 기술되어야 한다. <정의 부분="">은 다음과 같은 형태로 구성된다. %{ /* 이 부분은 생성 프로그램에 의해 복사된다. */ %} 이름1 치환식1 이름2 치환식2 ... 이름n 치환식n 여기서, %{와 %} 사이에는 액션 코드를 C 언어로 작성할 때 필요한 자료 구조, 변수 그리고 상수 등을 선언할 수 있는 부분이다. 렉스는 %{와 %} 사이에 있는 C 프로그램 부분을 렉스의 출력인 lex.yy.c의 앞 부분에 그대로 복사한다. 이름 정의 부분은 특정한 정규 표현을 하나의 이름으로 정의하여 그 형태의 정규 표현이 필요할 때마다 쓸 수 있도록 해주는 부분이다. 이는 정규 표현에 대한 매크로 정의로 간주할 수 있다. 이름은 최소한 한 개 이상의 문자로 구성되며 <규칙 부분="">에서 사용할 때는 {과 }사이에 쓴다. 치환식i는 이름 i에 해당하는 정규 표현이며 이름과 치환식 사이에는 적어도 하나의 공백 또는 탭으로 분리되어야 한다. ex) L [a-zA-Z_] D [0-9] <규칙 부분="">은 렉스 입력의 핵심 부분으로 토큰의 형태를 표현하는 정규 표현과 그 토큰이 인식되었을 때 처리할 행위를 기술하기 위한 부분인 액션 코드로 구성된다. (Rules ::= regular expression + actions) %% R1 A1 R2 A2 ... Rn An 여기서, %%는 <정의 부분="">과 구분을 나타내는 구분자이며, Ri는 정규 표현이고 Ai는 액션 코드로 입력 스트림에서 일치되는 Ri를 찾았을 때, 어휘 분석기가 해야할 행동을 기술하는 액션 코드로 C 프로그램으로 작성된다. ex) int printf("found keyword int\n"); -> 이는 입력 스트림 내에서 문자열 int를 매칭했을 때 "found keyword int"라는 메세지를 출력하라는 의미를 나타낸다. 액션이란 sum을 넣으면 printf("명칭입니다"); 이런 식으로 printf가 액션 부분이다. echo같은 것도 액션의 일종이다. 렉스 입력의 세 번째 부분인 <사용자 부프로그램="" 부분="">은 렉스의 입력을 작성할 때 사용되는 부 프로그램들을 정의하기 위한 곳으로 렉스에 의한 어떤 처리 없이 그대로 렉스의 출력인 lex.yy.c에 복사된다. 4.4.3 렉스의 정규 표현(text characters + Operater characters) 정의한 정규 표현을 바탕으로 실제로 렉스에서 제공된 방법을 사용하여 토큰의 형태를 정형하게 표현할 수 있어야 한다. 렉스의 정규 표현은 크게 텍스트 문자(text characters)와 연산자 문자들(Operater characters)로 구성된다. 텍스트 문자는 입력 스트림에서 실제로 매칭되는 부분(알파벳이나 숫자들)이고 연산자 문자는 반복 또는 선택 등을 나타내는 특수 문자들(?, [], () 등...)이다. 예를 들어, 정규 표현 a*에서 a는 텍스트 문자이고 *은 연산자 문자이다. 렉스에서 토큰의 구조를 쉽게 표현할 수 있도록 제공한 연산자 문자들은 다음과 같으며 그 의미를 차례로 살펴보자. " : "사이에 있는 모든 문자는 텍스트 문자로 취급된다. \ : 한 개의 문자를 에스케이프하기 위하여 사용된다. 즉, 한 개의 문자를 텍스트 문자로 취급하고자 하는 경우 특수 문자 앞에 덧붙임으로서 해결할 수 있다. [] : 문자들의 종류를 정의하는데 사용한다. 예를 들어, [abc]는 a, b, c 중에서 한 문자를 나타낸다. -는 범위를 표시한다. 예를 들어, [A-Z]는 대문자를 나타낸다. ^는 여집합을 표현한다. 예를 들어, [^a-zA-Z]는 영문자를 제외한 모든 문자를 나타낸다. 즉, 문자가 아닌 것들. \는 C언어의 에스케이프 문자열로 간주된다. 예를 들어, [\40-\176]은 아스키 값 40인 공백(blank)부터 176인 ~(tilde)까지의 모든 인쇄 가능한 문자를 나타낸다. * : 0번 이상 반복을 나타낸다. 즉, a*는 a가 0번 이상 반복될 수 있음을 나타낸다. + : 한 번 이상 반복될 수 있음을 나타낸다. [a-z]+는 소문자로 이루어진 단어를 나타낸다. ? : 선택을 의미하는 연산자로 ab?c는 b가 선택적이므로 abc 또는 ac를 의미한다. | : 택일을 위한 연산자로서 (ab | cd)는 문자열 ab 또는 cd를 인식한다. 여기서, 괄호 없이 ab | cd로 쓸 수 있다. ^ : 라인의 시작에서만 인식된다. 정규 표현식 ^abc는 라인의 시작에 문자열 abc가 나타났을 때에만 토큰으로 abc를 처리한다. []안에 있는 ^와는 구별해야 한다. $ : 오직 라인의 끝에서만 인식된다. / : 접미 문맥(trailing context)을 명시할 때 사용된다. 즉, ab/cd는 ab다음에 cd가 이어서 나타날 때만 ab가 토큰으로 처리된다. 따라서 abc$, abc/\n은 모두 라인 끝에 abc가 나타났을 때만 abc를 인식하게 된다. . : 점(dot)은 개행 문자를 제외한 모든 문자들을 나타낸다. 예를 들어, "--".*는 --부터 한 라인의 끝까지와 부합된다. {} : 정의된 이름을 치환식으로 확장할 때 사용한다. <> : 시작 조건. C언어에서 허용하는 명칭의 정규표현은 (l+_)(l+d+_)*이고 이것을 렉스의 정규표현으로 나타내면 [a-zA-Z_][a-zA-Z0-9_]*이다. 4.4.4 LEX action 액션 코드(action code)부분은 정규 표현에 일치되는 문자열, 즉 토큰이 인식되었을 때 실행해야 할 행동을 C언어로 기술하는 부분이다. 인식되지 않은 모든 문자에 대해 실행되는 default 행위는 입력을 출력으로 그대로 복사하는 것이다. 따라서 그대로 통과되는 문자열 없이 모든 입력을 처리하고자 하는 렉스 사용자는 모든 문자열을 처리할 수 있도록 렉스의 <규칙 부분="">을 작성하여야 한다. 렉스에서의 표준 입력과 출력은 stdin과 stdout이다. 어떤 행위도 실행할 필요가 없는 문자열에 대한 처리는 다음과 같이 C언어의 널 문장(null statement)을 사용한다. [ \t\n] ; // " " | "\t" | "\n" 과 같다. 이것은 구분자로 사용된 공백, 탭, 개행 문자를 입력에서 무시하고자 할 경우에 처리하는 방법이다. 렉스의 전역변수(global variable)인 yytext는 문자 배열형(character array type)으로 어떤 정규 표현에 의해 실제로 매칭된 문자열 값을 갖고 있다. 따라서 토큰 값이 필요한 경우에 변수 yytext의 내용을 사용하여 해결할 수 있다. 가령, [a-z]+ printf("%s",yytext); 은 입력에서 소문자로 이루어진 단어를 찾으면 그 단어가 yytext에 저장되고 그 내용을 그대로 출력한다. 이와 동일한 기능을 하는 렉스의 함수에는 ECHO가 있다. [a-z]+ ECHO;해주면 위와 똑같은 기능을 해준다. 전역변수 yytext : 입력 스트림에서 정규 표현하고 실제 매칭된 문자열 (ex. [a-z]+ printf("%s", yytext); ) yyleng : 매칭된 문자열의 길이를 나타내는 변수 (ex. yytext[yyleng-1] : 마지막 문자를 나타내고 싶을 때 배열은 0부터 시작하니까 이렇게 써준다.) 함수 yymore() : 현재 매칭된 문자열의 끝에 다음에 인식될 문자열이 덧붙여지도록 하는 함수. 이 모든 문자열은 yytext에 저장된다. yyless(n) : n개의 문자만을 yytext에 남겨두고 나머지는 다시 처리하기 위하여 입력 스트림으로 되돌려 보내는 함수 yywrap() : 렉스가 입력 스트림의 끝을 만났을 때 호출하는 함수이다. 정상적인 경우에 이 함수의 복귀 값은 1이 된다. 입출력 함수 input() : 입력 스트림으로부터 다음 문자를 읽는 함수. output(c) : 출력 스트림으로 문자 c를 내보내는 함수. unput(c) : 다시 처리될 수 있도록 문자 c를 입력 스트림으로 되돌려 보내는 기능을 하는 함수. 함수 input()에 의해 다시 읽혀진다. 4.4.7 Usage cc는 c의 컴파일러 -o는 object파일이 test다. -ll은 linked library. 스캐너의 생성 및 동작 렉스를 이용하여 스캐너를 생성하는 과정을 나타내면 다음과 같다. 필요한 작업을 처리할 수 있도록 렉스 입력을 작성한 후, 렉스를 통하여 lex.yy.c를 생성한다. 생성된 lex.yy.c 파일을 컴파일하면 필요한 스캐너를 얻을 수 있다. lex test.l cc lex.yy.c -o test -ll test < hello.mc 를 해주면 된다. -ll은 렉스의 디폴트 라이브러리를 링크시키기 위한 것이다. 렉스의 출력은 C프로그램인 lex.yy.c이고 이 파일 내에는 스캐너 역할을 담당하는 함수 yylex()가 포함되어 있다. 함수 yylex()는 렉스의 입력에서 명시한 정규 표현과 일치하는 토큰을 입력 스트림에서 찾을 때까지 한 번에 한 문자씩 계속 읽어들인다. 현재의 입력 스트림이 두 개 이상의 정규 표현과 매칭될 때 렉스의 선택 규칙은 다음과 같다. 토큰을 가장 길게 인식할 수 있는 정규 표현을 선택한다. 인식할 수 있는 토큰의 길이가 같은 경우, 먼저 기술된 정규 표현을 선택한다. 예를 들어, integer Keyword action; [a-z]+ identifier action; 두 가지가 있을 때 먼저나온 integer부터 적용한다는 것이다. 5장 Context-free 문법 context-free문법은 효율적이고 잘 정의된 구문 분석 알고리즘을 가지기 때문에 프로그래밍 언어의 문법적인 표현이나 번역에 매우 중요하다. 정규문법은 간단한 패턴을 기술하기에는 적합하지만 프로그래밍 언어의 구문 구조를 표현하기에는 너무 제약이 많아 부적합하다. 따라서 대부분의 경우 토큰의 구조는 정규 표현으로 나타내지만 프로그래밍 언어의 구조는 context-free 문법을 사용한다. context-free 문법으로 표현하면 다음과 같은 장점이 있다. 간단하고 이해하기 쉽다. 표현된 문법으로부터 자동적으로 인식기를 구현할 수 있다. 입력된 프로그램의 구조를 생성 규칙에 의해 분해할 수 있으므로 번역에 유용하다. context-free 문법에서 모든 생성규칙은 A -> a의 형태를 갖는다. 유도 과정의 문장 형태에서 A를 문맥에 관계없이 a로 대치할 수 있기 때문에 context-free라 부른다. 문법 심벌들의 간단한 표기법을 알아보자. Terminal 심벌(Vt) a, b, c..., 0, 1, 2 ... +와 -같은 연산자 기호와 콤마, 세미콜론. if 또는 then등과 같은 얘들. Nonterminal 심벌(Vn) A, B, C... S는 보통 시작 심벌 나 와 같이 <>로 나타낸 문법 심벌 만약 아무런 언급이 없다면, 첫 번째 생성 규칙의 왼쪽에 있는 nonterminal이 시작심벌이다. A -> a1, A -> a2, A -> a3 ...와 같이 모두 왼쪽이 A라면 A -> a1 | a2 | a3 등으로 간단히 표기할 수 있다. 예를 들면, E →E OP E | (E) | -E | id , OP →+| −| ∗| /가 있을 때 VN= {E, OP } VT= {(, ), −, id, +, ∗, /} 이다. 시작 심벌은 E이다. 5.2.1 유도 context-free 문법에서 문장의 생성은 문장 형태의 스트링에서 생성 규칙을 연속적으로 적용하여 nonterminal을 확장함으로써 얻을 수 있다. 예를 들어 이런 문법이 있다. E -> E + E | E * E | (E) | a E가 E+E로 유도되는 것을 E ⇒ E+E로 표기할 수 있고 연속적으로 적용해 E ⇒ (a + a)가 될 수 있다. Context-free 문법에서는 생성 규칙의 오른쪽에 nonterminal이 여러 개 나올 수 있기 때문에 같은 문장을 유도하는 여러 방법이 있을 수 있다. 가장 왼쪽에 있는 nonterminal을 대치하면 좌측 유도라고 하고 가장 오른쪽에 있는 nonterminal을 대치하면 우측 유도라고 한다. 좌측 유도 : E ⇒ (E) ⇒ (E+E) ⇒ (a+E) ⇒ (a+a) //⇒밑에 lm이라고 써져있다. 우측 유도 : E ⇒ (E) ⇒ (E+E) ⇒ (E+a) ⇒ (a+a) //⇒밑에 rm이라고 써져있다. 좌측 유도에서 적용된 일련의 생성 규칙 순서를 좌파스(left parse)라 하며, 우측은 우파스라고 한다. 생성 규칙에 번호를 붙이면 된다. 좌파스 : 2 3 1 4 4 4같이. 5.2.2 유도 트리 Context-free 문법에서, 문장이 유도되는 과정을 트리 형태로 표현할 수 있는데 이를 유도 트리(derivation tree)라 한다. 유도 트리는 루트 노드, 중간 노드, 단말 노드로 구성되며, 생성 규칙에 의해 적용되는 문장의 계층적 구조를 나타낸다. context-free 문법 G = {Vn, Vt, P, S}에 대한 유도 트리 루트 노드의 이름은 항상 시작 심벌 S이다. 중간 노드의 이름은 nonterminal 심벌이다. 단말 노드의 이름은 terminal 심벌이거나 ε가 될 수 있다. 왼쪽부터 순서적으로 이름이 A1, A2,..., AK인 노드들이 어떤 노드 A의 자식 노드라면, 생성 규칙 A -> A1A2A3 ...AK가 존재한다. 구성된 유도 트리는 자 노드의 위치 순서가 생성 규칙의 오른쪽에 나타난 심벌의 순서와 반드시 일치한다. 따라서 유도 트리는 순서 트리가 된다. 각각의 유도 방법에 따라 유도 트리의 모양은 변하지 않는다. 즉, 한 문장에 대한 tree 모양은 unique하다. 그러나 어느 한 가지 유도 방법을 이용하더라도 구성되는 유도 트리가 유일하다는 것을 확증하지 못할 뿐만 아니라, 실제로 두 개 이상의 유도 트리가 만들어지는 경우도 존재한다. 예를 들어, 문장 a+a*a를 아까 문법에 의해서 좌측 유도를 했을 때 바로 E + E * E를 갈 수도 있고 a + E * E로 갈 수 있기 때문이다. 이러한 문법을 모호하다고 말한다. (문법 G에 의해 생성되는 어떤 문장이 두 개 이상의 유도 트리를 갖는다면, 문법 G는 모호하다라고 한다) 즉, 모호한 문법은 어떤 문장에 대해 좌측 유도나 우측 유도 어느 한 가지 방법을 적용하더라도 두 개 이상의 유도 과정이 존재하는 경우이다. 그러므로 증명하는 방법은 두 개 이상의 유도 트리를 그리기만 하면 된다. 구문 분석기의 출력으로 유도 트리를 낼 경우, 문장의 유도 트리를 결정적으로 구성하기가 어렵기 때문에 모호하지 않은 문법이 필요하다. 그러므로 모호한 문법을 모호하지 않은 문법으로 바꿀 수 있으나 모든 문법을 바꿀 수 있지는 않다. 일반적으로 연산 순위나 결합 법칙의 정보를 이용해서 생성 규칙을 추가하여 모호성을 제거한다. 이때 새로운 nonterminal을 도입하게 된다. E -> E + E | E * E | (E) | a 를 바꿔보자. 연산순위는 +가 먼저고 *를 뒤로 미룬다고 한다. 가장 기초적인 피 연산자를 F라 두면 이것은 괄호로 묶인 산술식이나 a가 될 수 있다. F -> (E) | a 다음으로 순위가 높은 *를 갖는 F를 위해 T를 도입한다. T -> T * F | F 여기서, T가 좌측 순환 구조를 갖기 때문에 a*a*a는 (a*a)*a이다. 즉, 좌측 결합에 합당함을 알 수 있다. 결과는 아까 사진과 같다. +와*가 먼저 연산되기 전에 괄호 안이 먼저 연산되고 *가 연산된다. 일반적으로 생성 규칙의 형태가 A -> AaA인 경우 모호성이 나타난다. 왜냐하면, AaAaA와 같은 문장 형태에 대해 두 가지 형태의 트리를 만들 수 있기 때문이다. 한 context-free 언어를 생성하는 모든 문법이 모호하다면, 이 언어를 본질적으로 모호하다고 한다. 그리고 본질적으로 모호한 문법은 모호하지 않은 문법이 존재하지 않는다. 일반적으로 한 문법이 모호하다는 것을 형식적으로 증명할 수 있는 방법이 존재하지 않으며, 모호하지 않게 바꾸는 알고리즘도 존재하지 않는다. 5.3 문법 변환 주어진 문법에 대해 효율적인 구문 분석을 하기에 적합한 형태로 바꾸는데 이용되는 여러 가지 기법을 소개하고자 한다. 만약 L(G1) = L(G2)이면 문법 G1과 G2는 동등하다고 말한다. 다시 말해서, 두 개의 문법이 동등하다는 의미는 두 개의 문법이 생성하는 언어가 같을 때이다. 한 문법을 다른 형태의 동등한 문법으로 변환하는데 사용되는 기법에는 크게 두 가지가 있다. 첫 번째는 대입이고 두 번째는 확장이다. 대입이란 특정한 생성 규칙을 제거하고 그에 해당하는 생성 규칙들을 추가하는 방법으로 제거된 생성 규칙의 오른쪽 부분에 있는 nonterminal 심벌 대신에 그 생성 규칙들의 오른쪽을 대입함으로써 문법을 변환하는 방법이다. 요약하면 A -> aBr을 제거하고 그 대신에 A -> ab1r을 추가하여 동등한 문법을 만드는 방법이다. 유도 과정에서 대입한 효과는 유도 과정의 횟수를 한 번 줄인 결과가 된다. 확장이란 새로운 nonterminal을 도입하여 한 개의 생성 규칙을 쪼개는 방법이다. A →αβ가 있을 때 A →αX, X→β or A →Xβ, X→α로 쪼갤 수 있다. 필요 없는 생성 규칙 제거 한 문법이 생성하는 언어는 시작 심벌로부터 유도할 수 있으며 모두 terminal 심벌들로 이루어진 스트링의 집합이다. 따라서 문장을 생성하는데 적용할 수 없는 생성 규칙들은 모두 제거할 수 있으며 필요 없는 생성 규칙이라 부른다. X가 필요없는 심벌이라는 의미는 X가 terminal 스트링을 생성할 수 없는 nonterminal 심벌이거나, 또는 시작 심벌로부터 도달할 수 없는 심벌이라는 것이다. 역으로, 필요한 생성 규칙들은 모두 terminating nonterminal(terminal 스트링을 유도할 수 있는 nonterminal)과 도달 가능한 심벌들이다. 하는 방법은 생성 규칙의 오른쪽이 모두 terminal만으로 이루어진 생성 규칙을 찾는다. 그 다음 그걸 거리키는 nonterminal을 찾는다.(그냥 거꾸로 가기) 추가되는 nonterminal이 없으면 종료하고 원래 있던 nonterminal에서 빼면 된다. 도달 가능한 심벌을 구하는 방법은 시작 심벌로 시작해서 나눠지는 걸 다 찾는다. 계속 찾고 마지막 결과물을 가장 처음에 있던 것에서 빼준다. ε 생성 규칙 제거 생성 규칙의 형태가 A -> ε인 경우, ε-생성 규칙이라 부른다. CFG가 다음과 같은 조건을 가질 때 ε-free라고 한다. P가 ε 생성 규칙을 갖지 않거나 S하나만이 ε 생성 규칙을 가지며, 다른 생성 규칙의 오른쪽에 S가 나타나지 않아야 한다. 즉 S가 ε로 갈 수 있으면 없어질 수 있으니까 다른 terminal이 붙어있으면 빼주는 것까지 규칙으로 넣으면 된다. S -> aSbS이면 S -> aSbS | abS | aSb | ab 가 된다. 단일 생성 규칙의 제거 생성 규칙의 형태가 A -> B와 같이 생성 규칙의 오른쪽에 한 개의 nonterminal만이 나오는 생성규칙을 단일 생성 규칙이라 한다. 이것으로 인하여 불필요한 유도 과정이 생기며 파싱 속도가 느려진다. 단일 생성 규칙 제거 방법 초기에, 단일 생성 규칙을 모두 제거하여 P`를 구한다. 먼저 Vna를 구한다. Vna는 A로부터 단일 생성 규칙을 적용해서 갈 수 있는 nonterminal의 집합이다. Vna에 속하는 nonterminal B가 B -> a 형태의 생성 규칙이 있다면 직접 A에서 유도될 수 있도록 A -> a를 추가한다. E -> E + T | T T -> T * F | F F -> (E) | a 이면 P` = { E -> E + T, T-> T * F, F-> (E), F->a} 그리고 각 nonterminal에 대하여 다음을 반복한다. 첫 번째로 E에 대해서, Vne = {T, F}가 된다. Vne에 속하는 각 nonterminal의 생성 규칙 중 단일 생성 규칙이 아닌 생성 규칙의 rhs를 E에 대한 생성 규칙으로 만든 후, P`에 추가한다. 따라서, P`은 다음과 같은 생성 규칙을 갖게 된다. P` = { E -> E +T | T* F| (E) | a, T -> T * F, F -> (E), F ->a} 두 번쨰로 T에 대해서, Vnt = {F}가 된다. 마찬가지로 F생성규칙 중 단일 생성 규칙이 아닌 것을 T에 대한 생성 규칙으로 만들어 P`에 추가한다. P` = {E -> E + T | T * F | (E) | a, T -> T * F | (E) | a, F -> (E), F -> a} 세 번째로 F에 대해서 Vnf는 공집합이라 추가되는 생성 규칙이 없다. 단일 생성 규칙을 제거한 문법을 보면 E -> E + T | T * F | (E) | a T -> T * F | (E) | a F -> (E) | a 이다. Context free 문법 G = (Vn, Vt, P, S)가 어떤 A ∈ Vn에 대하여 A *=>A형태의 유도 과정을 갖지 않을 때 cycle-free하다고 한다. 만약 G가 cycle-free하고 ε-free, 그리고 필요 없는 심벌을 가지지 않을 때 proper하다고 한다. cycle과 ε을 가지고, 필요없는 심벌을 가질 경우, 구문 분석기의 크기가 필요없이 커지게 된다. 그래서 proper하게 만들어야 한다. CFG 표기법(3가지 - BNF, EBNF, SD) BNF(Backus - Naur Form)는 프로그래밍 언어의 형식적 정의를 위해 널리 사용되어 왔다. BNF에서, nonterminal 심벌은 <>로 나타낸다. terminal 심벌은 ''로 나타낸다. ->은 ::=으로 나타낸다. 예를 들면 ::= a | b | c | ... | y | z F -> (E) | a는 ::= '(' ')' | 'a'이다. BNF로 모든 프로그래밍 언어의 문법을 기술 할 수 있지만, 이보다 읽기 쉽고 간결하게 프로그래밍 언어를 나타내기 위해 확장된 BNF(EBNF)를 도입했다. EBNF는 반복되는 부분이나 선택적인 부분을 간결하게 표현할 수 있는 방법으로 이를 위해 특수한 의미를 갖는 메타 심벌(meta symbol)을 사용한다. 메타 심벌은 언어의 일부분이 아니라 그 언어를 표현하려고 사용된 특수 심벌이다. 반복되는 부분을 기술하기 위해서는 {}를 사용하고 반복되는 최대 횟수와 최소 횟수를 나타낼 수 있다. {} 뒤에 최대 횟수를 위에, 최소 횟수를 아래에 넣으면 된다. 선택적인 부분을 기술할 때에는 메타 심벌 []로 나타낸다. 괄호는 (), 택일 연산자는 |이다. 이를 이용해서 여러 개의 생성 규칙들을 묶어서 표현할 수 있다. 예를 들면, BNF로는 ::= , | 가 되나 EBNF로는 ::= {,}가 된다. ::= 'if' '(' ')' ['else' ] //RG는 어휘용 문법이고 CFG는 구문용 문법이다 초보자가 언어의 구문 구조를 쉽게 이해할 수 있도록 문법을 도식화하는 방법이 있다. 이와 같은 그림을 문법 흐름도(Syntax diagram)이라고 한다. 원 : terminal symbol 사각형 : nonterminal symbol 화살표 : 흐름 경로 C일 때, 반복인데 흐름도니까 +가 먼저 와있다. 5.5 푸시다운 오토마타 유한 오토마타는 보조 기억장치를 갖고 있지 않기 때문에 지나간 입력의 유래를 알 수 없다. 따라서 입력 심벌의 일정한 개수를 셀 수 있는 능력이 없는 것이다. 그러나 푸시다운 오토마타는 보조 기억장치가 있다. 푸시다운 오토마타(Push down automata)는 인식기의 한 종류로 유한 상태 제어(finite control), 입력 테이프(input tape), 그리고 스택(push-down list, stack)으로 구성된다. 입력 테이프는 입력 스트링을 유지하고 있으며 스택은 보조 기억장치로 보통 푸시다운 리스트라고 부른다. 유한 상태 제어는 전체 행동을 제어하는 기능을 하며 현재 입력 심벌과 스택의 top 심벌에 따라 행동한다. 푸시다운 오토마타 P는 7개의 요소로 구성된다. Definition: PDA P = (Q, Σ, Γ, δ, q0, Z0, F), Q : 상태의 유한집합. Σ : 입력 심벌의 유한집합. Γ : 스택 심벌의 유한집합. δ : 사상함수 Q ×(Σ∪{ε}) ×Γ→Q ×Γ*, //스택 심벌까지 들어가 있다. q0 ∈ Q : 시작상태(start state), Z0 ∈ Γ : 스택의 시작 심벌, F ⊆ Q : 종결 상태(final state)의 집합이다. δ : Q × (Σ ∪ {ε}) × Γ → Q × Γ* //사상함수. δ(q, a, Z) ={(p1, α1), (p2, α2), ... ,(pn, αn)} //사상함수는 이런 형태를 가진다. 의미: 현재상태가q이고 입력 심벌이 a이며 스택top 심벌이 Z일 때, 다음 상태는 n개중에 하나이며 만약(pi, αi)가 선택되었다면 그 의미는 다음과 같다 현재의 q 상태에서 입력a를 본 다음 상태는 pi이다. 스택 top 심볼Z를 αi로 대치한다. P의 configuration : (q, ω, α) //P의 형태란 어떤 시점에서 P의 현재 상태를 나타내는 방법이다. q : current state //현재의 상태 ω: input symbol //읽지 않은 입력 부분 //ε일 경우에는 모든 입력 심벌이 읽혀짐. α: contents of stack //스택의 내용 예를 들어, 어떤 한 시점에서 P의 형태가 (qi, aiai+1...an, ZiZi+1...Zi+k)일 때, 현재 상태는 qi이고 아직 읽지 않은 부분 즉, 앞으로 봐야할 스트링이 aiai+1...an이다. 여기서 ai가 현재 보고있는 입력 심벌이다. 또한 스택의 내용은 ZiZi+1...Zi+k가 되며 Zi가 스택 top 심벌이다. P에 의해 한 상태에서 다른 상태로의 이동은 ㅏ로 표기한다.( P의이동(move)ː┣) δ(q, a, Z)가 (q', r)를 가지면, 다음과 같은 이동이 있게 된다. (q, aω, Zα) ┣( q', ω, γα) 만일 a ≠ε인 경우, 유한 제어가 q 상태에 있고 현재의 입력 심벌이 a, 스택의 top이 Z인 경우 P의 형태에서 유한 제어가 q` 상태로 되고, 입력 헤드(input head)가 다음으로 한 칸 이동하고, 스택의 top에 있는 Z가 γ로 대치된 형태로 이동됨을 나타낸다. γ가 ε인 경우, 스택에서 pop되었다고 말한다. 만약 a=ε인 경우, ε-이동(ε-move)이라고 하는데, 현재의 입력 심벌에 대해서는 고려되지 않고, 입력 헤드도 움직이지 않는다. 그러나 유한 제어의 상태가 변하고, 스택의 내용도 바뀐다. ε-이동은 모든 입력 심벌이 읽혀 졌을 때에도 발생할 수 있는 행동이다. 그러나 스택이 비었을 경우에는 어떠한 이동도 가능하지 않다. ㅏ*는 0번 이상의, ㅏ+는 한 번 이상의 이동을 나타낸다. (move star, move dagger) P의 시작 형태는 ∑*에 속하는 w에 대해 (q0, w, Z0)의 형태(시작형태)를 가지며 종결형태는 (q, ε, a)의 형태를 이룬다. 시작 상태에서 입력 스트링 w를 다 본 상태가 종결 상태에 속하면 스트링 w는 P에 의해 인식된다고 말한다. 그리고 P에 의해 정의되는 언어, 즉 푸시 다운 오토마타 언어는 L(P)로 표기하며, P에 의해 인식되는 스트링의 집합으로 다음과 같은 의미를 갖는다. 일반적으로 PDA가 인식하는 언어와 CFG가 생성하는 언어의 종류는 같다. 항상 L(CFG) = L(PDA)가 된다. 푸시 다운 오토마타는 앞에서도 설명했듯이 입력 스트링을 모두 읽은 후에도 이동이 일어나며, 스택이 빈 경우에는 이동이 발생하지 않는다. 그리고 한 번의 이동으로 스택 top 부분에 있는 심벌 뿐만 아니라 스택 top 부분에 있는 유한 길이의 스트링도 다른 스트링으로 대치할 수 있다. 지금까지의 PDA는 한 번의 이동으로 스택의 top에 있는 심벌만이 대치될 수 있었다. 이와 같은 사실을 이용하여 PDA를 다음과 같이 확장할 수 있다. (q,aω,αγ) ┣(q', ω,βγ) 이것은 q 상태에서 입력심벌 a를 보고 입력 헤드를 오른쪽으로 한 심벌 이동하고 top 부분의 알파를 베타로 대치한다는 의미이다. 일반적인 PDA와는 달리 확장된 PDA는 스택이 비었을 때도 이동이 발생할 수 있다. 회문의 형태를 인식하기 위해, P는 먼저 스택의 입력인 prefix인 w를 저장하고, 스택의 top에 center mark인 S를 놓는다. 그 후 스택에 다음 입력 심벌을 넣어 스택 top 부분의 aSa 혹은 bSb를 S로 대치한다. 이런 방법으로 모든 입력에 대하여 처리한다. 마지막으로 SZ가 스택에 있다면 P는 SZ를 pop하고 종결 상태로 간다. 5.6 Context-free 언어와 PDA 언어 지금까지의 내용을 기초로 PDA 언어가 정확히 context-free 언어라는 것을 보일 수 있다. 즉, CFG가 주어졌을 때, 그에 해당하는 PDA를 구성할 수 있고 역으로 PDA가 주어졌을 때, PDA가 인식하는 언어와 같은 언어를 생성하는 CFG를 만들 수 있다. CFG가 주어졌을 때, L(G)를 인식하는 PDA를 구성하는 방법을 생각해보자. 상태는 하나만 필요하고 그것이 시작 상태도 된다. 그리고 입력 심벌은 항상 terminal 심벌이 되고 스택에는 terminal 심벌이나 nonterminal 심벌이 들어갈 수 있다. 스택 시작 심벌은 문법의 시작 심벌이 되며, 입력 스트링을 모두 보고 스택이 비어 있을 때만 인식하게 만들기 때문에 종결 상태는 없다. top-down PDA의 δ 함수는 G의 생성 규칙으로부터 만든다. 여기서, 1을 확장(expand)라 한다. 즉, ε-이동을 하면서 스택의 내용만 A를 알파로 바꾼다. 그리고 2를 pop이라 하며 입력 심벌과 스택 top 심벌이 같은 경우에 스택의 top 심벌은 스택에서 제거하고 입력 심벌은 입력 스트링에서 제거한다. 이와 같은 방법으로 PDA를 만들 경우, δ 함수의 개수는 생성 규칙의 개수에다 terminal 심벌의 개수를 더한 것이 된다. 시작 심벌이 확장을 통하여 주어진 입력 스트링과 같아지면 올바른 문장이 되어 입력은 다 보고 스택은 비게 됨으로 인식하게 된다. 시작 심벌로부터 아래로 내려가면서 스트링을 만들기 때문에 이와 같은 방법을 top-down 구문 분석 방법이라 한다. CFG에서 우측 유도를 역으로 적용함으로써 bottom-up 파서로 작동하는 확장된 PDA를 만들 수도 있다. bottom-up P의 형태에서 스택 top의 위치는 top-down인 경우에는 왼쪽이며 bottom-up인 경우에는 오른쪽이다. 주어진 스트링을 bottom-up 방법으로 인식하기 위한 과정은 다음과 같다. 생성 규칙의 rhs가 스택 top부분에 나타날 때 까지 shift를 반복하다가 rhs가 모아지면 reduce를 한다. 반복하고 시작 심벌에 다다르면 올바른 문장이라고 인식하는 방법이다. 다음으로 PDA P가 주어졌을 때, P가 인식하는 언어 L(P)를 생성하는 CFG G를 만드는 방법을 고려해보자. P가 인식하는 모든 스트링을 생성할 수 있는 문법을 고안해야 한다. 그 방법은 P가 스트링 w를 인식하는 과정에서 생기는 일련의 이동과 CFG G가 w를 좌측 유도로 생성하는 유도 과정이 직접 일치하도록 G의 생성규칙을 만드는 것이다. 뭐 그렇다. 다음은 모두 동등한 의미를 갖는다. 결론 L은CFG G에의해생성되는언어L(G)이다. L은PDA P에의해인식되는언어L(P)이다. L은PDA P에의해인식되는언어Le(P)이다. L은extendedPDA에의해인식되는언어L(P)이다. 6장 구문 분석 구문 분석이란 주어진 입력이 올바른 프로그램인가를 검사하고 다음 단계에서 필요한 정보를 구성하는 과정이다. 구문 분석기는 간단히 파서라 부르며, 스캐너에 의해 생성된 토큰을 입력으로 받아 문법적인 검사를 한 후에 다음 단계인 중간 코드 생성기가 효과적으로 중간 코드를 생성할 수 있는 형태의 정보를 구성하여 출력한다. 구문 분석의 결과로 출력되는 구문 분석 정보는 일반적으로 트리 형태 이며 트리를 어떤 방식으로 만들어 가느냐에 따라 크게 top-down 방식과 bottom-up 방식으로 구분된다. 일반적으로 생성되는 트리는 유도 트리와 같은 모양을 갖는데 유도 과정을 나타낼 때는 유도 트리라 말하고, 구문 분석기에 생성될 때는 파스 트리라고 부른다. Context 문법을 위한 구문 분석 방법은 파스 트리를 어떤 순서로 만들어 가느냐에 따라 크게 top-down 방식과 bottom-up 방식으로 구분할 수 있다. top-down 방식 루트노드에서 단말노드로 만듬 좌측 유도와 같은 순서의 생성 규칙 적용 시작 심벌로부터 생성규칙을 적용하여 주어진 스트링을 생성할 수 있으면 올바른 문장, 아니면 틀린 문장. 문장형태에서 nonterminal을 계속 대치해 나갈 때, 그 nonterminal에 대한 생성 규칙이 여러 개 있으면 어떤 생성 규칙을 적용해야 되는지는 비 결정적이다. 그러나, 문법이 어떤 특정한 조건을 만족한다면 결정적으로 생성규칙을 선택할 수 있고, 어떤 문장이 옳은지를 입력 길이의 선형 시간에 판단할 수 있다. bottom-up 방식 단말노드에서 루트노드로 만듦. 우측 유도의 역순 주어진 스트링으로부터 시작하여 문법의 시작 심벌로 축약시킨다.(reduce한다.) 시작 심벌로 갈 수 있으면 올바른 문장이고 그렇지 않으면 틀린문장 reduce sequence는 우측 유도 과정에서 적용된 생성 규칙 번호의 역순이 된다. 입력 스트링은 두 방식 다 한 번에 한 심벌씩 왼쪽부터 오른쪽으로 검조한다. bottom-up 방식이 파스 트리를 구성하는데 더 효과적이다. 6.2 구문 분석기의 출력 구문 분석기는 입력으로 스트링 w를 받아 만일 w가 정의된 문법의 문장이라면 구문 분석 정보를 생성하고 w가 정의된 문법의 문장이 아니라면 에러 메세지를 출력한다. 유도 과정에서 적용된 일련의 생성 규칙 번호를 파스라 하며, 파스의 종류에는 좌측 유도 과정에서 생성된 좌파스와 우측 유도 과정에서 적용된 생성 규칙 번호의 역순인 우파스가 있다. top-down일 때는 좌파스가 생성되고, bottom-up일 때는 우파스가 생성된다. 파스트리 파스 트리는 올바른 문장에 대해 구문 분석기가 그 문장의 구조를 트리 형태로 나타낸 것으로 루트 노드, 중간 노드, 단말 노드로 구성되는데 루트 노드는 정의된 문법의 시작 심벌이고, 중간 노드는 각 생성 규칙의 좌측 nonterminal에 해당되며, 단말 노드는 주어진 스트링을 생성하는 terminal 심벌들이 된다. 파스 트리는 주어진 스트링에 대해 형태는 같지만 구문 분석 방법에 따라 구성되는 순서가 다르다. top-down 방식은 루트 노드로부터 생성 규칙이 적용되어 직접 유도될 때마다 트리가 구성되며, bottom-up 방식은 주어진 문장으로부터 생성 규칙이 reduce될 때 서브트리가 만들어진다. 주어진 스트링을 구문 분서갛여 구성된 파스 트리의 형태가 두 개 이상 생길 수가 있다. 연산자 +와 *에 대한 연산 순서를 따진다. 추상 구문 트리 파스 트리의 중간 노드에서 표현되는 nonterminal은 쓸데 없음. 필요한 의미 정보만 가진 추상 구문 트리가 더 효율적이다. = syntax tree, semantic tree 추상 구문 트리의 비단말 노드는 의미 있는 생성 규칙의 이름이 되며 단말 노드는 의미있는 terminal 심벌이 된다. 의미 있는 생성 규칙과 의미있는 terminal 심벌은 모두 컴파일러를 구현하는 사람이 결정한다. 일반적으로 의미 있는 terminal 심벌은 보통 토큰 값을 갖는 terminal로 명칭과 상수이며, 의미있는 생성 규칙은 특정한 구문 구조를 표현하고 있는 생성 규칙이다. <7장 LL 구문 분석> A에 3번의 백트레킹 가능성. 하지만 그 전에 확인했으면 좋겠다. 퍼스트나 팔오우나 둘다 터미널의 집합. A에 오른쪽에 나타나면. A뒤에 a가 있음. B뒤에는 c하나. 각각 확인. 공집합인가. 겹치는 게 없다. 2)도 만족. Recursive - descent 파서 S -> aA | bB 터미널이라면 다음 심볼을 읽는다. nonterminal은 P(A)에 대한 프로슈저. tc then 끝. $가 왔다는 건 다 읽었다. 약간 메인 함수와 부 프로그램등 코딩하는 방식과 비슷하다. Lookahead 좀더 앞을 보자. 누가 먼저 들어갈지 모르겠다. 처음 들어가려고 할 때 어떤 생성규칙을 정할 것인가. 계속 만들어서 그 집합을 찾아냄. a가 nullable하면 FOLLOW도 포함시키자. ////////////////// 아래의 문법에서 FOLLOW를 구해보자 E -> TE' E' -> +TE' | ε T -> FT' T' -> *FT' | ε F -> (E) | id 일단 FOLLOW를 구하기 전에 FIRST를 모두 구해야 한다. FIRST(E) = { ( , id } FIRST(E') = { + , ε } FIRST(T) = { ( , id } FIRST(T') = { * , ε } FIRST(F) = { ( , id } FIRST를 모두 구했다면 FOLLOW를 구해질 준비를 마쳤다. FOLLOW에는 몇 가지 규칙이 있다. FOLLOW(X)를 기준으로 찾아보자. 첫 번째 규칙(처음으로 찾는 규칙)에는 집합에 시작 심벌($)를 추가해준다. 생성규칙의 왼쪽을 제외하고 모든 생성규칙의 오른쪽에서 X 뒤에 뭐가 오는지 찾아본다. 여러 개라면 찾아서 합집합을 해주면 된다. X뒤에 오는 게 terminal일 경우 -> 그 터미널을 FOLLOW(X) ={ } 집합에 넣어준다. X뒤에 오는 게 nonterminal일 경우 -> FIRST(X 뒤의 nonterminal) 그런데 FIRST(X 뒤의 nonterminal)에 ε가 있으면 ε를 지우고 그 찾았던 생성규칙의 맨 앞, 즉 생성규칙의 왼쪽에 있는 nonterminal, FOLLOW(nonterminal)을 추가시키면 된다. //만약에 FOLLOW(T') = FOLLOW(T')가 나온다면 공집합 처리를 해주면 된다. FIRST(X 뒤의 nonterminal)에 ε가 없으면 그냥 FIRST만 추가시키면 된다. X뒤에 오는 게 아무 것도 없을 경우 -> 그 생성규칙의 맨 앞, 즉, 생성규칙의 왼쪽에 있는 nonterminal, FOLLOW(nonterminal)을 추가시키면 된다. FOLLOW(E) 시작 심벌이므로 먼저 $를 포함한다. -> { $ } 시작심벌로부터 유도될 수 있는 모든 문장형태에서 E뒤에 나오는 terminal을 찾아야 하므로 5번에서 E뒤에 )가 있다. 끝. FOLLOW(E) = { $, ) } FOLLOW(T) (1번에서 )T는 자기 자신 뒤에 오는 terminal이 없고 비어 있으므로 FOLLOW(E) ⊆ FOLLOW(T)이다. Predictive 파서 문법이 바뀌더라도 파싱테이블만 재구성하면 된다. Initial configuration : stack, INPUT 23쪽. 둘이 같으면 pop해서 꺼낸다. 스택이니까 CBA의 순서로. 알고리즘. Yk부터...? 테이블 만드는 것. 30. 그렇다~ <8장 LR 구문 분석> 빨간색은 가장 중요한 것. 파란 색은 덜 중요한 것. 초록색은 그 다음으로 중요한 것. bottom up 파서이다. R하다. 규모가 크다. 파서의 아웃풋은 적용한 생성규칙의 번호가 파서다. LL파서는 좌파서를 내지만 LR은 우파서를 낸다. L은 INPUT에 대해서 왼쪽에서 오른쪽으로. 예를 들어 w : if (a > b) than ~~ 의 방향으로 점검한다. R은 LR파서가 매력적인 이유. 대부분의 프로그래밍 훨씬 더 일반적인 기법이다. 문법적인 오류가 있는지 찾는 것. as soon as possible. But, 너무 일이 많아서 손으로 LR파서를 구현하는 건 어렵다. 그래서 파서 제너레이터를 만든다. 그러면 어떻게 구성하냐. BNF, EBNF, syntax diagram. PGS 파싱테이블을 만들고 LR파서가 파싱테이블을 참조해서 output(1, 2, 3)한다. 드라이버 루틴은 lr 파서의 알고리즘 정해져있다. 그냥 파싱 테이블만 바뀌는 것. 왜 바뀔까. 자바 문법과 c문법과 다 다르니까. 파서가 다 다를 거 아니냐. 그래서 드라이버 루틴 ... 파싱 테이블을 어떻게 만들어 내기 위한 기술은 3가지가 있다. SLR 방법 - LR(0) item, FOLLOW를 갖고있으면 만들 수 있다~ CLR LALR 파싱테이블은 PGS에 맡기고 SAME하다. LR 파서의 구조 드라이버 루틴과 파싱테이블을 참조한다. 여기서 스택을 이용한다. Stack : S0X1S1... 스택의 탑 정보를 가지고 비교한다. 파싱 테이블을 가지고 한다. 터미널과 nonterminal을 가지고... Configuration 스택과 인풋을 가지고 한다. 스택속에는 state number와 등등... Input 데이터등이 들어있다. 왼쪽에서 오른쪽으로 스캔. Sm과 ai를 비교:? LR파싱 테이블(액션 테이블... Four Actions : 쉬프트 : 아직까지 reduce할 대상을 못 만났다. top에 계속 올림. 핸들을 만날 때까지 기다림 리듀스 : 줄여가는 과정. 리듀스 작업이 시작 심벌까지 왔을 때 에러거나 억셉트가 됨. 에러 -> 끝까지 다 살펴봤는데 없다.. LR 파싱 테이블. 어떤 상태번호로 넘어갈지... 스택의 상태가 Sm이고 ai를 만났을 때. 쉬프트 S를 함. S는 상태번호를 의미. 다음에 볼 상황 S도 넣고 SmaiS, 이렇게. 리듀스 A는 a와 |a|가 있다. 그 길이의 두 배에 해당하는 만큼을 차례로 끄집어 낸다. accept, 끝났다라는 얘기. error, the parser has discovered.. LR파서의 작동 원리. LR 파싱 예제 8.1 파싱 테이블을 이해할 수 있어야 하고 파싱 테이블을 만들 수 있어야 한다. PGS가 만들더라도 우리가 만들 수 있어야한다. Action table과 고테이블. List, ELEMENT. a, a 이렇게 만들어져 있다.~ w = a, a 초기 상태에는 0이라도 해도 좋지만 $라고 해도 좋다. 시작상태다. 0은. 인풋에서 a를 본다. 파싱테이블을 참조하자. s3가 되어있다. 아직 못 찾았다. 쉬프트한다. 스택의 top에 밀어넣겠다는 말. 3번 상태로 가라. 내가 본 a를 top에 넣는다. 3번도 탑에 집어넣는다. 3번 상태에서 a를 봤으니까 ,를 보니까 r3가 있다. 3번 생성규칙으로 reduce하라. element -> a이다. 리듀스를 만들면 줄여들여가라. 3번 생성 규칙. |r| = 1 크기의 2배만큼 빼내라. 2번으로 간다. 그래서 0 ELEMENT 2가 된다. 2번 상태에서 ,를 본다. ELEMENT의 ... LIST... 1번 그렇게 된 거예요. 1번 상태에서 , 를 봐야겠죠. s4로 되어있습니다. 쉬프트하고 4번으로 가는 겁니다. ,를 넣고 4로 이동합니다ㅏ. 그리고 다시 4번 상태에서 a를 보니까 쉬프트 3번이 된다. a를 집어넣고 다음 상태가 3번. 달라를 봐야된다. 달라는 r3. 3번 상태는 element -> a. 두 개를 없애야 된다. goto ???? 어떤 문법이 주어지면 파싱테이블이 주어지면 드라이버 루틴을 이용해 검증할 수 있다. 확인해 볼 수 있다. 그런데 문제는 파싱테이블을 어떻게 만드는지 모른다. 파싱테이블은 PGS가 만든다. PGS도 사람이 만든다. 3가지 SLR, CLR, LALR SLR을 빼고. 10쪽까지.