본문 바로가기
프로그래밍언어

[프로그래밍언어] 20가지 예제로 준비하는 기말고사 (1)

김치말이삼겹살 2024. 3. 25. 15:50
  1. 문자열 parsing 기본 컨셉
    1. Top-down 구문 분석: 시작 심벌로부터 유도 과정(production rule)을 거쳐 주어진 문자열과 같은 문장을 생성하기 위한 방법
    2. 일반적인 top-down 방식의 문제점: 입력 심벌을 반복해서 scan 하면서 구문 분석: 시간 ㅈㄴ 오래 걸림: 반복 scan 대신 결정적으로 parsing 할 수 있는 방법 요구됨
    3. 결정적으로 Top-down 파싱: LL parsing
    4. LL? Left to right scan + left parse 생성
    5. LL 조건을 만족하는 문법을 결정적으로 파싱할 수 있는 파서: Predictive Recursive Descent Parser
  2. BackTracking을 피하기 위해 할 수 있는 작업
    1. FIRST(): 컴파일러가 처음 나올 문자를 확인하기 위해 필요함!
    2. FOLLOW() : 컴파일러가 다음에 올 문자를 확인하기 위해 필요함!
      1. S가 starting symbol : FOLLOW(S)에 $ 추가
      2. B → aA일 때, FOLLOW(B)를 FOLLOW(A)에 추가
      3. B → aAC0C1C2…Ck 이고, e 가 FIRST(C0), FIRST(C1), … , FIRST(Ck)에 포함될 때 FOLLOW(B)를 FOLLOW(A)에 추가
      4. B → aAC0C1…Ck이면 FIRST(C0)-{e}를 FOLLOW(A)에 추가
      5. B → aAC0C1…CiCi+1…Ck 이고, e가 FIRST(C0), … , FIRST(Ci)에 포함된다면, FIRST(Ci+1) - {e}를 FOLLOW(A) 에 추가함
    예)A → CD | aAC → cC | eFIRST(S) = {a,c,d,b}FIRST(B) = {b}FIRST(D) = {d, e}INITIAL
    FOLLOW(S) {$} {$}
    FOLLOW(A) {b} {b}
    FOLLOW(B) {c,d,$} {c,d,$}
    FOLLOW(C) {$,d,b} {$,d,b}
    FOLLOW(D) {$,b} {$,b}
    FOLLOW(C)에서 b 가 추가된 이유가 뭘까?
  3. → A → CD 에서 FIRST(D)에 e가 포함되고, FOLLOW(A)에 b가 있었기 때문!
  4. FIRST(C) = {c, e}
  5. FIRST(A) = {a,e,c,d}
  6. D → dD | e
  7. B → b
  8. S → ABCD
  9. deterministic parsing 조건
    1. If A → a and A → b, then FIRST(a) 와 FIRST(b)의 교집합은 공집합
    2. → 이렇게 하지 않으면… deterministic한 top-down parsing을 할 수 없달까? ㅋ
    3. If e 가 FIRST(A)에 포함되면, FIRST(A) 와 FOLLOW(A)의 교집합은 공집합→ Deteministic Parsing Rule 증명 : 문자열 하나(e.g. “a” 생성) 생성 할 때 2가지 이상의 방법으로 도출
    4. → 결정적으로 파싱을 하기 위해서 하나의 문자열을 생성할 때 단 한가지 파싱 방법만 있어야 함
  10. Predictive Recursive Descent Parsers (Deterministic Parse Tree)
    1. CFG 생성
    2. FIRST와 FOLLOW set 구함
    3. CFG가 Predictive Recursive Descent Parser인지 증명 → RING SUM 사용
      1. RING SUM:
        1. if A에 e 포함되지 않으면 A RING SUM B = A
        2. if A에 e 포함되면 A RING SUM B = (A-{e}) UNION B
      2. LOOKAHEAD 사용
        1. 모든 production Rule 나열
        2. 모든 non-terminal에 대한 FIRST ,FOLLOW 구함
        3. 모든 production rule에 대한 LOOKAHEAD 를 구함
          1. 이때 LOOKAHEAD는 FIRST(production rule 오른쪽) RING SUM FOLLOW(production rule 왼쪽)
          예제)
          1. FIRST 및 FOLLOW 구하기
            1. FIRST(S) = {a, e, d ,b} , FIRST(A) = {d,b}, FIRST(B)={e}
            2. FOLLOW(S) = {$}, FOLLOW(A) = {c,$}, FOLLOW(B) = {d,b,$,c}
          2. LOOKAHEAD 구하기
            1. S → aBA : FIRST(aBA) RING SUM FOLLOW(S) = {a}
            2. S → BB : FIRST(BB) RING SUM FOLLOW(S) = {$}
            3. S → ABc : FIRST(ABc) RING SUM FOLLOW(S) = {d,b}
            4. A → dA : FIRST(dA) RING SUM FOLLOW(A) = {d}
            5. A → b : FIRST(b) RING SUM FOLLOW(A) = {b}
            6. B → e : FIRST(e) RING SUM FOLLOW(B) = {d,b,$,c}
          3. LL Parsing Table 생성
            1. 행에는 prodcution rule의 왼쪽에 해당하는 Non-terminal
            2. 열에는 Terminal Symbol
            Terminal Symbol
            Non-Terminal Symbol   a b c d $
              S S로부터 a가 나오는 LOOKUP        
            = S → aBA S → ABc   S → ABc S → BB    
              A   A → b   A → dA  
              B   B → e B → e B → e B → e
        4. S → aBA | BB | ABc, A → dA | b, B → e
    4. Stack 이용해서 유효한지 확인Terminal Symbol
      Non-Terminal Symbol   a b c d $
        S S로부터 a가 나오는 LOOKUP        
      = S → aBA S → ABc   S → ABc S → BB    
        A   A → b   A → dA  
        B   B → e B → e B → e B → e
      예제)Stack : 맨 뒤 요소가 stack pointer라고 하자
      • {$ , S} : d 를 뽑아야 하니까 S 를 pop 하고 ABc 를 stack에 넣음
      • {$, c , B ,A} : d 뽑아야겠지? A pop 하고 dA를 stack에 넣음
      • {$, c, B, A, d}: d pop
      • {$, c, B, A} : A pop하고 b 뽑기 위해 A pop하고 b넣음
      • {$, c, B, b} → ouput : {d,b}
      • {$ ,c, B}
      • {$ ,c, e} → ouptut: d,b
      • {$, c,}
      • {$, } → output: d,b,c
      • {} → output : d,b,c,$
    5. Input: dbc$
  11. Functional programing : 이거 어카믈,,,
    1. 자료형
      1. unit: C에서 void형
      2. int
        1. 단항 비트연산자: lnot
          1. lnot 3의 결과 → 011 → 111100 (2): -4 (sign-extended(
        2. 이항 비트연산자 : lsl, lsr, asl, asr, land, lor, lxor
          1. 2 asl 1;; 은 왜 error 가 나는가?
      3. float → int_of_float (float → int변환하는 함수), float_of_int (int → float 변환하는 함수)
        1. 타입 변환 필수
        2. float 사이의 연산 : +. 와 같이 .을 붙여줘야 함
      4. char
      5. string
      6. bool: 맞는지 틀리는지 문법 보면서 확인하기
        1. x = y vs. x == y
          1. x = y는 구조적으로 동일한지 확인
          2. x == y는 물리적으로 동일한지 확인 (같은 주소 공간을 공유하는 지 확인)
          e.g.) [1;2] = [1;2] : TRUE , [1,2]==[1,2] : FALSE
        2. x <> y vs. x!=y
          1. 전자는 구조적으로 다른지 확인
          2. 후자는 물리적으로 다른지 확인 (다른 주소 공간인지 확인)
    2. Statement vs. Expression
      1. Statement: 상태 전이; 값을 변경 가능, 값을 도출하지는 못함
        1. Statement-oriented: C, C++, Java, Python
      2. Expression: 값을 도출하지만 상태 전이(값 변경) 못함.
        1. expression-oriented: Haskell, Scala, Lisp
      → 메모리 리턴 여부로 판단
    3. Static types vs Dynamic Types
      1. 컴파일 시 타입 체킹이 이뤄지는지의 여부로 나눔
      2. Static type은 런타임 시 타입 에러가 발생하지 않아 안전함, but not flexible
      3. Dynamic type은 더 flexible한 언어 특징을 가지고 있음, but type errors appear at run-time
    4. 값이 bound되었다.
      1. let x = 3+ 4;; (expression의 리턴값이 변수에 할당됨; 변수의 값은 바뀔 수 없다)
반응형

'프로그래밍언어' 카테고리의 다른 글

[프로그래밍언어] 20가지 예제로 준비하는 기말고사 (2)  (0) 2024.03.25
[프로그래밍언어] 20가지 예제로 준비하는 중간고사 (3)  (0) 2024.03.25
[프로그래밍언어] 20가지 예제로 준비하는 중간고사 (2)  (0) 2024.03.25
[프로그래밍언어] 20가지 예제로 준비하는 중간고사 (1)  (0) 2024.03.25

'프로그래밍언어' Related Articles

티스토리툴바