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) 문법을 파싱할 수 있는 파서를 생성할 수 있다.
