프로그래밍 언어론 - 요약(1)

●프로그래밍 언어의 구성 요소

▷구문 구조Syntax, 이름Names, 타입Types, 의미 구조Semantics

 

●구문 구조Syntax

▷문법적으로 프로그램이 어떻게 생겼는지 서술

 

●명령형 프로그래밍

▷폰노이만-엑커르트 의 계산 모델(입력,메모리(프로그램,변수),제어,산술,출력)

 

●객체지향형 프로그래밍

 

●프로그램의 생김새는 구문구조라고 하고 프로그램의 뜻은 의미구조라고 한다.

 

●문맥자유 문법은 생성규칙의 집합 P,단말자 기호의 집합 T. ω비단말자 기호의 집합 N. 시작기호 S로 구성된다.

*문맥자유 문법=BNF문법

*메타언어=상위언어

 

●비단말자 기호의 집합 N은 Identifier 와 같은 언어의 문법 카테고리를 가리키고, 보통 첫 생성규칙으로 정의된다.

 

●화살표와 수직선은 메타언어에 속해있는 것이다, 정의하는 언어에 속해있는 기호가 아니므로 메타기호라고 한다.

 

●이 유도는 352라는 스트링이 유도될 수 있다는 증명이 되며, 아래와 같이 표시한다.

▷Integer=>*352

▷*은 왼쪽에 있는 심볼이 0번이상 나타난다.

 

●BNF 문법 G로 정의한 언어 L은 그 시작 기호로부터 유도될 수 있는 모든 단말자 스트링의 집이다.

 

●파스 트리는 그림형식으로 유도를 그려보는 것이다.

 

●파스트리의 내부 노드는 모두 비단말자로 구성된다.

▷파스트리는 잘못된 문법을 찾는데 더 도움이 된다.

 

●파스트리의 우선순위는 시작 기호에서 연산자까지의 가장 짧은 유도 길이에 의해서 결정되고, (좌/우)결합성은 재귀를 어느(왼/오른) 쪽으로 하는냐에 따라서 결정된다.

▷시작기호와 가까운 연산자가 우선순위가 낮다

 

●문법에서 규칙의 개수를 현저하게 줄일 수 있으면 특히 모호성이 용인되는 경우가 있을 수도 있다.

▷두가지의 파스트리를 만들 수 있다면, 그것은 모호한 문법이다.

 

●비대칭 선택문 문제로 인한 문법의 모호성을 if else로 알 수 있다.

▷이는 EBNF를 사용하면 일반적으로 피할 수있다.

▷C, else와 가장 가까운 if를 자동으로 짝지음

▷Ada 각 조건문 마다 유일한 키워드를 사용하여 끝맺음

▷Java 문법으로 두 개의 모양이 다른 조건으로 따로 정의하여 해결

 

●()는 여러 개 중에서 하나를 반드시 선택하고, {}는 그 안에 포함된 기호가 0번이상 반복된고, []는 EBNF의 메타기호로 사용하면 그 안에 옵션으로 사용될 기호를 넣는다.

 

●EBNF에서 단말자는 너비가 고정된 폰트로, 메타기호는 굵은 폰트를 쓰는 관례를 이 책에선 따른다.

 

●“opt“ 첨자는 여러 개의 단말자와 비단말자 기호를 같이 묶어서 옵션으로 처리할 수 있는 능력을 가진 메타기호인 대괄호에 해당한다.

 

●EBNF가 BNF 보다 표현력이 더 풍부해지지는 않는다.

 

◆어휘 구문구조

●어휘 구문으로 유도가능한 단말자 문자열을 토큰이라고 하고, 다음과 같은 그룹으로 나눈다.

▷식별자(함수, 클래스, 변수 이름), 리터럴(정수 char true와 false, float), 키워드(bool char else false if int main), 연산자, 구두점

 

●대부분의 언어에서 키워드는 모두 예약어로 취급한다.

▷if int char 는 식별자는 어떤 이름(식별자)가 될 수 없다.

 

◆구체(적) 구문구조

●구체 구문구조는 해당 문법의 시작 비단말자로 시작하여 토큰 나열을 파스한 트리를 나타낸다.

 

●컴파일러

▷소스프로그램->어휘 분석기--(토큰)->구문분석기--(추상 구문)->의미 분석기--(중간 코드)->코드 성능 향상기--(중간 코드)->코드 생성기->기계 코드

 

●성능 향상을 하지 않는 컴파일러에서 75%의 시간은 어휘를 분석하는데 쓰인다.

 

●어휘분석기는 렉서 이다.

 

●구문분석기는 파서 이다. (파스트리)

 

●의미 분석기는 선언된 식별자만 있는지, 연산자 타입이 올바른지 확인하고 오류를 출력한다.

 

●추상 구문은 파서로 하여금 구문적 치장을 벗겨버리고 계산에 핵심이 되는 요소만을 가지고 있는 트리를 생성하게 해주는 표기법니다.

 

●추상 구문은 프로그램의 의미를 정하는데 적절하다.

 

◆정규 문법(type 3)(어휘를 만들 때)

●오른쪽 정규 문법은 비단말자가 오른쪽에만 있을 수 있다.

▷비단말자는 최대 한가지만 올 수 있다.

 

●문맥자유 문법(type 2)(문장을 만들 때)

▷BNF 문법과 동일

 

●문맥민감 문법(type 1)

▷선택절에서 우변의 길이가 좌변의 길이보다 크거나 같다.

▷이는 여러 가지 원하지 않는 결정 불가능성을 가진다.

주어진 프로그램이 문법 G를 따르고 있는지를 결정할 수 없다.

L(G)가 타당한 스트링들을 모두 포함하는지 결정할 수 없다.

 

●무제한 문법(type 0)

▷우변의 길이에 대한 제한도 없다. 무제한 문법은 튜링 기계와 표현력이 같으며 완전한 C/C++와도 표현력이 같다.

 

●토큰은 하나의 기호를 표시하기 위해 논리적으로 응집된 문자열이다.

 

●파서가 인식해야 하는 문자열

▷식별자, 리터럴, 키워드, 연산자, 구두문자, 여백, 주석, 줄끝 표시자, 파일끝 표시자

 

●렉서가 삭제 하는것

▷여백, 주석, 줄끝 표시자