프로그래밍 언어론 - 요약(2)
●프로그래밍 언어의 구성 요소
▷구문 구조Syntax, 이름Names, 타입Types, 의미 구조Semantics
●구문 구조Syntax
▷문법적으로 프로그램이 어떻게 생겼는지 서술
●명령형 프로그래밍
▷전통적인 폰노이만-엑커르트 계산 모델을 따름
▷(입력,메모리(프로그램,변수),제어,산술,출력)
▷Cobol, Fortrn, C, Ada, Perl
●객체지향형 프로그래밍
▷상태를 변환시키는 메시지를 주고받으며 상호 교류하는 객체의 모임.
▷Smalltalk, java, C++, C#, Python
●함수형 프로그래밍
▷프로그래밍은 계산문제를 수학 함수의 집합으로 모델링.
▷Lisp, Scheme, ML, Haskell
●논리형 프로그래밍
▷프로그램에서 얻어내야 하는 결과가 무엇인지를 선언 하도록 문제를 모델링하여 프로그램 작성
▷Prolog
●이벤트 처리(GUI), 동시 계산(클라이언트-서버), 프로그램의 정확성
●컴파일언어
▷Fortran, Cobol, C, C++
●인터프리터 언어
▷Scheme, Haskell, Python
●둘다 사용하는 언어
▷Java Virtual Machine
●컴파일 실행 과정
▷원시프로그램 어휘분석 구문분석 타입검사 코드향상 코드생성 컴퓨터(입출력)
●해석기=인터프리터 실행 과정
▷원시프로그램 어휘분석 구문분석 타입검사 (추상구문트리) 해석기(입출력) 컴퓨터
●구문구조란
▷문법적으로 맞는 프로그램을 정확하게 기술한 것.
●어휘 구문구조(Lexical syntax)
▷언어를 구성하는 기본 기호(이름, 값, 연산자 등)를 정의
●구체 구문구조(Concrete syntax)
▷계산식, 문장, 프로그램을 작성하는 규칙
●추상 구문구조(Abstract syntax)
▷구두점이나 괄호와같은 구문인식 전용 구조를 제외한 핵심적인 구문정보만으로 구성된 구문
●프로그램의 생김새는 구문구조라고 하고 프로그램의 뜻은 의미구조라고 한다.
●BNF문법은
▷생성규칙의 집합 P(Productions),
▷단말자 기호의 집합 T(Terminal symbols).
▷ω비단말자 기호의 집합 N(Nonterminal symbols).
▷시작기호 S로 구성된다 (Start symbol).
*문맥자유 문법=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%의 시간은 어휘를 분석하는데 쓰인다.
●어휘분석기는 렉서 이다.
●구문분석기는 파서 이다. (파스트리)
●의미 분석기는 선언된 식별자만 있는지, 연산자 타입이 올바른지 확인하고 오류를 출력한다.
●추상 구문은 파서로 하여금 구문적 치장을 벗겨버리고 계산에 핵심이 되는 요소만을 가지고 있는 트리를 생성하게 해주는 표기법니다.
●추상 구문은 프로그램의 의미를 정하는데 적절하다.
◆정규 문법(Regular grammar)(type 3)(어휘를 만들 때)
●오른쪽 정규 문법은 비단말자가 오른쪽에만 있을 수 있다.
▷비단말자는 최대 한가지만 올 수 있다.
▷유한 오토마타(Finite Automata)
●문맥자유 문법(Context-free)(type 2)(문장을 만들 때)
▷BNF 문법과 동일
▷푸쉬다운 오토마타(Pushdown Automata)
●문맥민감 문법(Context-sensitive grammar)(type 1)
▷선택절에서 우변의 길이가 좌변의 길이보다 크거나 같다.
▷이는 여러 가지 원하지 않는 결정 불가능성을 가진다.
주어진 프로그램이 문법 G를 따르고 있는지를 결정할 수 없다.
L(G)가 타당한 스트링들을 모두 포함하는지 결정할 수 없다.
●무제한 문법(recursively enumerable set)(type 0)
▷우변의 길이에 대한 제한도 없다. 무제한 문법은 튜링 기계와 표현력이 같으며 완전한 C/C++와도 표현력이 같다.
●토큰은 하나의 기호를 표시하기 위해 논리적으로 응집된 문자열이다.
●파서가 인식해야 하는 문자열
▷식별자, 리터럴, 키워드, 연산자, 구두문자, 여백, 주석, 줄끝 표시자, 파일끝 표시자
●렉서가 삭제 하는것
▷여백, 주석, 줄끝 표시자
●결정적 유한 상태 오토마타(Deterministic Finite Automata)
▷구문 구조Syntax, 이름Names, 타입Types, 의미 구조Semantics
●구문 구조Syntax
▷문법적으로 프로그램이 어떻게 생겼는지 서술
●명령형 프로그래밍
▷전통적인 폰노이만-엑커르트 계산 모델을 따름
▷(입력,메모리(프로그램,변수),제어,산술,출력)
▷Cobol, Fortrn, C, Ada, Perl
●객체지향형 프로그래밍
▷상태를 변환시키는 메시지를 주고받으며 상호 교류하는 객체의 모임.
▷Smalltalk, java, C++, C#, Python
●함수형 프로그래밍
▷프로그래밍은 계산문제를 수학 함수의 집합으로 모델링.
▷Lisp, Scheme, ML, Haskell
●논리형 프로그래밍
▷프로그램에서 얻어내야 하는 결과가 무엇인지를 선언 하도록 문제를 모델링하여 프로그램 작성
▷Prolog
●이벤트 처리(GUI), 동시 계산(클라이언트-서버), 프로그램의 정확성
●컴파일언어
▷Fortran, Cobol, C, C++
●인터프리터 언어
▷Scheme, Haskell, Python
●둘다 사용하는 언어
▷Java Virtual Machine
●컴파일 실행 과정
▷원시프로그램 어휘분석 구문분석 타입검사 코드향상 코드생성 컴퓨터(입출력)
●해석기=인터프리터 실행 과정
▷원시프로그램 어휘분석 구문분석 타입검사 (추상구문트리) 해석기(입출력) 컴퓨터
●구문구조란
▷문법적으로 맞는 프로그램을 정확하게 기술한 것.
●어휘 구문구조(Lexical syntax)
▷언어를 구성하는 기본 기호(이름, 값, 연산자 등)를 정의
●구체 구문구조(Concrete syntax)
▷계산식, 문장, 프로그램을 작성하는 규칙
●추상 구문구조(Abstract syntax)
▷구두점이나 괄호와같은 구문인식 전용 구조를 제외한 핵심적인 구문정보만으로 구성된 구문
●프로그램의 생김새는 구문구조라고 하고 프로그램의 뜻은 의미구조라고 한다.
▷
●BNF문법은
▷생성규칙의 집합 P(Productions),
▷단말자 기호의 집합 T(Terminal symbols).
▷ω비단말자 기호의 집합 N(Nonterminal symbols).
▷시작기호 S로 구성된다 (Start symbol).
*문맥자유 문법=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%의 시간은 어휘를 분석하는데 쓰인다.
●어휘분석기는 렉서 이다.
●구문분석기는 파서 이다. (파스트리)
●의미 분석기는 선언된 식별자만 있는지, 연산자 타입이 올바른지 확인하고 오류를 출력한다.
●추상 구문은 파서로 하여금 구문적 치장을 벗겨버리고 계산에 핵심이 되는 요소만을 가지고 있는 트리를 생성하게 해주는 표기법니다.
●추상 구문은 프로그램의 의미를 정하는데 적절하다.
◆정규 문법(Regular grammar)(type 3)(어휘를 만들 때)
●오른쪽 정규 문법은 비단말자가 오른쪽에만 있을 수 있다.
▷비단말자는 최대 한가지만 올 수 있다.
▷유한 오토마타(Finite Automata)
●문맥자유 문법(Context-free)(type 2)(문장을 만들 때)
▷BNF 문법과 동일
▷푸쉬다운 오토마타(Pushdown Automata)
●문맥민감 문법(Context-sensitive grammar)(type 1)
▷선택절에서 우변의 길이가 좌변의 길이보다 크거나 같다.
▷이는 여러 가지 원하지 않는 결정 불가능성을 가진다.
주어진 프로그램이 문법 G를 따르고 있는지를 결정할 수 없다.
L(G)가 타당한 스트링들을 모두 포함하는지 결정할 수 없다.
●무제한 문법(recursively enumerable set)(type 0)
▷우변의 길이에 대한 제한도 없다. 무제한 문법은 튜링 기계와 표현력이 같으며 완전한 C/C++와도 표현력이 같다.
●토큰은 하나의 기호를 표시하기 위해 논리적으로 응집된 문자열이다.
●파서가 인식해야 하는 문자열
▷식별자, 리터럴, 키워드, 연산자, 구두문자, 여백, 주석, 줄끝 표시자, 파일끝 표시자
●렉서가 삭제 하는것
▷여백, 주석, 줄끝 표시자
●결정적 유한 상태 오토마타(Deterministic Finite Automata)