C\#품사 분석 기의 입력 버퍼 와 코드 포 지 셔 닝 의 응용 분석
7231 단어 입력 버퍼코드 포 지 셔 닝
품사 분석 을 어떻게 하 는 지 소개 하기 전에 별로 언급 되 지 않 은 문제 인 원본 파일 에서 문자 흐름 을 어떻게 읽 는 지 먼저 말 해 보 세 요.왜 이 문제 가 이렇게 중요 합 니까?문법 분석 에서 문자 흐름 에 대한 요구 가 있 기 때문에 반환 작업 을 지원 해 야 합 니 다.
먼저 왜 리 턴 작업 을 지원 해 야 하 는 지 설명 하 겠 습 니 다.간단 한 예 를 들 어 지금 은 두 모델 을 일치 시 켜 야 합 니 다.
그림 1 흐름 의 후퇴 과정
위 는 간단 한 매 칭 과정 으로 후퇴 과정 만 보 여주 기 위해 뒤에서 DFA 시 뮬 레이 터 를 실현 할 때 어소 와 어떻게 일치 하 는 지 상세 하 게 설명 한다.
이제 C\#에서 입력 과 관련 된 클래스 를 살 펴 보 겠 습 니 다.Stream 이 있 습 니 다.스 트림 검색 을 지원 하지만 바이트 로 만 접근 할 수 있 습 니 다.Binary Reader 와 TextReader 는 읽 기 문 자 를 지원 하지만 되 돌 리 는 것 을 지원 할 수 없습니다.따라서 이 입력 버퍼 류 를 스스로 완성 해 야 합 니 다.대체적으로 생각 하 는 것 은 TextReader 를 기본 문자 로 입력 한 다음 에 자신의 클래스 에서 반환 능력 에 대한 지원 을 완성 하 는 것 입 니 다.
에 서 는 버퍼 가 맞 는 방법 을 제시 했다.쉽게 말 하면 두 개의 버퍼 를 열 고 버퍼 크기 를 모두 N 글자 로 설정 하 는 것 이다.매번 N 자 를 버퍼 에 읽 고 이 버퍼 에서 문자 작업 을 수행 합 니 다.현재 버퍼 의 데이터 가 처리 되 었 다 면 N 개의 새 문 자 를 다른 버퍼 에 읽 고 새 버퍼 로 바 꿉 니 다.
이러한 데이터 구 조 는 효율 이 높 고 적당 한 지침 만 유지 하면 반환 기능 을 쉽게 실현 할 수 있다.그러나 버퍼 크기 는 고정 되 어 있 습 니 다.새로 읽 은 문 자 는 오래된 문 자 를 덮어 씁 니 다.반환 이 필요 한 문자 수가 너무 많 으 면(예 를 들 어 긴 문자열 을 분석 할 때)오류 가 발생 하기 쉽다.나 는 여러 개의 버퍼 를 사용 하여 오래된 문자 가 덮어 쓰 이 는 문 제 를 해결 했다.버퍼 가 부족 하면 오래된 데 이 터 를 덮어 쓰 는 것 이 아니 라 새로운 버퍼 를 열 었 다.
버퍼 만 계속 추가 하면 사용 하 는 메모리 가 계속 증가 할 뿐 의미 가 없습니다.그래서 저 는 버퍼 를 방출 하 는 세 가지 동작 을 정 의 했 습 니 다.Drop,Accept,AcceptToken.Drop 의 역할 은 현재 위치 이전의 모든 데 이 터 를 무효(버 림 받 음)로 표시 하 는 것 입 니 다.잘못된 데 이 터 를 사용 하 는 버퍼 가 방출 되 고 중복 적 으로 이용 할 수 있 습 니 다.Accept 는 단순 한 포기 가 아니 라 잘못된 데이터 로 표 시 된 데 이 터 를 문자열 로 되 돌려 줍 니 다.이와 유사 하 게 AcceptToken 은 무효 화 된 데 이 터 를 Token 형식 으로 되 돌려 주 는 것 으로 어법 분석 을 편리 하 게 하기 위 한 것 이다.
이러한 데이터 구 조 는 STL 의 deque 와 유사 합 니 다.그러나 여 기 는 무 작위 로 데 이 터 를 방문 하고 삽입,삭제 할 필요 가 없습니다.데이터 의 머리,꼬리 에서 만 작 동 하기 때문에 저 는 여러 개의 버퍼 를 양 방향 링크 로 연결 하고 세 개의 포인터 current 를 사용 합 니 다.first 와 last 는 링크 에 데이터 가 있 는 버퍼 를 가리 키 고 있 습 니 다.다음 그림 과 같 습 니 다.
그림 2 여러 개의 버퍼 로 구 성 된 링크 입 니 다.빨간색 부분 은 데이터 가 있 고 흰색 부분 은 데이터 가 없습니다.
그 중에서 first 는 최초의 데이터 버퍼 를 가리 키 고 last 는 최신 데이터 버퍼 를 가리 키 며 current 는 현재 방문 하고 있 는 데이터 버퍼 를 가리 키 며 current 는 항상[first,last]범위 안에 있 습 니 다.firstIndex 와 lastLen 사이 의 빨간색 부분 은 유효한 데 이 터 를 포함 하 는 버퍼 입 니 다.idx 는 현재 접근 하고 있 는 문 자 를 표시 합 니 다.흰색 부분 은 빈 버퍼 나 버퍼 의 데이터 가 잘못 되 었 음 을 표시 합 니 다.
다음 문 자 를 읽 어야 할 때 current 에서 데 이 터 를 순서대로 읽 고 idx 를 뒤로 이동 합 니 다.current 의 데 이 터 를 읽 었 다 면 current 를 last 로 이동 합 니 다.
그림 3 current 에서 last 로 이동
문 자 를 계속 읽 어야 하 는데 current 에 새 데이터 가 없습니다.이 때 current 는 last 와 같 습 니 다.버퍼 에 업데이트 되 지 않 은 데 이 터 를 표시 하려 면 TextReader 에서 데 이 터 를 읽 고 새로운 버퍼 에 넣 어야 합 니 다.current 와 last 를 뒤로 이동 하 는 동시에 last 가 항상 최신 버퍼 를 가리 키 도록 해 야 합 니 다.
그림 4 current 와 last 를 뒤로 이동 합 니 다.
이제 리 턴 작업 을 살 펴 보 자.되 돌 릴 때 는 current 를 first 방향 으로 이동 해 야 합 니 다(마찬가지 로 current 와 first 사이 에 여러 개의 버퍼 가 있 을 수 있 습 니 다).
그림 5 후퇴 조작
Drop 작업(Accept 와 AcceptToken 도 마찬가지)의 실현 도 간단 하 다.first 를 current 위치 로 이동 하고 firstIndex 를 idx 로 이동 하면 된다.이것 은 idx 이전의 데이터 가 모두 무효 데이터 로 간주 된다 는 것 을 의미한다.
그림 6 드 롭 조작
여기 서 주의해 야 할 것 은 드 롭 작업 이 완료 되면 무효 화 된 데이터 가 새 데이터 로 덮어 쓸 수 있 으 므 로 데이터 가 더 이상 필요 하지 않 을 때 드 롭 작업 을 수행 해 야 한 다 는 것 이다.Drop 작업 의 효율 이 매우 높 기 때문에 효율 에 영향 을 미 칠 염려 가 거의 없다.
이러한 링 데이터 구 조 를 사용 하 는 장점 은 버퍼 에 문 자 를 채 우 는 것 을 제외 하고 데이터 의 추가 복 제 를 완전히 피 할 수 있다 는 것 이다.전진,후퇴,드 롭 작업 모두 포인터(참조)만 작 동 하고 효율 이 높다 는 것 이다.Drop 을 비교 할 때 두 개의 버퍼 만 사용 하고 메모 리 를 추가 로 사용 하지 않 습 니 다.사용 하 는 버퍼 가 너무 많 을 때 남 은 메모 리 를 주동 적 으로 방출 할 수 있 습 니 다(여 기 는 현재 고려 하지 않 았 습 니 다).
단점 은 실현 하기 가 복잡 하 다 는 것 이다.first,current 와 last 의 관 계 를 잘 처리 하고 firstIndex,index 와 lastLen 의 범위 제한 을 잘 처리 해 야 하 며,때로는 여러 버퍼 의 조작 도 포함한다.
완전한 코드 를 볼 수 있 습 니 다SourceReader.cs.코드 포 지 셔 닝
소스 코드 를 분석 할 때 모든 Token 에 대응 하 는 줄 번호 와 열 번 호 를 기록 하 는 것 은 분명히 필요 한 작업 입 니 다.아무 도 많은 Error 에 직면 하 는 것 을 좋아 하지 않 을 것 입 니 다.그리고 하필 이면 무엇이 틀 렸 는 지 알려 주지 않 습 니 다.그래서 코드 포 지 셔 닝 은 품사 분석 에 필수 적 인 기능 이 라 고 생각 하기 때문에 이 기능 을 SourceReader 류 에 직접 내장 시 켰 습 니 다.
코드 포 지 셔 닝 을 어떻게 실현 하 는 지 설명 한다.코드 포 지 셔 닝 은 3 차원 데이터:색인,줄 번호 와 열 번 호 를 포함 합 니 다.색인 은 0 에서 시 작 된 문자 색인 으로 주로 프로그램 처리 가 편리 합 니 다.줄 번호 와 열 번 호 는 모두 1 에서 시 작 된 것 으로 주로 사람 을 위해 보 러 간다.
줄 포 지 셔 닝 이 간단 합 니 다.유 닉 스 의 줄 바 꿈 부 호 는''이 고 윈도 우즈 의 줄 바 꿈 부 호 는'\r'이기 때문에'의 개 수 를 직접 통계 하면 됩 니 다.
다음은 열 위치 입 니 다.비교적 좋 은 효 과 를 얻 기 위해 서 는 두 가지 요 소 를 고려 해 야 한다.즉,전각,반 각 문자 와 Tab 문자 이다.
하나의 중국어 문자(즉 전각 문자)는 두 열 에 대응 하고 영문 문자(반 각 문자)는 한 열 에 대응 하 며 이렇게 넓 은 글씨체 아래 에서 모든 열 은 상하 로 정렬 된다.열 수 를 계산 할 때 도 문자열 의 길이 가 아 닌 Encoding.Default.GetByteCount()를 사용 해 야 합 니 다.하지만 여기 서 메모리 문 제 를 발 견 했 습 니 다.(자세 한 내용 은 여기 참조)Encoding.Default.GetEncoder()의 GetByteCount 방법 으로 바 꾸 면 됩 니 다.
Tab 문자 의 길 이 는 정 해 지지 않 았 습 니 다.(일반적으로 4 또는 8,사람 에 따라 다 릅 니 다.)그래서 TabSize 를 정의 하여 Tab 문자 의 너 비 를 표시 합 니 다.그럼 Tab 문 자 는 TabSize 열 에 대응 합 니까?그렇지 않 습 니 다.일반적으로 보기 에는 그렇지만 사실은 Tab 문 자 는 다음 문자 에 대응 하 는 열 을 항상 TabSize 의 정수 배 에 1 을 더 합 니 다.TabSize=4 라면 다음 그림 과 같이 행동 합 니 다.그 중에서 a 와 bcc 뒤에 두 개의 Tab 문자 가 있 습 니 다.bcccc 와 bccccccc 뒤에 모두 Tab 문자 가 있 습 니 다.모든 Tab 문 자 는 회색 화살표 로 표 시 됩 니 다.
그림 7 Tab 문자 인 스 턴 스
따라서 실제 열 번 호 는 아래 의 공식 으로 계산 해 야 합 니 다.그 중에서 currentCol 은 Tab 문자 가 있 는 열 이 고 nextCol 은 다음 문자 가 있 는 열 입 니 다.
nextCol = tabSize * (1 + (currentCol - 1) / tabSize) + 1;종합 적 으로 고려 한 후에 저 는 코드 위치의 계산 을 Drop 작업(Accept 와 AcceptToken 도 마찬가지)에 넣 기로 결 정 했 습 니 다.하 나 는 위 에서 말 한 것 입 니 다.계산 효율 이 약간 높 을 것 입 니 다.다른 하 나 는 보통 Token 을 식별 한 후에 야 위 치 를 정 해 야 합 니 다.이때 가 바로 Drop 이나 AcceptToken 의 시기 입 니 다.Token 을 인식 하 는 과정 에서 포 지 셔 닝 을 해도 소 용이 없다.
나 는 코드 포 지 셔 닝 기능 을SourceLocator.cs클래스 에 단독으로 봉 했다.
다음 편 에 서 는 품사 분석 에 사용 되 는 정규 표현 식 과 정규 표현 식 을 어떻게 해석 하 는 지 소개 합 니 다.
좋은 웹페이지 즐겨찾기
