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

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

김치말이삼겹살 2024. 3. 25. 15:42

 

  1. 유한 오토마타 (유한 집합 기계)
    • 유한 상태를 구성하는 추상적인 기계
    • 정규 표현식을 표현할 수 있다
    • 주어진 문자열이 언어 L에 부합하는지 체크할 수 있다
    e.g. Email address with lower cases only변환함수 생성법:
    • (q0,[a-z]) → q1, (q1,[a-z]) → q1 : [a-z]+ 표현
    • (q1,@) → q2 : @ 표현
    • (q2,[a-z]) → q3 , (q3,[a-z]) → q3 : [a-z]+ 표현
    • (q3, .) → q4 : . 표현
    • (q4, [a-z]) → q5, (q5, [a-z]) → q5 : [a-z]+ 표현
    시작 state: q0 , 종료 state: {q5}
    • Q : 유한한 상태 집합
    • $\Sigma$ : symbol의 집합
    • q : 시작 상태 (시작은 단 하나)
    • F : 종료 상태들의 집합
    • $\sigma$ : 변환 함수 : 상태와 알파벳의 조합 (Q* $\Sigma$ → Q)

    1. Given String: sungjaeh@skku.edu
    Cur_state Cur_index String[Cur_index]
    q0 0 s
    q1 1 u
    q1 2 n
    q1 3 g
    q1 4 j
    q1 5 a
    q1 6 e
    q1 7 h
    q1 8 @
    q2 9 s
    q3 10 k
    q3 11 k
    q3 12 u
    q3 13 .
    q4 14 e
    q5 15 d
    q5 16 u
      비교 후 17까지 증가!  
    Cur_state가 종료 state와 같은지 비교, length가 Cur_index와 같은지 비교
  2. FA(or FSM) = (Q, $\Sigma$, q, F, $\sigma$)
  3. [a-z]+@[a-z]+\.[a-z]+
  4. longest matching rule
    • next input symbol부터 시작해서 가장 긴 string을 찾기
    1.1abc1.2를 Longest Matching Prefix Rule을 적용해보셈string match potentioal longest match
    1.1abc1.2   ALL  
    1 num num,decimal num,1
    1.   decimal num,1
    1.1 decimal decimal decimal,3
    abc1.2   ALL  
    a id id id,1
    ab id id id,2
    abc id id id,3
    abc1 id id id,4
    .2   ALL  
    . dot (dot은 1개이므로 암것도 없음) dot,1
    2 num num num,1
    최종 결과: decimal, id, dot, num
  5. ambiguous grammar
    • 1 문장에서 여러 parse tree가 나오는 경우
      • Exp → Exp + Exp
      • Exp → Exp * Exp
      • Exp → NUM
    • 1 + 2 * 3 parse하는 경우
      • Exp → Exp * Exp → Exp + Exp * Exp → 1 + Exp * Exp → 1 + 2 * Exp → 1 + 2 * 3
      • Exp → Exp + Exp → 1 + Exp → 1 + Exp * Exp → 1 + 2* Exp → 1 + 2 * 3
       
  6. left recursion
    1. directterminal이 먼저 나오게 한다!A → $\beta$B
    2. B → $\alpha$B | $\epsilon$
    3. 그러면 $\beta\alpha*$ 가 나오겠지?
    4. A → A$\alpha$ | $\beta$
    5. indirectA → Ac|Sd|e
      1. indirect → direct로 변경A → Ac|Aad| bd|e
      2. A → Ac|(Aa | b)d|e
      3. direct → right recursion으로 변경경우의 수: bd로 시작, e로 시작
        • bdcccc….
        • bdadadad…
        • ecccccc…
        • eadadad….
        A →bdB|eB
      4. B → adB|cB|e
      5. 그다음에 c…., ad…. 붙는 식임!
      6. how? 우선 A 들어간 애들 제끼고 시작
    6. S → Aa | b
  7. left fatoring을 하는 이유
    1. left recursion이 일어나는 상황에서 일일히 backtracking 해야하는 과정을 공통의 부분으로 묶어두면 단계를 훨씬 줄여 효율성이 늘어남
    2. A → $\alpha$$\beta$ | $\alpha\gamma$ < = > A → $\alpha$($\beta|\gamma)$
    3. A → $\alpha$B, B→ $\beta|\gamma$랴
  8. First(alpha)
    1. 법칙을 다 외우고 있을 필요는 없지만, 시험 시간은 촉박하다!
    2. 때문에 rule의 concept은 잡고 가야 시험에 유리
    3. FIRST() set

  1. x가 terminal일 경우, FIRST(x) = {x}
  2. First(e) = {e}
  3. A → B$\alpha$ 가 production rule이라면, FIRST(A)에 FIRST(B) - {e}를 추가해라!
  4. A → B0B1B2…Bi..Bi+1..Bk 이고 Bi까지 모두 e를 포함하고 있으면 first(Bi+1)-e를 first(A)에 추가해라!
  5. A → b0b1b2…bk이고 b0부터 bk까지 e를 포함하면 e를 first(A)에 추가해라!

Rules

S → ABCD

A → CD | aA

B → b

C → cC | e

D → dD | e

  1. 유한 오토마타 (유한 집합 기계)
    • 유한 상태를 구성하는 추상적인 기계
    • 정규 표현식을 표현할 수 있다
    • 주어진 문자열이 언어 L에 부합하는지 체크할 수 있다
    e.g. Email address with lower cases only변환함수 생성법:
    • (q0,[a-z]) → q1, (q1,[a-z]) → q1 : [a-z]+ 표현
    • (q1,@) → q2 : @ 표현
    • (q2,[a-z]) → q3 , (q3,[a-z]) → q3 : [a-z]+ 표현
    • (q3, .) → q4 : . 표현
    • (q4, [a-z]) → q5, (q5, [a-z]) → q5 : [a-z]+ 표현
    시작 state: q0 , 종료 state: {q5}
    • Q : 유한한 상태 집합
    • $\Sigma$ : symbol의 집합
    • q : 시작 상태 (시작은 단 하나)
    • F : 종료 상태들의 집합
    • $\sigma$ : 변환 함수 : 상태와 알파벳의 조합 (Q* $\Sigma$ → Q)
    1. Given String: sungjaeh@skku.edu
    Cur_state Cur_index String[Cur_index]
    q0 0 s
    q1 1 u
    q1 2 n
    q1 3 g
    q1 4 j
    q1 5 a
    q1 6 e
    q1 7 h
    q1 8 @
    q2 9 s
    q3 10 k
    q3 11 k
    q3 12 u
    q3 13 .
    q4 14 e
    q5 15 d
    q5 16 u
      비교 후 17까지 증가!  
    Cur_state가 종료 state와 같은지 비교, length가 Cur_index와 같은지 비교
  2. FA(or FSM) = (Q, $\Sigma$, q, F, $\sigma$)
  3. [a-z]+@[a-z]+\.[a-z]+
  4. longest matching rule
    • next input symbol부터 시작해서 가장 긴 string을 찾기
    1.1abc1.2를 Longest Matching Prefix Rule을 적용해보셈string match potentioal longest match
    1.1abc1.2   ALL  
    1 num num,decimal num,1
    1.   decimal num,1
    1.1 decimal decimal decimal,3
    abc1.2   ALL  
    a id id id,1
    ab id id id,2
    abc id id id,3
    abc1 id id id,4
    .2   ALL  
    . dot (dot은 1개이므로 암것도 없음) dot,1
    2 num num num,1
    최종 결과: decimal, id, dot, num
  5. ambiguous grammar
    • 1 문장에서 여러 parse tree가 나오는 경우
      • Exp → Exp + Exp
      • Exp → Exp * Exp
      • Exp → NUM
    • 1 + 2 * 3 parse하는 경우
      • Exp → Exp * Exp → Exp + Exp * Exp → 1 + Exp * Exp → 1 + 2 * Exp → 1 + 2 * 3
      • Exp → Exp + Exp → 1 + Exp → 1 + Exp * Exp → 1 + 2* Exp → 1 + 2 * 3
  6. left recursion
    1. directterminal이 먼저 나오게 한다!A → $\beta$B
    2. B → $\alpha$B | $\epsilon$
    3. 그러면 $\beta\alpha*$ 가 나오겠지?
    4. A → A$\alpha$ | $\beta$
    5. indirectA → Ac|Sd|e
      1. indirect → direct로 변경A → Ac|Aad| bd|e
      2. A → Ac|(Aa | b)d|e
      3. direct → right recursion으로 변경경우의 수: bd로 시작, e로 시작
        • bdcccc….
        • bdadadad…
        • ecccccc…
        • eadadad….
        A →bdB|eB
      4. B → adB|cB|e
      5. 그다음에 c…., ad…. 붙는 식임!
      6. how? 우선 A 들어간 애들 제끼고 시작
    6. S → Aa | b
  7. left fatoring을 하는 이유
    1. left recursion이 일어나는 상황에서 일일히 backtracking 해야하는 과정을 공통의 부분으로 묶어두면 단계를 훨씬 줄여 효율성이 늘어남
    2. A → $\alpha$$\beta$ | $\alpha\gamma$ < = > A → $\alpha$($\beta|\gamma)$
    3. A → $\alpha$B, B→ $\beta|\gamma$랴
  8. First(alpha)
    1. 법칙을 다 외우고 있을 필요는 없지만, 시험 시간은 촉박하다!
    2. 때문에 rule의 concept은 잡고 가야 시험에 유리
    3. FIRST() set
  1. x가 terminal일 경우, FIRST(x) = {x}
  2. First(e) = {e}
  3. A → B$\alpha$ 가 production rule이라면, FIRST(A)에 FIRST(B) - {e}를 추가해라!
  4. A → B0B1B2…Bi..Bi+1..Bk 이고 Bi까지 모두 e를 포함하고 있으면 first(Bi+1)-e를 first(A)에 추가해라!
  5. A → b0b1b2…bk이고 b0부터 bk까지 e를 포함하면 e를 first(A)에 추가해라!

Rules

S → ABCD

A → CD | aA

B → b

C → cC | e

D → dD | e

  1. 유한 오토마타 (유한 집합 기계)
    • 유한 상태를 구성하는 추상적인 기계
    • 정규 표현식을 표현할 수 있다
    • 주어진 문자열이 언어 L에 부합하는지 체크할 수 있다
    e.g. Email address with lower cases only변환함수 생성법:
    • (q0,[a-z]) → q1, (q1,[a-z]) → q1 : [a-z]+ 표현
    • (q1,@) → q2 : @ 표현
    • (q2,[a-z]) → q3 , (q3,[a-z]) → q3 : [a-z]+ 표현
    • (q3, .) → q4 : . 표현
    • (q4, [a-z]) → q5, (q5, [a-z]) → q5 : [a-z]+ 표현
    시작 state: q0 , 종료 state: {q5}
    • Q : 유한한 상태 집합
    • $\Sigma$ : symbol의 집합
    • q : 시작 상태 (시작은 단 하나)
    • F : 종료 상태들의 집합
    • $\sigma$ : 변환 함수 : 상태와 알파벳의 조합 (Q* $\Sigma$ → Q)
    1. Given String: sungjaeh@skku.edu
    Cur_state Cur_index String[Cur_index]
    q0 0 s
    q1 1 u
    q1 2 n
    q1 3 g
    q1 4 j
    q1 5 a
    q1 6 e
    q1 7 h
    q1 8 @
    q2 9 s
    q3 10 k
    q3 11 k
    q3 12 u
    q3 13 .
    q4 14 e
    q5 15 d
    q5 16 u
      비교 후 17까지 증가!  
    Cur_state가 종료 state와 같은지 비교, length가 Cur_index와 같은지 비교
  2. FA(or FSM) = (Q, $\Sigma$, q, F, $\sigma$)
  3. [a-z]+@[a-z]+\.[a-z]+
  4. longest matching rule
    • next input symbol부터 시작해서 가장 긴 string을 찾기
    1.1abc1.2를 Longest Matching Prefix Rule을 적용해보셈string match potentioal longest match
    1.1abc1.2   ALL  
    1 num num,decimal num,1
    1.   decimal num,1
    1.1 decimal decimal decimal,3
    abc1.2   ALL  
    a id id id,1
    ab id id id,2
    abc id id id,3
    abc1 id id id,4
    .2   ALL  
    . dot (dot은 1개이므로 암것도 없음) dot,1
    2 num num num,1
    최종 결과: decimal, id, dot, num
  5. ambiguous grammar
    • 1 문장에서 여러 parse tree가 나오는 경우
      • Exp → Exp + Exp
      • Exp → Exp * Exp
      • Exp → NUM
    • 1 + 2 * 3 parse하는 경우
      • Exp → Exp * Exp → Exp + Exp * Exp → 1 + Exp * Exp → 1 + 2 * Exp → 1 + 2 * 3
      • Exp → Exp + Exp → 1 + Exp → 1 + Exp * Exp → 1 + 2* Exp → 1 + 2 * 3
  6. left recursion
    1. directterminal이 먼저 나오게 한다!A → $\beta$B
    2. B → $\alpha$B | $\epsilon$
    3. 그러면 $\beta\alpha*$ 가 나오겠지?
    4. A → A$\alpha$ | $\beta$
    5. indirectA → Ac|Sd|e
      1. indirect → direct로 변경A → Ac|Aad| bd|e
      2. A → Ac|(Aa | b)d|e
      3. direct → right recursion으로 변경경우의 수: bd로 시작, e로 시작
        • bdcccc….
        • bdadadad…
        • ecccccc…
        • eadadad….
        A →bdB|eB
      4. B → adB|cB|e
      5. 그다음에 c…., ad…. 붙는 식임!
      6. how? 우선 A 들어간 애들 제끼고 시작
    6. S → Aa | b
  7. left fatoring을 하는 이유
    1. left recursion이 일어나는 상황에서 일일히 backtracking 해야하는 과정을 공통의 부분으로 묶어두면 단계를 훨씬 줄여 효율성이 늘어남
    2. A → $\alpha$$\beta$ | $\alpha\gamma$ < = > A → $\alpha$($\beta|\gamma)$
    3. A → $\alpha$B, B→ $\beta|\gamma$랴
  8. First(alpha)
    1. 법칙을 다 외우고 있을 필요는 없지만, 시험 시간은 촉박하다!
    2. 때문에 rule의 concept은 잡고 가야 시험에 유리
    3. FIRST() set
  1. x가 terminal일 경우, FIRST(x) = {x}
  2. First(e) = {e}
  3. A → B$\alpha$ 가 production rule이라면, FIRST(A)에 FIRST(B) - {e}를 추가해라!
  4. A → B0B1B2…Bi..Bi+1..Bk 이고 Bi까지 모두 e를 포함하고 있으면 first(Bi+1)-e를 first(A)에 추가해라!
  5. A → b0b1b2…bk이고 b0부터 bk까지 e를 포함하면 e를 first(A)에 추가해라!

Rules

S → ABCD

A → CD | aA

B → b

C → cC | e

D → dD | e

반응형

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

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

'프로그래밍언어' Related Articles

티스토리툴바