문법의 종류

문법은 비종결기호(非终结符), 종결기호 (终结符), 시작 기호(开始符, 비종결기호중 하나), 그리고 생성 규칙으로 구성된다. 이중 0~3형 문법이 있다.

• 3형 문법: 정규 문법 (正则文法)로, 어휘 분석의 모델을 정의한다.
• 2형 문법: BNF 문법 혹은 문맥에 구애받지 않는 문법으로, 구문 분석에 사용된다.
• 1형 문법: 문백에 구애받는 문법으로, 더 복잡한 구조의 언어를 정의하는데 사용된다.
• 0형 문법: 제한이 없다.

3형 문법: 정규 문법

词法分析器, 어휘 분석기에 대한 모델을 제공한다. 대부분의 특성이 판단 가능하며, 예를 들어 어떤 종류의 문자열이 생성 가능한지, 문자열이 문법에 정의된 언어에 속하는지, 언어 내의 문자열이 유한한지 등등을 판별 할 수 있다.

$a^n$형태의 문자열을 생성 가능하며, 이중 a는 유한한 문자 시퀀스다. 유한한 수의 요소만으 계산할 수 있으며, 키워드, 단어 스캐닝에 사용된다.

프로그래밍 언어에서 단어나 토큰을 인식하고 분석하는 데 사용되는 기본적인 규칙 시스템을 제공하며, 이는 프로그래밍 언어의 구문 분석과 해석에 중요한 기초를 마련한다.

2형 문법: Context-free grammar

생성 형태가 $X→\alpha$다. $\alpha$는 终结符와 非终结符의 임의 시퀀스다.

3형처럼 여기서도 대부분 성질이 판별 가능하다. 두 개의 항목을 계산 및 비교 가능하고, $a^ncb^n$ 형태의 문자열을 만들 수 있다. 스택의 형탷로 구연 가능하고, 프로그램의 语法分析树를 자동으로 만드는데 사용 가능하다.

1형 문법- Context-sensitive grammar

생성 규칙의 형식이 α → β다. 알파는 비종결기호의 시퀀스, 베타는 종결기호와 비종결기호의 임의 시퀀스다. 알파의 부호 개수는 베타의 것보단 많지 않아야 한다.

특징으로 开始符에서 파생된 문자열의 길이는 증가하고, 2형 문법은 인식 못하는 $a^nc^nc^n$등 문자열 인식을 위해 고정된 저장 공간을 사용한다. 너무 복잡해서 언어 설계에 사용키는 어렵다. 1형 문법은 언어의 구조가 복잡할 때 사용되며, 프로그래밍 언어의 구조를 더 세밀하게 분석하는 데 사용되나, 그 복잡성 때문에 프로그래밍 언어 설계에서는 일반적으로 사용되지 않는다.

0형 문법- 비제한 문법

생성 규칙 형태에 아무런 제한이 없다. α → β 형태를 사용하되 알파와 베타에 위처럼 제한이 있지 않다. 어떠한 계산 가능 함수 인식이 가능하여 튜링 기계와 동등한 표현능력을 가지고, 대부분의 특성은 판별 불가하다.

가장 강력한데, 판단이 어려워 실제로 직접적으로 사용되진 않는다.

언어의 능력

문법 종류가 다양할수록 생성되는 언어의 복잢어도 증가하지만, 컴퓨터의 문제해결 능력이 무제한적으로 강해진다는 뜻은 아니다. 예를 들어, "C언어 프로그램을 작성하여 다른 C언어 프로그램이 종료될 수 있는지 여부를 판단할 수 있을까?" 라는 문제는 불가능하다. 어떤 알고리즘도 임의의 프로그램이 입력에 대해 멈출 것인지 결정 할 수 없다. 이는 수학 모델 자체의 한계 때문이다.

튜링 머신

일반적으로 하나의 언어로 작성된 프로그램은 다른 언어로도 구현이 가능하다. 프로그램이 한 언어로만 구현될 수 있는 경우는 없다. 튜링 머신은 계산 가능한 함수를 정의하기 위한 추상적 컴퓨터다. 이는 한개의 데이터 구조, 즉 길이가 변할 수 잇는 선형 배열인 "带子"를 가진다. 테이프는 여러개의 셀로 나뉘어져 있고, 각 셀에는 하나의 문자가 들어간다. 读出头라는 포인터 변수가 테이프의 특정 셀을 가르킨다.

튜링 머신은 读出头를 통해 테이프의 문자를 읽거나 수정한다. 이는 좌우로 이동되고 테이프 끝에 도달하면 새로운 빈 셀이 추가된다. 튜링머신은 사전에 정의된 작업 시퀀스에 따라 데이터를 읽고 쓰며, 정지케 되면 테이프의 내용이 최종 출력 결과가 된다. 튜링 머신은 0형 문법과 동일한 계산 능력을 가지고, 确定型튜링기는 非确定형 튜링기와 계산 특면에서 동등하다.

정지 문제

다시 돌아온 정지 문제다. "어떤 주어진 튜링 머신이 주어진 입력에 대해 결국 멈출 것인지를 결정할 수 있는 범용 알고리즘이 존재할까?"라는 문제는 불가결정적이다.

결론적으로 프로그래밍 언어는 상호 대체 가능하며, 상호간의 차이는 질보다는 양에 있고, 각 목적, 환경, 요구에 따라 존재 이유가 있다.

언어의 의미 (语义)

언어 설계는 문법에 구애받지 않는 문법, 특히 LR(K) 문법을 중심으로 이루어진다. 현대에는 문법 분석보다는 프로그램의 의미를 결정하는 것이 중요하게 되었다.

의미 결정 방법

• 문법 모델: BNF 문법을 확장하여 语法分析树에서 추가 정보를 얻어낸다.
• 操作모델: 가상 머신에서 프로그램이 어떻게 실행될지 정의한다.
• 응용 모델: 프로그램의 계산을 함수로 정의한다. 프로그램의 각 기본적인 또는 사용자 정의 연산이 수학적 함수를 대표하며, 이러한 함수들이 복합되어 전체 프로그램의 함수 모델을 형성한다.
• 공리 모델: 형식적 논리 증명 이론을 구축하여 프로그램이 그 명세를 만족하는지 확인한다.
• 규격 모델: 프로그램을 구성하는 다양한 함수 간의 관계를 설명한다. 구현이 모든 함수 간의 관계를 만족하면, 그 구현은 규격에 대해 '올바른' 것으로 간주된다. 예를 들어, pop(push(S, x)) = S라는 공리를 만족하는 모든 구현은 스택의 올바른 구현으로 간주한다.

마다마다 장점과 단점이 있으니 상황을 잘 봐야한다. 작동모델은 사용자에겐 너무 세부적일 수도 있고, 공리론은 이해가 쉽지만 복잡한 프로그래밍 정의에는 어렵고, 구현에 대한 지원이 부족하다.

속성 문법

속성 문법은 분석 트리의 각 노드에 함수를 연결하여, 노드의 의미를 제공한다. 즉, 속성 문법의 생성 과정은 각 규칙에 대해 관련된 语义函数를 정의해주는 것이다.

继承属性은 함수로, 트리의 비종결기호값과 고위 계층의 비종결기호의 값을 연결해준다. 즉, 규칙의 오른쪽에있는 비종결기호의 함수 값은 왼쪽의 비종결 기호에 의해 결정된다.

综合属性도 함수로, 왼쪽과 우측의 비종결기호의 값으 연결하여 트리에서 정보를 상향 전달한다.

위는 속성 트리의 예시다.

속성 문법은 또한 데이터의 타입 정보를 트리를 통해 전달하는 데도 사용된다. 위의 예처럼 선언 정보는 언어의 선언 생성식으로 수집 가능하다.

속성 문법을 사용하려면 우선 语法分析树를 생성한다. 표현식이 어떻게 유도되었는지에 대한 이미 알려진 정보를 가정하며, 유도 과정의 분석 방법에는 관심을 두지 않는다.

프로그램 검증

프로그래밍에서는 프로그램의 정확성과 신뢰성이 점점 더 중요해지고 있다. 정확성에 대해선, 주어진 프로그램 P의 의미, 그리고 规范说明S는 무엇인지, S가 주어졌을때 이에 따라 구현된 P가 개발되는지, S와 P는 동일한 기능을 수행하는지를 따져본다.

이러한 관계를 형식적으로 추론 가능하다면, S1이 주어지면 프로그램이 상태 S4에서 종료됨을 수학적으로 증명할 수 있으나, 이는 매우 어렵다. 또한, 규격 설명이 없는 경우 "프로그램이 정확한가?"라는 질문은 의미가 없을 수 있다.

공리화 검증

谓词逻辑公式로 프로그램의 语义를 표현하고, 논리 계산으로 프로그램의 정확성을 검증하는 방법이다.

이중 실증은 일련의 테스트 데이터로 프로그램이 규격 설명을 만족하는지 보여주고, 검증은 형식적 논의를 통해 보여준다. 실증은 프로그램 실행이 필요하고, 후자는 필요 없을수 있다.