파서 (주로 파서 표현 문법)에 관심이 있기 때문에, 파싱을 범주 적으로 처리하는 작업이 있는지 궁금합니다. 카테고리 이론의 분석에 대한 모든 참조는 높이 평가됩니다.
베스트,
답변
대수 기하학 외부의 주제에 대한 범주 이론의 첫 번째 적용 중 하나는 파싱이었습니다! 검색을 안내하려는 키워드는 “Lambek calculus”및 “categorial grammar”입니다.
현대적으로 요아킴 램벡은 문장 구조를 모델링하기 위해 비 계산적 선형 논리 를 발명했습니다 . 기본적인 아이디어는 당신이 말의 기본 부분을 유형을 갖는 것으로 줄 수 있고, 그 후 영어 형용사에 명사구를 명사구로 가져가는 함수형을 씁니다. (예 : “녹색”은 명사에 명사를 사용하는 함수로 간주됩니다. 즉, “계란”이 명사이므로 “녹색 달걀”이 잘 입력되었음을 의미합니다.
A∖B
B
A
B/A
B
ㅏ
ㅏ※비
ㅏ
비
Lambek 문법은 문맥이없는 언어와 동일하지만 상당히 어려운 결과입니다. CFG가 Lambek 문법의 하위 집합임을 보여주는 것은 쉽지만, 다른 방향은 1991 년 Pentus에 의해서만 확립되었습니다.
독자를위한 좋은 연습 ^ H ^ H ^ 공개 (예 : 시도하지 않았지만 시도해 보는 것이 좋을 것이라고 생각합니다)는 Lambek 미적분학을 사용 하여 부울 행렬 곱셈을 통한 VYant 의 CYK 구문 분석 표현을 범주별로 재구성하는 것입니다. 자귀. 동기 부여로서 Lambek의 1958 년 논문 의 문장 구조 수학 :
여기에 제시된 미적분학은 선형 및 다중 선형 대수학에서의 정식 매핑에 대한 논의를 위해 GD Findlay 및 현재 저자에 의해 구성된 미적분학과 공식적으로 동일합니다.
답변
la Parsec을 파싱 하는 (컨텍스트가없는) 것은 자연스럽게 Applicative 유형 클래스로 표현되는 것으로 보입니다 . 차례로,이 클래스는 소위에 의해 잘 설명되어 강력한 느슨한의 monoidal 펑 에 언급, 이 아주 좋은 cstheory 질문 및 이 좋은 유래 질문 .
더 일반적으로, 파섹 파서는 모나드 이며, CS 이론과 범주 이론 모두에서 잘 알려져 있으므로 요청하지 않으면 언급하지 않을 것입니다.