차트 구문 분석기

Chart parser

컴퓨터 과학에서 차트 파서는 애매한 문법(자연어 문법 포함)에 적합한 파서의 일종이다.그것은 동적 프로그래밍 접근방식을 사용한다. 부분적인 귀무 가설의 결과는 차트라고 불리는 구조에 저장되고 다시 사용될 수 있다.이것은 역추적을 없애고 결합폭발을 방지한다.

차트 파싱은 일반적으로 마틴 케이에게 인정된다.[1]

차트 구문 분석기 유형

일반적인 접근방식은 Viterbi 알고리즘의 변형을 사용하는 것이다.Earley 파서는 주로 컴퓨터 언어학에서 파싱에 사용되는 차트 파서의 일종으로, 발명가의 이름을 따서 명명되었다.또 다른 차트 파싱 알고리즘은 CYK(Cocke-Younger-Kasami) 알고리즘이다.

차트 파서들은 컴퓨터 언어의 구문 분석에도 사용될 수 있다.특히 Earley 파서들은 임의의 Context-free 그래머를 사용하여 구문 분석하는 그들의 능력이 특정 언어의 문법을 쓰는 작업을 용이하게 하는 컴파일러 컴파일러에서 사용되어 왔다.그러나 그들의 낮은 효율성으로 인해 사람들은 대부분의 컴파일러 작업을 위해 그들을 피하게 되었다.

양방향 차트 구문 분석에서 차트의 가장자리는 전방 또는 후방 중 한 방향으로 표시되며, 추가 가장자리로 결합하기 위해 가장자리가 가리키는 방향으로 규칙이 시행된다.

증분 차트 구문 분석에서 차트는 사용자가 텍스트를 편집함에 따라 점진적으로 생성되며, 각 텍스트가 변경될 때마다 차트에 대한 가능한 최소의 해당 변경이 발생한다.

차트 파서는 하향식 및 상향식뿐만 아니라 능동형과 수동형으로 구분된다.

참고 항목

참조

  1. ^ "Chart Parsing" (PDF). Archived from the original (PDF) on 21 February 2015. Retrieved 20 November 2011.

외부 링크