서지주요정보
스테이트 백트랙을 이용한 비-LALR(1) 문법의 결정적 파싱 기법 = Deterministic parsing of non-LALR(1) grammar using state backtracking
서명 / 저자 스테이트 백트랙을 이용한 비-LALR(1) 문법의 결정적 파싱 기법 = Deterministic parsing of non-LALR(1) grammar using state backtracking / 김택인.
발행사항 [대전 : 한국과학기술원, 2005].
Online Access 원문보기 원문인쇄

소장정보

등록번호

8016272

소장위치/청구기호

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

MCS 05010

휴대폰 전송

도서상태

이용가능

대출가능

반납예정일

리뷰정보

초록정보

In many programming languages, the programs can be parsed in LALR(1) grammar, but it is not easy to make a parser that can parse the grammar including conflicts. Bison, which is a general purpose parser generator for an LALR(1) context-free grammar, has the disadvantage that the parser cannot parse acceptable input strings in the grammar. We modify Bison and implement the state backtracking method to resolve this problem. In this thesis, we propose a method to make the parser that can parse the grammar which includes some conflicts. In the states with shift-reduce conflicts, the action of the parser of the traditional Bison is shifting or reduction, not both of them. State backtracking is the method that makes a parser to backtrack and to parse again when the parsing error is detected. If the parser shifts some tokens and detects a parsing error, it backtracks to that state, reduces, and continues the parsing process. The parser is required to back up the parsing information in the state including conflicts, and to restore the information when it re-starts to parse from that state. The modified parser generator, which is based on Bison, that supports the state backtracking, is able to generate the parser that can parse the non-LALR(1) grammar including conflicts.

여러 가지 프로그래밍 언어들이 LALR(1) 문법으로 파싱될 수 있지만 컨플릭트를 포함하는 문법을 파싱하는 파서를 만드는 것은 쉽지 않다. 범용 파서 생성기 bison은 수용가능한 입력 스트링을 파싱하지 못하는 경우가 있다. bison을 수정해서 스테이트 백트랙을 구현함으로써 이 문제를 해결한다. 이 논문에서는 컨플릭트를 포함하는 문법을 파싱하는 파서를 만드는 방법을 제안한다. 기존의 bison에서는 컨플릭트를 포함하는 스테이트에서 여러 선택들 중 한 가지만 취하지만, 스테이트 백트랙은 파싱 오류를 만났을 때 백트랙하여 다시 파싱하는 방법이다. 이 때 파서는 파싱 정보를 저장해 두었다가 파싱을 다시 시작할 때 그 정보를 사용한다. bison에서 수정된 파서 생성기는 스테이트 백트랙을 지원함으로써 컨플릭트를 포함하는 비-LALR(1) 문법을 파싱할 수 있는 파서를 생성할 수 있다.

서지기타정보

서지기타정보
청구기호 {MCS 05010
형태사항 vi, 41 p. : 삽화 ; 26 cm
언어 한국어
일반주기 저자명의 영문표기 : Taek-In Kim
지도교수의 한글표기 : 최광무
지도교수의 영문표기 : Kwang-Moo Choe
학위논문 학위논문(석사) - 한국과학기술원 : 전산학전공,
서지주기 참고문헌 수록
QR CODE qr code