(오토마타)CFG(CNF) 촘스키 노말 폼 파싱 구현(C/C++)

소개글

context free grammar 중 chomsky normal form 파싱을 c,c++을 이용하여 구현했습니다.
출력은 left most derivation으로 했습니다.
동적계획법(dynamic)을 사용했습니다.

컴파일 실행환경

Microsoft VIsual Studio 2010

본문내용

Parsing

context-free grammar G가 Chomsky normal form으로 주어져 있다. G의 변수들은 영문 대문자로 이루어져 있고, 터미널 심벌들은 영문 소문자로 이루어져 있으며, S가 start symbol이라고 가정한다. 영문 소문자로 구성된 스트링 w가 주어질 때, w가 L(G)의 원소인지 아닌지를 판별하는 프로그램을 작성하시오. 프로그램의 실행시간은 10초를 초과할 수 없다.

입력 형식
입력 파일의 이름은 input.txt이다. 입력 파일의 첫째 줄에 스트링 w가 입력된다. 스트링의 길이 n은 100 이하이다. 둘째 줄에는 G의 production rule의 개수 m이 입력된다. m도 100 이하이다. 셋째 줄부터 마지막 줄까지 한 줄에 하나씩 G의 production rule이 입력된다. production rule은 하나의 스트링으로 입력되는데, rule의 왼쪽 변수, 이어서 “->”, 그리고 rule의 오른쪽 부분이 주어진다. 입력 파일에 빈칸은 없다.

출력 형식
출력 파일의 이름은 output.txt이다. 첫째 줄에 입력으로 주이진 스트링 w가 L(G)의 원소이면 “member”를 출력하고, 그렇지 않으면 “nonmember”를 출력한다. 첫째 줄에 “member”를 출력한 경우에는 S에서 시작하여 w에서 끝나는 leftmost derivation을 출력하는데, 한 줄에 sentential form을 하나씩 출력한다. 두 sentential form 사이에 기호 “=>”을 줄의 맨 앞에 보인다. leftmost derivation이 둘 이상인 경우에는 임의의 것 하나 출력하면 된다. 출력 파일에도 빈칸은 없다.

압축파일 내 파일목록

parsing.cpp
output.txt
input.txt
programming project - parsing.hwp

참고 자료

MSDN