[0908] 1주차 요약
원래는 수업을 한 뒤에, 질의응답을 통해 학습을 진행하고, 구글폼을 통해 이해한 내용을 테스트 해 보는 것이었으나,
아직 과목에서 정식으로 진도를 나간 것이 없기때문에 튜터가 간단하게 수업을 하고 퀴즈를 푸는 형식으로 진행하였다.
<1주차 학습 내용>
- 어휘분석의 의미
- 정규 표현식
- 오토마타
- 어휘분석기와 파서의 관계
1. 어휘분석기
어휘란 token이라고도 불리며, 문법적으로 의미를 가진 최소단위이다.
이러한 어휘들을 '어휘'인 단위로 인식하여 분리하는 것이 '어휘 분석기'이다.
2. 정규 표현식
정규식은 문자열을 식으로 쓰는 것!이라고 생각하면 편하다. 이는 나중에 나오는 '오토마타'로 표현될 수 있다.
정규 표현식은 아래와 같은 규칙을 가진다.
예를 들어 아래와 같은 정규표현식과 나타낼 수 있는 문자열들은 오른쪽 문자열들과 같다.
마지막의 식은 2진수의 집합을 표현해낼 수 없다.
왜냐하면 1을 꼭 포함해야하기 때문에, 0을 표현할 수 없기때문이다.
그러므로 맞는 정규표현식은 0 | (0|1)* 인가......?(공백은 보기 편하라고 넣은 거임)
3. 오토마타
FSA(Finite State Automata, 유한 상태 오토마타) :
상태 간의 전이를 정의하며, 시작 상태와 끝 상태(여러개 가능)을 가진다
정규 표현식과 동일한 표현력을 가진다
상태 전이도로 나타낼 수 있다
DFA(Deterministic finite automata, 결정 유한 상태 오토마타) :
FSA의 한 종류이다
각 상태에서 나가는 edge가 레이블 문자에 의해 유일하게 '결정'된다
(각 상태마다 문자 'a'가 붙은 edge는 하나만)
토큰 인식은 정규표현식 -> NFA(non-DFA) -> DFA -> 인식
의 절차로 이루어진다.
1) 식별자의 인식
l은 letter이고, d는 digit이다.
2) 정수의 인식
이 때, '+'는 정규표현식에서 +가 의미를 가지기 때문에 구분하기 위함이다.
3) 실수의 인식
우와 복잡하다.
C의 상태에서 종료되는 것이 | 기준, 왼쪽의 정규표현식이고
E의 상태에서 종료되는 것이 오른쪽의 정규 표현식이다.
4) 스트링의 인식
" "에 있어야 스트링이며, *가 붙은 이유는 공백또한 스트링이기 때문이다.
4. 어휘분석기와 파서
파서는 '구문 분석기'이다.
위와 같은 단계로 실행된다.
(아직 구문분석기는 진도 X)