본문 바로가기
반응형

Computer

중지계산 (short-circuit evaluation) Bool 식의 값을 왼쪽에서 오른쪽으로 계산하는 도중 나머지 부분을 계산하지 않아도 식의 값이 결정되는 경우 더 이상 그 식의 나머지 부분을 계산하지 않고 값을 결정하는 기능 더보기
매개변수 전달방식 실 매개변수를 형식 매개변수에 바인딩할 때, 형식 매개변수가 실 매개변수의 값/주소/이름을 전달받을 수 있는데, 이에 따른 분류. 1. 값에 의한 전달 실 매개변수의 값이 형식 매개변수의 값으로 복사되고, 형식 매개변수는 부프로그램의 지역변수처럼 사용된다. 2. 결과에 의한 전달 값에 의한 전달의 역 개념. 부프로그램의 종료시점 : 형식 매개변수의 값이 실 매개변수로 전달됨. 단점 : 같은 이름의 변수가 실 매개변수로 주어지고, 이것이 서로 다른 형식 매개변수에 바인딩되는 경우 문제가 발생할 수 있다.(모호성 문제) 3. 값-결과에 의한 전달 부프로그램의 시작시점 : 실 매개변수의 값이 형식 매개변수로 전달됨 부프로그램의 종료시점 : 형식 매개변수의 값이 실 매개변수로 전달됨 4. 주소에 의한 전달 실 .. 더보기
장치관리 ( Device Management ) 장치의 범주 - 전용장치(dedicated devices) 한 번에 단지 하나의 작업에만 할당된다. - 공유장치(shared devices) 여러 프로세스에 할당된다. 요구를 인터리빙(Interleaving). - 가상장치(virtual devices) 전용장치와 공유장치의 조합. 스풀링(Spooling). 순차접근 저장장치 테이프 장치에서 레코드간 이동시에 헤드가 멈출 시간(IRG:InterRecord Gap)이 필요함. - 전송률(transfer rate) = 밀도(density) X 전송속도(transport speed) 직접접근 저장장치 드럼, 디스크 등의 임의접근저장장치(random access storage devices). - 고정헤드방식 접근시간(access time) = 회전지연시간(se.. 더보기
푸시다운 오토마타 ( Push-Down Automata ) 푸시다운 오토마타의 7개 구성요소 M=(Q, Σ, T, δ, q0, z0, F) Q : 상태들의 유한집합 Σ : 입력기호들의 유한집합 T : 스택기호들의 유한집합 δ : 전이함수 Q X (∑∪{ε}) X T -> Q X T* q0 ∈ Q : 시작(start state)상태 z0 ∈ T: 스택의 시작기호 F ⊆ Q : 종결상태(final state)의 집합 전이함수δ (q,a,z) = {(p1,r1),(p2,r2),...,(pm,rm)}에서 - m = 1 이면 결정적 푸시다운 오토마타(DPDA:Deterministic Push-Down Automata) - m ≥ 2 이면 비결정적 푸시다운 오토마타(NPDA:Non-Deterministic Push-Down Automata) 더보기
Left-Recursion - Immediate Left-Recursion : A -> Aα 형태의 생성규칙 - Indirect Left-Recursion : A =(+)=> Aα 형태의 유도과정이 존재하는 경우 문제점 Top-Down구문분석시, 같은 생성규칙이 반복 적용되어 무한루프 제거방법 right-recursion으로 변환함 더보기
Left-Factoring 같은 기호들을 prefix로 갖는 2개 이상의 생성규칙이 존재할 경우, 공통된 prefix를 인수분해하는 것을 left-factoring이라고 한다. 구문분석기가 어떤 생성규칙을 적용해야할 지 결정할 수 없어서, 규칙의 선택값을 순차적으로 재시도하게 되는 현상(backtracking)을 방지하기 위해서 left-factoring을 수행한다. 입력 : 문법 G 출력 : 동일한 left-factoring된 문법 방법 begin repeat Find the production A -> αβ1|αβ2||...|αβn|γ (*γ는 문자열*) Find the longest prefix α ; If α ≠ ε then replace all tha A -> αβ1|αβ2||...|αβn|γ by A -> αA'|γ A.. 더보기
단일 생성규칙 (single production) 제거 단일생성규칙(single production, unit production) 오른편이 단 하나의 Non-Terminal로 구성되는 생성규칙을 말한다.CFG G(VN, VT, P, S)가 어떤 A∈ VN에 대하여 A=(+)=>A형태의 유도과정을 가지지 않을 때, cycle-free라고 하며, 만약 G가 cycle-free이며, ε-free, 그리고 불필요한 기호를 가지지 않으면 그 문법은 proper하다고 한다. 제거방법 오른편에 Non-terminal 기호가 한개만 나오는 생성규칙을 찾아서, 그 자리를 다른 생성규칙들로 대체함으로써 제거한다. 더보기
ε(epsilon)-생성규칙 제거 ε-생성규칙을 제거하는 방법은 간단하다. 모든 S에 ε을 대입하면 된다. CFG G=(VN,VT,P,S)가 다음 중 한 가지 조건만을 만족할 경우에 ε-free문법이라고 한다 1. P가 생성규칙을 갖지 않는다. 2. 시작기호 S만이 S->ε 인 ε생성규칙을 가질 경우, 다른 생성규칙의 오른쪽에 S가 나타나지 않는다. 더보기
반응형

티스토리툴바