Lec02. Lexical Anaylsis(1) (1주차 2강)

1주차 2강 - 9월 4일 수요일, Lexical Analysis(1) Specification of Tokens

* 연관 단원: CPTT Ch3.3

* 제 개인 공부용으로 정리하는 글입니다.

* 정확한 내용은 꼭 본인이 공부하는 교재를 확인하시길 바랍니다.

 

1. Roadmap for Building a Lexical Analyzer

- Specification: valid lexeme pattern을 어떻게 표현할 것인가?

    ex) C언어에서 가능한 변수 선언은 x, xy, match0, _abc 등

    -> 이걸 정의하는 것을 regular expression이라고 함!

- Recognition: valid lexical pattern을 어떻게 accept할건가? invalid lexical pattern을 어떻게 reject할건가?

   ex) C언어에서 match0은 accept, 0match는 reject

   -> 이걸 deterministic finite automata(DFA)라고 함 (오토마타 개념의 등장 ㅎㅅㅎ)

- Implementation: string recognizer를 어떻게 구현할 것인가?

   -> Thompson's construction, subset construction

 

2. Specification of Tokens: 이번 강의에서는 token에 대해 자세히 알아본다

- Regualr Expresison을 정의하기 위해 알아야 할 것: alphabets, strings, languages

- Regular Expression의 Syntax(문법)와 Semantics(의미)

- Regular Expresison을 간단하게 표현하기 위해 확장에 대해 알아본다

 

3. Preliminary: 정규 표현식을 알기 전에 알아야 할 것

3.1. Alphabet 

- alphabet ∑는 finite(유한), non-empty인 symbol의 set이다.

- ∑ = {0,1} 는 binary alphabet, ∑ = {A,B,...,Z}는 English alphabet

   우리가 생각하는 그 알파벳이 아니라 정규표현식을 나타낼 수 있는 문자의 종류와 그 묶음을 말하는 듯

- 실제 예시: ASCII, Unicode

 

3.2. String (Sentence, Word)

- String: alphabet set의 symbol로 만든 finite sequence

   ex) 1, 01, 10110은 ∑ = {0,1}의 string임

- string notation(표기법)

   -  ε: empty string

   - wv: w와 w의 concatenation(연속)

     ex) w = dog, v = house, wv = doghouse

     ex) empty string과 어떤 문자열을 concatenation해도 원래 문자열과 같다

           어떤 문자열 s에 대해 s, εs = sε = s

   - | w | : string w의 길이

     | ε | = 0, |sa|=|s|+1 for some a∈∑

   - exponentiation(power): concatenation을 지수승으로 표현할 수 있음

 

3.3. Language

- language L: some alphabet ∑으로 만들어진 string의 subset

- Union(합집합):  두 언어 중 적어도 하나에 속하는 모든 문자열의 집합

  L1 ∪ L2 = {x | x ∈ L1 ∨ x ∈ L2}

- Concatenation(연결): L1의 각 문자열과 L2의 각 문자열을 연결하여 얻은 모든 문자열의 집합

  L1L2 = {xy | x ∈ L1 ∧ y ∈ L2}

- Power(거듭제곱): 

• L0: 빈 문자열 {ϵ}만 포함하는 집합
• Ln: 언어 L을 n번 연결한 집합
  • L^0 = { ε }
  • L^n = L^(n-1)L

- Kleene Colsure 클리니 폐쇄: L^*, L을 0번 이상 연결한 모든 문자열의 집합. 빈 문자열을 포함한다!

- Positive Closure of a language L, L^+: L을 1번 이상 연결한 모든 문자열의 집합. 빈 문자열을 포함 안한다!

 

 

4. Regular Expresison

- 드디어 정규표현식: 특정 유형의 language를 표현하기 위해 정의된다

- Syntax(문법)이 inductive(귀납적)으로 정의된다->base case에서 더 복잡한 case로 나아감

- base case: primitive(초기의) regular expression을 정의한다

• ∅: 빈 집합을 의미하는 표현식
• ϵ: 빈 문자열을 의미하는 표현식
• a (여기서 a는 알파벳 Σ의 원소): 단일 문자 a를 의미하는 표현식

 

- Inductive cases: 작은 것 부터 큰 regular expression으로 나아가며 정의한다

 

• R1 | R2: R1 또는 R2를 의미. 이는 두 정규 표현식 중 하나를 선택하는 경우.
• R1 · R2: R1의 문자열 뒤에 R2의 문자열이 오는 것을 의미. 즉, 두 정규 표현식을 연결.
• R1*: R1의 문자열을 0번 이상 반복. 즉, R1의 클리니 폐쇄를 나타냄.
• (R): 괄호로 묶인 R은 R 자체를 의미. 괄호는 우선순위를 명확히 하기 위해 사용.

 

- Semantics(meaning): inductively(귀납적)으로 정의

 

• L(∅)= ∅ : 빈 집합. 어떤 문자열도 포함하지 않음.
• L(ϵ)={ ϵ }: 빈 문자열 {ϵ}만 포함하는 집합.
• L(a)={a}: 문자 a만 포함하는 집합. 예를 들어, a라는 문자열만 포함하는 경우.
• L(R1 | R2)=L(R1) ∪ L(R2): R1 또는 R2로 표현되는 언어의 집합. 즉, L(R1)과 L(R2)의 합집합.
• L(R1 · R2)=L(R1)L(R2): R1의 문자열과 R2의 문자열을 연결하여 얻은 문자열들의 집합. 즉, L(R1)과 L(R2)의 연결.
• L(R∗)=(L(R))*: R의 문자열을 0번 이상 반복하여 얻은 모든 문자열의 집합. 즉, L(R)의 클리니 폐쇄.
• L((R))=L(R): 괄호로 묶인 R과 같은 의미를 가짐. 괄호는 우선순위를 명확히 하기 위한 것

- 예시

 

가장 바깥 괄호부터 순서대로 풀어나가면 됨

 

- 예제

 

• a · a는 두 개의 a를 연결한 것, 즉 aa.
• (a · a)*는 aa를 0번 이상 반복하는 것을 의미.
  • ϵ  , aa, aaaa, aaaaaaaa 등이 포함됨

 

 

5. Regular Definitions

• 정규 표현식의 표현을 간편하게 하기 위해 사용함
• 정규 표현식에 이름을 부여하고, 이후 표현식에서 이 이름을 대신 사용해서 복잡한 걸 간단하게 나타냄
• 정규 표현식의 구조

d1 → r1
d2 → r2
...
dn → rn

 

• di는 새로운 이름이며, 알파벳 Σ의 원소가 아님.
  • d1 → a*와 d2 → b라는 정의가 있을 때, d3는 d1 · d2와 같이 이전 정의들을 사용할 수 있음
• ri는 정규 표현식, Σ와 이전에 정의된 Regular Definition(d1, d2, ..., di-1)을 조합해서 구성할 수 있음

• 예시: 정수 또는 실수 표현하기
  
  • digit: 하나의 숫자 0~9
  • digits: 하나 이상의 숫자 digit digit*
  • optionalFraciton: 소수점 이하 부분: 없거나 소수점과 숫자들이 있거나, .(소수점) digits | ϵ
  • optionalExponent: 지수 부분: (E (+ | - | ϵ) digits) | ϵ
    • E: 지수 부분의 시작. 예를 들어, 6.336E4에서 E4가 지수 부분
    • (+ | - | ϵ): 지수 부분에 대한 부호. + 또는 -가 있을 수 있으며, 부호가 없을 수도 있음
    • digits: 지수 부분에서의 숫자들. 예를 들어, E4에서 4를 의미
    • ϵ: 지수 부분이 없는 경우
  • number: 전체 숫자 표현: digits optionalFraction optionalExponent

6. Extensions of Regular Expressions

• 정규 표현식을 더 간결하게 만들어줌
  • R+: 정규 표현식 R의 positive 클리니 폐쇄를 나타냄.
    • 정의: L(R+) = L(R)+
    • 의미: R의 문자열이 1번 이상 반복되는 모든 문자열을 포함함
    • 예시: a+는 a가 1회 이상 반복되는 문자열을 의미합니다. a, aa, aaa, aaaa 등
  • R?: 정규 표현식 R의 optional 패턴을 나타냅니다.
    • 정의: L(R?) = L(R) ∪ {ϵ}
    • 의미: R의 문자열이 0회 또는 1회 나타날 수 있는 경우를 의미. R이 없거나 R이 한 번 나타나는 경우 포함.
    • 예시: a?는 빈 문자열(ϵ) 또는 a를 의미함.
  • Character Classes: 특정 범위나 집합의 문자들을 정의하는 데 사용
    • [a1a2..an] = a1|a2|...|an의 간단한 표현
    • [a1-an] = [a1a2..an]의 간단한 표현 (a1~an이 consecutive symbol인 경우)
      • [abc] = a|b|c
      • [a-z] = a|b|...|z
  • 예시

7. 요약

• valid lexeme pattern을 표현하는 방법을 배움(lexical analyzer의 valid input을 정의)
  • regular expression의 기초, alphabets, strings, languages를 배움
  • regular expression의 syntax, semantics
  • regular expression을 간소화하기 위한 확장법
• 다음시간: finite automata for accepting the valid lexical patterns

 

작성 시작 24.09.07. 22:27

작성 종료 24.09.07. 23:39

수강 일자 24.09.04. 1주차 2강

 

작성 노동요...는 어떤 유튜버의 팬게임 ost 모음..