컨텍스트 감지 부분과 언어의 컨텍스트 프리 부분을 분리하는 방법은 무엇입니까?

Question

는 내가 comp.theory 목록이 환상적인 게시물 읽기 :

http://coding.derkeiler.com/Archive/General/comp.theory/2004-03/0189.html

포스터는 대부분의 프로그래밍 언어는 문맥 자유 코어를 정의하는 점을하게 한 다음 구문 분석 트리에서 실행되는 추가 알고리즘을 언어 불법 구조를 필터링하기 :

이것은 상황에 맞는 부분에서 언어의 맥락이없는 부분을 분리 해 - 일반적으로 좋은 연습 (모듈의 일종으로 간주된다 "프로그램 언어 디자인을위한 "ming"규율).

이 기술을 설명하기 위해 "Hello World"예제를 제공 할 수 있습니까? 즉, 간단한 문맥 의존 언어를 제공하고 문맥없는 핵심을 식별 한 다음 문맥없는 핵심을 사용하여 입력을 구문 분석 한 다음 구문 분석 트리에서 불법 구문을 필터링하여 제거하는 방법을 설명합니다.

이 기술을 설명하는 기사 나 서적을 참조 할 수 있습니까? 문맥 자유없는 간단한 언어

Answer 1

하나는 단어가 ^N B ^N C ^N (A, B, C는 동일한 횟수로 반복 된 형태의 아르 하나이다 즉, abc, aabbcc, aaabbbccc, ...).

당신은 C의 수는 제한되지 않는 문맥 자유 언어 {A ^N B ^N C ^m}에 대한 문법을 ​​사용하여 구문 분석 할 수 있습니다. 파스 트리가 생기면 별도의 알고리즘을 사용하여 c의 반복 횟수가 a와 b의 반복 횟수와 동일한 지 확인합니다.

Answer 2

일반적으로 필터링은 언어의 over-approximations을 명확하게하기 위해 수행됩니다. 우리는 프로그래밍 언어에 대해 애매 모호하지만 문맥이없는 문법을 작성한 다음 나무 워커 또는 기타 메커니즘을 사용하여 원치 않는 파생어를 제거합니다.

하나의 참조 : 문맥 자유 문법의 동음 (1994)에 대한 필터를 사용

• , http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.51.9812

한 반면, 당신은 또한 추상 구문을 처리하는 유형 검사를 고려할 수 나무 같은 필터. 유형 검사기는 외부 (컨텍스트)가 아닌 정보를 기반으로 파서가 생성 한 트리를 거부합니다.

이

E ::= Int | String | E "+" E; 

하지만 유형 검사는 또한 정수와 문자열 사이 일을하고 언어에서 문장을 거부하지 않는 것을 말한다 예를 들어 다음과 같은 이유로

1 + "1" 

은 문법에 의해 허용됩니다. 유형 검사기는 구문 분석 후 추가 기호를 식별 한 다음 테이블에서 유효한 피연산자 조합을 찾는 방식으로 트리를 탐색하고 조합이 유효하지 않으면 불평을 시작하여이를 수행합니다. 나는 그것이 일반적으로 컴파일러가 작동하는 방법이라고 생각합니다. Aho 외. 용 책.추상적으로 말하면 흥미로워집니다 :-)