서지주요정보
Extended context-free parsing of regular right part grammars = 우변정규문법의 확장된 자유문맥 구문해석
서명 / 저자 Extended context-free parsing of regular right part grammars = 우변정규문법의 확장된 자유문맥 구문해석 / Heung-Chul Shin.
저자명 Shin, Heung-Chul ; 신흥철
발행사항 [대전 : 한국과학기술원, 1994].
Online Access 제한공개(로그인 후 원문보기 가능)원문

소장정보

등록번호

8004328

소장위치/청구기호

학술문화관(문화관) 보존서고

DCS 94005

SMS전송

도서상태

이용가능

대출가능

반납예정일

등록번호

9000329

소장위치/청구기호

서울 학위논문 서가

DCS 94005 c.2

SMS전송

도서상태

이용가능

대출가능

반납예정일

초록정보

Regular right part grammar is an alternative to context-free grammar, in which right parts of productions are nondeterministic finite state machines to extend the descriptive power of context-free grammar by including notations for describing repetitions and alternations. However, on its LR parsing, extra work is required to identify the left end of a handle at reduction time because a nonterminal can derive potentially infinite number of strings via a single production. Properties of LALR(k) regular right part grammars and their extended LR(0) automata are examined. An improved method for building efficient extended LALR(k) parsers for such grammars is given, which uses only kernel items of extended LR(0) automata. Neither grammar transformation nor extra readback state of a parser is needed, which is used to construct readback machine to recognize the reverse of the state sequences leading to a reduction. For a reduction by particular production in a state, parser may refer to lookback states in which the parser may be restarted after a reduction. An optimizing algorithm to reduce these references is presented. An efficient method to compute lookahead sets by using only kernel items of extended LR(0) automation is also presented.

우변 정규표현 문법은 자유문맥문법의 일종으로, 반복 또는 교번(병렬선택)등의 표현기법을 활용하므로써 자유문맥문법의 표현력을 확장시키기 위해 프로덕션의 우변을 정규표현이나 미결정적인 유한 오토마타로 나타낸다. 우변 정규표현 문법은 종전의 자유문맥문법에 비해 프로그래밍 언어에 대한 구문의 기술이 간결하고 자연스러우며, 이를 이해하거나 구성하기가 매우 쉬운 장점을 지니고 있다. 그러나, 이에 대한 LR 구문해석시, 하나의 프로덕션을 통해 한 넌터미널 심볼은 무한히 긴 스트링이나 무한개의 스트링을 생성할 수 있기 때문에 축약할 때 핸들의 왼쪽 끝을 알아내기가 쉽지 않다. 본 논문에서는, 먼저 LALR(k) 우변 정규표현 문법과 그 확장 LR(0) 오토마타에 대한 특성들을 분석하였다. 게다가, ELR(0) 오토마타의 커널 항목만을 이용하여 매우 효율적인 ELALR(k) 구문해석기를 생성할 수 있는 개선된 방법을 제시하였다. 이 방법에서는 문법을 변환할 필요가 없을 뿐만 아니라, 축약할 때 일련의 스테이트 순에 대해 거꾸로 인식하기 위해 필요한 readback machine(프로덕션의 우변이 유한 오토마타이므로 축약시에는 이에 대한 역방향의 유한 오토마타)을 구성하는 readback 스테이트 역시 필요없다. 축약시에 lookback 스테이트(축약후에 프로덕션의 우변이 새로 시작되는 곳, 즉, 구문해석기가 다시 시작되는 곳)를 확인해야만 하는데, 이의 확인 과정을 최소로하는 방안도 함께 제시하였다. 또한, ELR(0) 오토마타의 커널 항목만을 이용하여 효과적으로 lookahead 집합을 구하는 방법도 제시하였다.

서지기타정보

서지기타정보
청구기호 {DCS 94005
형태사항 ii, 62 p. : 삽도 ; 26 cm
언어 영어
일반주기 저자명의 한글표기 : 신흥철
지도교수의 영문표기 : Kwang-Moo Choe
지도교수의 한글표기 : 최광무
학위논문 학위논문(박사) - 한국과학기술원 : 전산학과,
서지주기 Reference : p. 60-62
주제 문맥 자유 문법. --과학기술용어시소러스
구문 분석. --과학기술용어시소러스
Parsing (Computer grammar)
QR CODE qr code