4주차 - 4장 Lexival ans Syntax Analysis

0323 → 랙시컬 분석기를 왜 나눠야하는지, 랙시컬 분석기에 대한 기념

RD 파서 -> bnf 그대로 구현
그대로 하면 속도가 느려짐
속도 빠르기 위해서 테이블을 만듦

테이블 -> 빠른 파서 -> LL 파서, LR 파서

소스코드 -> 파스트리 : 신텍스 분석
신텍스의 앞단 -> 렉시컬 : 모듈을 만드로 쪼갬

Lexical 분석과 Syntax분석을 분리하는 이유

1. 간결성: Lexical Analysis과 Syntax Analysis를 구분하여 수행함으로써, 각각의 과정이 서로 다른 역할을 수행하도록 구분하여, 이해하기 쉽고 간결한 코드를 작성할 수 있습니다.
2. 효율성: Lexical Analysis과 Syntax Analysis를 병렬 처리하면, 컴파일 속도를 높일 수 있으며, 각각의 과정이 빠르고 효율적으로 수행될 수 있도록 최적화된 알고리즘을 적용할 수 있습니다.
3. 범용성: Lexical Analysis과 Syntax Analysis를 모듈화하여, 다른 언어나 다른 컴파일러에서 재사용이 가능하도록 설계함으로써, 범용성이 높은 코드를 작성할 수 있습니다.

목적: 이식성. 포터빌리티
입력 파스트리 -> 결과 파스트리
bnf 기분으로 옳은지 판단

입력 i/o 부분 계속 바뀜.

포터빌리티에 영향을 미치는 렉시컬만 앞으로 떼어서 분리하고 뒤는 그대로 신텍스 분석 함

단순하게 만들면 ,이퓨전시 올라가고 옾티마이즈도 잘 할 수 ㅣㅇㅆ음 (장점)

렉시컬 분ㄴ석
입력 : 스트링(문자열 ) -> 패턴매칭 ->

랙시컬 분석기를 만드는 방법

1. 패턴만 주면 SW tool을 통해서 자동으로 렉시컬 분석을 해줌 (비용 든다
2. 패턴 매칭을 위한 state diagram 만들기

   1. state diagram을 있는 그대로 코드로 변환한다

      (문제) state가 너무 많아지면 소스코드가 졸라 길어진다

      HW든 SW든 state를 묶을 수 있는 만큼 묶는게 효율적이다

      0,1,2,3, … 각각의 숫자가 다른 의미를 가진다면 각각의 state를 만들어 주는게 맞지만, 그게 아니라

      숫자는 그저 숫자이고 문자는 그저 문자라면 숫자 state, 문자 state 이런식으로 묶어서 만드는게 유리하다!
      ⇒ state 가 굳이 많을 필요 없다! 오히려 줄어드는게 유리함!!

3. state diagram을 만그리고 state diagram을 압축할 수 있는 테이블을 만든다
   1. 테이블을 기반으로 조금 더 속도가 빠른 랙시컬 분석기를 만들 수 있다.

⇒ 일반적으로 사용되는건 1,3번이지만, 교재와 우리가 할 수 있는건 2번이다. state diagram 을 그려봅시다

0328 →

• left-most derivation 왼쪽에서부터 파생되는(left-most derivation)는 형식 문법에서 새로운 문자열을 생성하기 위해 사용되는 파생 방법 중 하나입니다. 이 방법은 시작 기호에서부터 왼쪽으로 가면서 생성된 문자열을 차례대로 치환하는 방식입니다. 예를 들어, 다음과 같은 문법이 있다고 가정해 봅시다:

  S → Aa | Bb
  A → cA | d
  B → cB | e
  

  이 문법에서 S가 시작 기호이며, a, b, c, d, e는 터미널 기호입니다. 이제 S에서 시작하여 왼쪽에서부터 파생되는 방식으로 문자열 ccdab를 생성해 보겠습니다.

  1. S → Bb (S에서 Bb로 치환)

  2. B → cB (B에서 cB로 치환)

  3. cB → ccB (cB에서 ccB로 치환)

  4. ccB → ccdB (ccB에서 ccdB로 치환)

     ccB에서 ccdB로 치환하는 부분이 이해가 어려웠던 것 같아요. 제가 다시 한번 설명해드릴게요.

     B는 cB 또는 e로 치환할 수 있습니다. 그리고 ccB에서 B를 치환했으므로, ccB에서도 cB 또는 e로 치환할 수 있습니다.

     그런데 ccdab 문자열을 생성하는 과정에서는 B가 e로 치환될 일이 없었으므로, ccB에서는 반드시 cB로 치환되어야 합니다. 그래서 ccB에서 cB로 치환하게 됩니다.

     이렇게 ccB에서 cB로 치환한 후, 이어서 cB가 cBb와 ccBb에서 다시 치환되는 과정을 통해 ccdBb 문자열을 생성합니다.

  5. ccdB → ccdA (ccdB에서 ccdA로 치환)

  6. ccdA → ccdacA (ccdA에서 ccdacA로 치환)

  7. ccdacA → ccdacd (ccdacA에서 ccdacd로 치환)

  8. S → Bb → cB → ccB → ccdB → ccdA → ccdacA → ccdacd (최종 결과)

     이렇게 왼쪽에서부터 파생되는 방식으로 문법을 사용하여 문자열을 생성할 수 있습니다.

파서의 목적

0330 녹강

• LR 파서에 대해서