본문 바로가기
반응형

컴퓨터

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가 나타나지 않는다. 더보기
모호성 (Ambiguity), 모호한 문법 (Ambiguous Grammer) 모호한 문법(Ambiguous Grammer) 동일한 문자열에 대하여 상이한 분석나무가 나타날 수 있는 문법 모호한 문법은 모호하지 않은 동등한 문법으로 바꿀 수 있으나, 모든 경우에 그러하지는 않다. 모호성 제거 연산에 우선순위를 부여하거나 모호성 제거규칙을 만든다. 연산우선순위만으로는 모호하지 않은 문법을 만들 수 없고, 결합법칙(associativity)을 사용함 결합법칙(associativity) 연산자의 우선순위가 같은 경우에 왼쪽에서 오른쪽으로 계산할지(좌측결합,left associative), 오른쪽에서 왼쪽으로 계산(우측결합,right associative)할지를 결정하는 규칙. 하나의 context-free언어를 생성하는 모든 문법이 모호하다면, 이 언어를 본질적으로 모호하다(inhere.. 더보기
파일관리 시스템 ( File Management System ) 파일관리 시스템의 요소 - 액세스방식 : 저장되어 있는 데이터에 접근하는 방식 - 파일관리 : 파일을 저장,참조,공유할 수 있는 기법을 제공 - 보조기억장치관리 : 저장공간 할당 등을 관리 - 파일 무결성 유지 : 파일의 정보가 소실되지 않도록 보장함 파일관리 시스템의 기능 - 사용자간 전송/공유(판독,기록,수행), 백업 및 복구, 기호화된 이름 사용, 장치독립성, 암호화와 해독, 사용자 인터페이스, 파일 생성/수정/제거 등 블록킹(Blocking) - 물리적 레코드(Physical record) : 블록(Block). 장치에 출력되거나 입력되는 실제 정보의 단위 - 논리적 레코드(Logical record) : 사용자 관점에서 한 단위로 취급되는 자료의 단위 - 블로킹되지 않은 레코드 : 물리적 레코드.. 더보기
CISC와 RISC(Complex / Reduced Instruction Set Computer) 복합 명령어 세트 컴퓨터(CISC : Complex Instruction Set Computer) 고급언어 동작을 지원하는 하드웨어를 제공하기 때문에 간결한 프로그래밍이 가능하다. CISC 아키텍쳐(architecture)는 프로그래밍 언어에서 사용하는 연산기능에 더 가깝도록 하면서 프로그램 규모를 작게 하며 기억장치를 줄이도록 하는 명령어를 갖고 있다. 성능상의 효율은 RISC에서의 기본연산만 할 경우와 비교할 때 기억장치에서 가져오는 명령어 수가 줄어들기 때문에 향상된다. - 특징 ① 대부분의 명령어는 직접적으로 기억장치 액세스를 할 수 있다. ② 주소지정방식의 수가 상당히 많다. ③ 명령어 포맷은 여러 개의 길이를 갖는다. ④ 명령어는 기본적인 연산과 복잡한 연산을 모두 수행한다. 단축 명령어 세트.. 더보기
교착상태 탐지 교착상태 탐지를 위해 필요한 기능 - 현재 자원의 할당상태에 관한 정보 관리 - 이 상태정보에 의해 교착상태인지 여부를 판단할 수 있는 알고리즘 각 자원의 유형이 여러 개일 경우 - 필요한 자료구조 1. 가용자원(Available) : 가용자원의 수(길이 m의 벡터) 2. 할당자원(Allocate) : 할당된 유형별 자원의 수(n X m 행렬) 3. 요구량(Request) : 각 프로세스가 요구하는 유형별 자원수( n X m 행렬 ) - Shoshani & Coffman 의 탐지 알고리즘 한 개의 자원 유형만 있는 경우 - 교착상태 탐지에 m X n^2 에 비례하는 처리량이 필요함 - n이 커짐에 따라 탐지에 더 많은 시간 소요됨 교착상태 탐지 알고리즘 이용(언제 탐지할 것인가) 다음 두 요인에 의해 결.. 더보기
반응형

티스토리툴바