저는 대부분의 프로그래밍 언어가 문맥 자유 문법 (CFG)으로 구문 분석 될 수 있음을 읽었습니다. 계산 능력의면에서 보면 푸시 다운 비 결정적 오토 마톤과 같습니다. 내가 맞습니까?
기술적으로 예. 유용하게, 아니.
- 당신은 문자열의 집합으로 생각하는 경우, 당신은 언어이 있습니다
이 질문에 대해 생각하는 두 개 이상의 유용한 방법이 있습니다.
- 문자열이 언어에 있는지 없는지를 결정하는 알고리즘을 생각 중이면 결정 문제가 있습니다.
어려움은 대부분의 프로그래밍 언어는 쉽게 문맥 자유 문법에 의해 기술되는 기본 구조를 가지고있는 동안 (티클 흥미로운 예외 인) 것으로, 문맥이없는 문법으로 설명 많은 문장이 아닌됩니다 실제로 "언어로" "언어로"는 "해당 언어로 된 유효한 프로그램"을 의미합니다. 이러한 추가 문장은 보통 정적 의미의 형식으로 배제됩니다. 예를 들어, 다음과 같은 발언은 C 프로그램의 문맥 자유 문법에서 문장이지만 유효한 C 프로그램의 집합에 그 자체입니다 : 여기
int f(void) { return n + 1; }
문제는 n이 범위에 포함되지 것입니다. C는 "사용하기 전에 선언"을 요구하며, 그 속성은 문맥 - 자유 문법을 사용하여 표현 될 수 없다.
실제 프로그래밍 언어에 대한 일반적인 판정 절차는 선단부 컴파일러 또는 인터프리터의 일부이고, 적어도 두 부분으로 갖는 하나의 파서하는 푸시로 결정 전력의 상당을 자동 장치; 그러나 두 번째는 많은 발언을 무효로 만드는 추가 검사를합니다. 이러한 검사에 사전 정의 된 속성 정의가 필요하다면 푸시 다운 자동화 또는 문맥 자유 문법으로 수행 할 수 없습니다.
사실이라면 CFG가 어떻게 튜링이 끝난 제한없는 문법 (UG)을 유지할 수 있습니까?
CFG는 단순히 언어를 설명하는 단어 "—"을 "보유하지"않습니다.
... 프로그래밍 언어가 CFG로 설명되는 경우에도 실제로는 튜링 기계를 설명하는 데 사용되고 UG를 통해 사용됩니다.
중요한 간접적 인 수준을 건너 뜁니다.
나는 적어도 두 가지 다른 수준의 컴퓨팅 때문이라고 생각합니다. 첫 번째는 CFG 구문 분석은 언어의 구조 (표현?)와 관련된 구문에 초점을 맞추는 반면, 다른 부분은 프로그래밍 언어의 기능과 관련된 의미 (감각, 데이터 자체의 해석). 다시 말하지만, 이러한 가정은 맞습니까?
그들은 약간 혼란스러워 보이지만 올바른 길을 가고 있습니다. 중요한 질문은 "언어과 프로그래밍 언어의 차이점은 무엇입니까?" 대답은 프로그래밍 언어는 계산 해석을 가지고 있습니다. 전산 해석은 많은 훌륭한 품종으로 이루어져 있으며, 모두가 튜링 완성되지는 않습니다. 그러나 마법은 해석이 아니라 구문에 있으므로 촘스키 계층은 여기에서별로 관련이 없습니다.
는 극단적 인 예를 내 지점을 증명하려면 :
일반 언어
[1-9][0-9]*은 다음과 해석에서 튜링 완료 :
- SK-콤비 언어가 튜링 완료됩니다.
- 수많은 SK 프로그램이 있습니다.
- 고유하게 결정 성있게 쉽게 열거 할 수 있습니다.
- 따라서 우리는 각 양의 정수를 SK 프로그램과 연관시킬 수 있습니다.
- 숫자의 시퀀스를 표준 방식으로 양의 정수로 해석하면 SK 프로그램과 동일한 숫자 시퀀스를 똑같이 잘 해석 할 수 있으며 SK 프로그램은 다음과 같은 유한 시퀀스를 사용하여 표현할 수 있습니다. 자릿수.
따라서 정수 리터럴의 언어는 튜링 완료입니다.
머리가 아프면 안됩니다.
약어가 너무 많습니다! 무의미하게 인코딩하지 않고는 의사 소통을 할 수 없다면 결코 효과가 없을 것입니다. –
@DonalFellows에는 두 개의 약어가 있습니다. CFG에 익숙하지 않은 경우 어쨌든 질문에 대답 할 수 없습니다. –