프로그래밍언어론 - 부프로그램 부프로그램이란, 프로그램에서 호출에 의해 실행되도록 만들어진 일련의 코드를 의미한다 부프로그램의 정의와 호출 부프로그램은 실행 할 내용을 기술한 일련의 코드로 머리부와 본체로 구성 되었다 부 프로그램은 코드 흐름 상, 순차적으로 실행 되던 중 함수, 프로시져 등 프로그램 흐름을 변경해서 기능하는 것들을 일컫는 것이라 이해했다 부프로그램의 머리 부분은 예약어, 부프로그램의 이름, 매개변수들의 이름과 타입, 반환 값의 타입 등을 기술한다 부프로그램의 정의 방법 부프로그램 선언 부프로그램이 정의되어 있다는 것을 컴파일러에게 알리는 역할 부프로그램의 머리부는 제공하지만, 부프로그램 몸체를 포함하진 않음 void sub(int, int); 부 프로그램 호출 FORTRAN에서 SUB ..
Computer Science/프로그래밍 언어론
프로그래밍언어론 - 반복문 반복문이란, 특정 부분을 반복 실행되게 하는 문장을 의미한다. 예시 : FORTRAN의 DO문 변수가 초기 값을 갖고 한 번씩 반복할 때마다 증가 값만큼 증가되면서, 종료 값보다 작거나 같은 동안 문장들을 실행 증가 값은 생략 가능, 생략하면 반복 할 때마다 변수 값은 1씩 증가 While 문 식이 참인 동안 문장을 반복해서 실행 C/C++/Java의 while 문 while(Expression) 문장; EBNF -> while() Ada의 while 문 while(Expression){ 문장 1; 문장 2; ... } with Ada.Text_IO; use Ada.Text_IO; procedure Sum is package Int_IO is new Ada.Text_IO.Int..
프로그래밍 언어론 - 조건문 조건문을 사용하면 조건에 따라 둘 이상의 실행 경로 중 하나를 선택할 수 있습니다. 프로그래밍에서 의사 결정 논리를 구현하기 위한 수단을 제공합니다. 두 가지 일반적인 유형의 조건문이 있습니다. “if” 문 if 문은 조건이 참인지 거짓인지에 따라 특정 실행 경로를 선택합니다. if 문은 FORTRAN 프로그래밍 언어에서 처음 도입되었습니다. “case” 또는 “switch” 문 case 또는 switch 문을 사용하면 서로 다른 조건에 따라 여러 경로 중 하나를 선택할 수 있습니다. 표현식을 평가하고 값을 다른 케이스 레이블과 일치시킵니다. 일치하는 경우에 따라 해당 코드 블록이 실행됩니다. If 문 FORTRAN If 문은 FORTRAN에 도입 처음 도입하였습니다 식의 결..
정규 언어, 정규 문법, 유한 오토마타의 동치 관계 전체 문법이 주어지면 문법으로 부터 토큰들을 분리해내고 이 토큰들을 정규 문법으로 표현 토큰에 대한 정규 문법을 정규 표현으로 표시. 이 정규 표현을 인식하는 인식기를 만들면 을 주면 언어가 주어지면, 이를 정규표현으로 변환 정규표현을 인식하는 NFA을 구성, NFA를 DFA로 변환, DFA를 최소화 하면 어휘 분석기 를 만들 수 있음 정규 문법, 정규 표현, 유한 오토마타의 관계가 서로 동치관계 임을 증명 정규문법 ⇒ 정규표현 정규표현 ⇒ 유한오토마타 유한 오토마타 ⇒ 정규문법 정규문법 ⇒ 정규표현으로변환 정규표현에의해서 정의된 문법G에 의해 생성 되는 언어 L(G)가 무엇인지를 알기 위해서는, 정규 문법을 정규 표현으로 변환 정규 문법을 계수(coe..
NFA와 DFA DFA와 NFA는 서로 동등하다 DFA보다 NFA가 언어의 구조를 쉽게 표현 NFA는 DFA보다 프로그램으로 구현하기 어려움 DFA는 NFA보다 프로그램으로 구현했을 경우에 효율면에서 훨씬 우수 일반적인 구현은 DFA로 해야 되는데 NFA가 언어의 구조를 쉽게 표현할 수 있기 때문에 서로가 변환이 필요하다 DFA의 상태수 최소화(state minimization) DFA를 이용하는 어휘 분석기의 상태 전이표의 크기를 줄임 기억공간을 적게 차지하도록 하고 또한 어휘분석 프로그램을 간단히 하는데 큰 도움 상태수를 최소화하는 방법 동치관계(equivalence relation)을 이용 상태수를 합침(state merge) [정의 3.22] 구별가능(distinguishable) [정의 3.23..
프로그래밍 언어론 - 식과 제어문 표현식(Expression) 계산 표현의 기본 수단 연산자, 피연산자, 괄호, 함수 호출 등으로 구성 연산자(Operator) 피연산자가 하나인 단항 연산자 피연산자가 2개인 이항 연산자 C 기반 언어 삼항 연산자: (i%2) ? “홀수” : “짝수” 대부분의 프로그래밍 언어에서 이항 연산자는 피연산자 사이에 위치합니다: x + y LISP에서 연산자는 피연산자 앞에 위치합니다: (+ x y) 연산자 표기 방법 중위 표기법(infix notation) : 연산자가 피연산자들 사이에 위치하는 표기법 전위 표기법(prefix notation) 연산자가 피연산자들보다 앞에 위치하는 표기법 예) 함수 호출 표기 : add(1, mul(2, 3)) 후위 표기법(prefix not..
오토마타 오토마타는 디지털 컴퓨터의 추상적 모델이다. 그래서인지 입력 장치, 제어 장치, 출력 장치, 저장 장치로 이루어져 있다. 추가로, 일시 기억 장치(무한개의 기억소자 cell로 이루어짐), 제어 장치(유한 개의 내부 상태 중 하나의 상태를 항상 유지)도 있다 오토마타의 분류 기능적인 측면 : 인식기(accepter)와 변환기(transducer) 구분 인식기의 경우 입력된 결과에 대해 오토마타는 인식/기각(accept/reject) 등을 표시하는 이진 기호를 출력한다 언어 변환기는 주어진 입력에 대응하는 새로운 문자열을 출력한다 변환기에는 상태에 따른 출력을 내는 Moore 기계와 전이에 따른 출력을 내는 Mealy 기계 등이 있다. 결정적 오토마타 VS 비결정적 오토마타 구분 결정적/비결정적 오..
프로그래밍 언어론 - 데이터 타입 프로그램의 모든 데이터에는 데이터 타입(Type)이 있다 즉 데이터 타입은 그 타입의 변수가 가질 수 있는 값들의 집합이다. 데이터 타입의 종류 기본 데이터 타입 정수 타입, 부동 소수점 타입과 같이 해당 언어에서 기본적으로 제공 사용자 정의 데이터 타입 레코드 타입과 같이 기본 데이터 타입을 이용하여 사용자가 생성 정수 타입 주요 관심사항은 정수 값을 표현하는 데 사용하는 바이트 수 FORTRAN과 같은 언어는 한 가지 크기만을 제공 Java와 C와 같은 언어는 여러 가지 크기를 제공 오버 플로우 : 해당 타입이 제공하는 범위를 넘어서면 오버플로우가 발생한다 비부호 정수 타입 C나 C++에서 제공 0과 양의 정수만 표현하며, unsigned로 시작하는 타입 부동 소수점..
EBNF EBNF의 등장 이유는 BNF를 이용해서 표현하는데 어려움이 있기 때문이다 예를들어 식별자의 길이를 지정해 준 경우 아래와 같이 엄청난 가지 수의 생성 규칙이 생성 될 수 있기 때문이다 ::= | | | | | | | ... | ::= a | b | c | ··· | z ::= 0 | 1 | 2 | ··· | 9 이와 같이 BNF는 반복되는 부분을 표시하는데 어려움을 가지기 때문에, 반복되는 부분을 쉽게 표시하면서 BNF (Backus-Naur Form)로 표시하는 방법이 EBNF이다. EBNF 표기법 반복되는 부분을 BNF 표기법보다 읽기 쉽고 간결하게 표현 BNF 표기법의 세 가지 메타 기호에 반복을 나타내는 { }와 [ ]를 추가하여 사용 {a}는a가0번이상반복될수있다는것을의미 정규표현 a..
구문 도표 쉽게 이해할 수 있도록 문법을 도식화하는 방법입니다. 일반적으로 구문 도표는 사각형과 타원 그리고 이들 사이를 연결한 간선(edge)으로 구성 구문 도표를 그리는 방법 터미널 기호 : 원 논 터니멀 기호 사각형 생성 규칙 접속 : 터미널/논 터미널을 간선으로 이어 통해 표현 생성 규칙 선택 : 병렬 처리하는 그림으로 표현 생성 규칙 : 반복 위의 그림은 B → α* 를 표현한 것이다 루프 형태로 표기하면, N 번 이상 반복하는 것을 표현 가능하다 예제 : 구문 도표로 표현하기 다음 문법을 구문 도표로 표현하라 G = (V_N, VT, P, S) V_N ={A,B,C} VT = {a, (, ), b, c {, }} S=A P: A→a|(B) B → bC C → {c} 논터미널 기호인 A와 B를 ..
