프로그래밍언어론 2nd edition Tucker and Noonan

Presentation on theme: "프로그래밍언어론 2nd edition Tucker and Noonan"— Presentation transcript:

1 프로그래밍언어론 2nd edition Tucker and Noonan
2장 구문구조 (syntax) 컴파일러로 처리하기 간단한 언어는 프로그래머가 보기에도 간단하다. 니클라우스 워드 (Niklaus Wirth) [1974]

2 소목차 2.1 문법 2.1.1 백커스/나우어 형식(BNF)의 문법 2.1.2 유도 2.1.3 파스 트리
2.1 문법 백커스/나우어 형식(BNF)의 문법 유도 파스 트리 결합성과 우선순위 모호한 문법 2.2 확장 BNF 2.3 소규모 언어 Clite의 구문구조 어휘 구문구조 구체 구문구조 2.4 컴파일러와 실행기 2.5 구문구조와 의미구조의 연결 추상 구문 추상 구문 트리 Clite의 추상 구문 트리

3 구문구조란? 프로그래밍 언어의 구문구조(syntax)는 문법적으로 올바른 프로그램을 정확하게 기술한 것이다.
정형적으로 기술된 최초의 구문구조는 Algol 60의 정의에서 처음 등장한 이래, 대부분의 언어에서 사용 세 단계: 어휘 구문구조(Lexical syntax) 구체 구문구조(Concrete syntax) 추상 구문구조(Abstract syntax)

4 구문구조의 단계 어휘 구문구조 = 언어를 구성하는 기본 기호(이름, 값, 연산자 등)를 정의
어휘 구문구조 = 언어를 구성하는 기본 기호(이름, 값, 연산자 등)를 정의 구체 구문구조 = 계산식, 문장, 프로그램을 작성하는 규칙 추상 구문구조 = 구두점이나 괄호와 같은 구문 인식전용 구조를 제외한 핵심적인 구문정보 만으로 구성된 구문 정의

5 2.1 문법 메타언어(metalanguage) 다른 언어를 기술하는데 사용하는 언어를 말한다.
문법(grammar)은 언어의 문법구조를 정의하는데 사용하는 메타언어이다. 목적: 문법으로 프로그래밍언어의 구문구조를 정의하는 것

6 The Big Picture Chomsky Hierarchy of Language Grammars (1956)

7 2.1.1 백커스/나우어 형식 (BNF) (촘스키 계층의 하나인) 문맥자유문법을 실용적으로 사용할 수 있도록 만든 것
(촘스키 계층의 하나인) 문맥자유문법을 실용적으로 사용할 수 있도록 만든 것 백커스/나우어 형식(Backus Normal Form)이라 함 Algol 60의 구문구조를 정의하는데 처음 사용 현재 대부분 언어의 구문구조를 정의하는데 사용

8 BNF 문법 다음의 집합으로 구성 생성 규칙(Productions): P 단말자 기호(Terminal symbols): T
비단말자 기호(Nonterminal symbols): N 시작 기호(Start symbol): S 생성규칙은 다음과 같이 쓴다. 여기서 이고, 이다.

9 예: 이진숫자(Binary Digits) 만드는 규칙
다음 문법을 보자. binaryDigit  0 binaryDigit  1 이렇게 써도 같은 표현이다. binaryDigit  0 | 1 여기서 수직선(|)은 양자택일을 나타내는 메타기호이다.

10 2.1.2 유도 다음 문법을 보자. 352와 같은 부호가 붙지 않은 정수를 이 문법으로 유도해낼 수 있다.
유도 다음 문법을 보자. Integer  Digit | Integer Digit Digit  0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 352와 같은 부호가 붙지 않은 정수를 이 문법으로 유도해낼 수 있다.

11 이 6단계로 이루어지는 유도 단계는 다음으로 시작한다. Integer
이 6단계로 이루어지는 유도 단계는 다음으로 시작한다. Integer

12 문법 규칙 하나를 적용하면 다음과 같이 유도된다. Integer  Integer Digit
352의 유도 (단계 1) 문법 규칙 하나를 적용하면 다음과 같이 유도된다. Integer  Integer Digit

13 352의 유도 (단계 1-2) 오른쪽에 있는 비단말자 하나에 문법 규칙 하나를 적용하면 다음과 같이 유도된다.
오른쪽에 있는 비단말자 하나에 문법 규칙 하나를 적용하면 다음과 같이 유도된다. Integer  Integer Digit  Integer 2

14 352의 유도 (단계 1-3) 같은 방식으로 계속 유도해나가면 다음과 같다. Integer  Integer Digit

15 Integer  Integer Digit  Integer 2  Integer Digit 2  Integer 5 2
352의 유도 (단계 1-4) Integer  Integer Digit  Integer 2  Integer Digit 2  Integer 5 2

16 352의 유도 (단계 1-5) Integer  Integer Digit  Integer 2  Integer Digit 2

17 352의 유도 (단계 1-6) 단말자 기호만 남으면 유도가 종료된다. Integer  Integer Digit
 3 5 2

18 352의 유도 (다른 방식) 이와 같이 단계마다 가장 왼쪽 비단말자가 대치되는 유도 방식을 ‘왼쪽 우선 유도’라고 한다.
Integer  Integer Digit  Integer Digit Digit  Digit Digit Digit  3 Digit Digit  3 5 Digit  3 5 2 이와 같이 단계마다 가장 왼쪽 비단말자가 대치되는 유도 방식을 ‘왼쪽 우선 유도’라고 한다. (첫 번째 유도는 ‘오른쪽 우선 유도’라고 한다.

19 유도 표기법 Integer * 352 352  L(G) L(G) = {   T* | Integer *  }
Means that the language defined by 문법grammar G 로 정의된 언어는 문법규칙 Integer로 유도할 수 있는 모두 기호 문자열  의 집합임을 뜻한다.

20 2.1.3 파스 트리 파스트리(parse tree)는 유도를 그림 형식으로 표현한 것이다.
트리의 내부 노드는 유도의 한 단계에 해당한다. 노드의 자식 노드들은 생성규칙의 우변을 나타낸다. 각 잎새 노드를 왼쪽에서 오른쪽으로 읽으면 유도된 문자열 기호가 된다.

21 예를 들어, 다음 단계는 아래와 같은 파스트리로 표현된다. Integer  Integer Digit

22 Integer로서 352에 대한 파스 트리 그림 2.1

23 산술계산식 문법 다음 문법은 한자리 정수, 덧셈, 뺄셈을 표현할 수 있는 산술계산식 언어를 정의하고 있다.
다음 문법은 한자리 정수, 덧셈, 뺄셈을 표현할 수 있는 산술계산식 언어를 정의하고 있다. Expr  Expr + Term | Expr – Term | Term Term  0 | ... | 9 | ( Expr )

24 문자열 5-4+3의 파스 트리 그림 2.2

25 2.1.4 결합성과 우선순위 문법은 계산식에서 연산자의 결합성과 우선순위를 정의하는데 사용된다.
문법은 계산식에서 연산자의 결합성과 우선순위를 정의하는데 사용된다. 예를 들어, + 와 – 는 수학에서 좌결합 연산자이고, * 와 / 는 +와 – 보다 우선순위가 높다. 좀 더 복잡한 문법 G1을 살펴보자. Expr  Expr + Term | Expr – Term | Term Term  Term * Factor | Term / Factor | Term % Factor | Factor Factor  Primary ** Factor | Primary Primary  0 | ... | 9 | ( Expr ) G1

26 문법Grammar G1으로 만든 4**2**3+5*6+7의 파스트리 그림 2.3

27 우선순위 결합성 연산자 3 right ** 2 left * / % 1 left + -
표 2.1 우선순위 결합성 연산자 3 right ** 2 left * / % 1 left 주목: 이 관계는 파스트리의 구조를 보면 다음과 같이 관찰할 수 있다. 우선순위가 높으면 아래쪽에 위치, 좌결합이면 각 수준에서 왼쪽으로 쏠림.

28 2.1.5 모호한 문법 문법으로 만들어내는 문자열 하나로 두 개 이상의 다른 모양의 파스트리를 만들 수 있는 경우, 그 문법은 모호하다(ambiguous)고 한다. 예를 들어, 위의 문법 G1 은 모호하지 않다. C, C++, Java 는 다양한 연산자와 다양한 우선순위 수준을 제공하고 있다. 문법 정의의 규모를 키우는 대신, 규모가 작은 모호한 문법을 쓰고, 우선순위와 결합성을 따로 정의한다 (예, 표 2.1)

29 모호한 문법 G2 Expr  Expr Op Expr | ( Expr ) | Integer
Notes: G2 은 G1과 동일함. 즉, 같은 언어를 정의함. G2 은 G1보다 비단말자의 개수와 생성규칙의 개수가 작다. 그러나 G2 는 모호하다.

30 문법 G2 가 모호함을 보여주는 5-4+3의 두 파스 트리
그림 2.4 G2 Expr  Expr Op Expr | ( Expr ) | Integer Op  + | - | * | / | % | **

31 비대칭 선택문 문제(Dangling Else)
IfStatement  if ( Expression ) Statement | if ( Expression ) Statement else Statement Statement  Assignment | IfStatement | Block Block  { Statements } Statements  Statements Statement | Statement

32 예 어느 ‘if’가 ‘else’와 관련된 쌍인가? if (x < 0) if (y < 0) y = y - 1;
else y = 0; Answer: 어느 것이든 가능하다!

33 비대칭 선택문 문제로 인한 문법의 모호성 그림 2.5

34 비대칭 선택문의 모호성 해결하기 Algol 60, C, C++: else와 가장 가까운 if를 우선적으로 짝지움; {} 또는 begin…end으로 둘러싸면 이 규칙을 무시할 수 있음. Algol 68, Modula, Ada: 각 조건문 마다 유일한 키워드를 사용하여 끝맺음 (예: if…fi) Java: 문법으로 두개의 모양이 다른 조건문을 따로 정의하여 해결 IfThenStatement  if ( Expression ) Statement IfThenElseStatement  if ( Expression ) StatementNoShortIf else Statement StatementNoShortIf 는 IfThenStatement를 제외한 모둔 문장을 나타낸다.

35 2.2 확장 BNF (Extended BNF) BNF: EBNF: 메타문자 추가 사용 반복을 재귀적으로 표현 비단말자로 그룹화
{ } 0번 이상 반복 ( ) 여러 개 중에서 하나는 반드시 선택 [ ] 옵션, 선택하거나 버리거나 둘 중 하나 * BNF를 EBNF로 표현함으로써 사용되는 비단말 기호의 개수를 줄일 수 있고 간결하게 표현 가능 함.

36 EBNF 사례 Expression 은 하나 이상의 Terms이 연산자 + 와 – 로 분리되어 나열된 것임
Expression  Term { ( + | - ) Term } Expr  Expr + Term | Expr – Term | Term IfStatement  if ( Expression ) Statement [ else Statement ] IfStatement  if ( Expression ) Statement |if ( Expression ) Statement else Statement C스타일 EBNF 에서는 아래 첨자 opt를 사용하여 옵션으로 사용하는 부분을 표시한다. 예: IfStatement: if ( Expression ) Statement ElsePartopt ElsePart: else Statement

37 EBNF 를 BNF 로 변환하기 EBNF 문법은 BNF로 언제든지 변환이 가능하다. 예를 들어, 다음 EBNF문법은
A -> x { y } z 다음과 같이 BNF 문법으로 변환된다. A -> x A' z A' ->ε | y A' ( )와 [ ] 로 표현된 EBNF 문법을 BNF로 변환하는 방법은 연습문제로 남겨둔다. A -> a [ b ] A -> a | a b EBNF가 BNF보다 표현력이 더 좋은 것은 아니지만, 보기에는 일반적으로 훨씬 간단 명료하다.

38 덧셈 연산자가 포함된 Expressions에 대한 구문 다이어그램
Figure 2.6 Expression  Term { (+|-) Term }

39 구문도표( syntax diagram, syntax chart ) 를 이용하는 방법. 형태가 순서도와 유사함.
비단말 기호는 사각형으로, 단말기호는 원이나 타원으로 표기, 이들 사이의 연결은 지시선으로 연결함.

40 - 구문 도표를 그리는 방법 1) 단말 x는 원 또는 타원 안에 x로 표기하고 다음 기호를 보기 위해 나가는 지시선을 그림. x 2) 비단말 B는 사각형 안을 B로 쓰고 단말의 경우와 같이 지시선으로 연결함. 사각형의 내용은 그 안의 이름으로 참조 가능함. B

41 3) 생성규칙 A  X1X2 … Xn은 아래와 같은 문법 순서도를 나타냄.
(ㄱ) Xi가 비단말 기호인 경우 : A X X … Xn (ㄴ) Xi가 단말 기호인 경우 : A X X … Xn

42 4) 생성 규칙 A  1 | 2 | … |n 은 아래와 같이 나타냄.

43 5) EBNF A  { }는 다음과 같이 표현됨. A 

44 5) EBNF A  []는 다음과 같이 표기 함. A 

45 6) EBNF A  (1 | 2 ) 는 다음과 같이 표기 함.

46 - 다음 EBNF를 구문 도표로 바꾸어 보자. A  x | ‘(‘ B ‘)’ B  AC C  {+A} 단말기호 : x, +, ‘(‘ , ‘)’ 비단말기호 : A, B, C 각 비단말에 대한 구문 도표를 각각 먼저 그린다.

47 A  x | ‘(’ B ‘)’ B  AC C  {+A} - 각 비단말에 대한 구문 도표를 그리면 다음과 같다. A x

48 A  x | ‘(’ B ‘)’ B  AC C  {+A} - 앞의 예는 다음과 같이 하나로 표현 가능 A x ( A )

49 2.3 소규모 언어 Clite의 구문구조 C의 일부 만을 쓰는 동기:
문법 언어 (쪽수) 참고문헌 Pascal 5 Jensen & Wirth C Kernighan & Richie C Stroustrup Java 14 Gosling, et. al. Clite 문법은 1쪽에 작성 가능 (슬라이드로는 3쪽), 따라서 언어 설계를 공부하기에는 안성맞춤

50 그림 2.7 Clite 문법: Statements
Program  int main ( ) { Declarations Statements } Declarations  { Declaration } Declaration  Type Identifier [ [ Integer ] ] { , Identifier [ [ Integer ] ] } Type  int | bool | float | char Statements  { Statement } Statement  ; | Block | Assignment | IfStatement | WhileStatement Block  { Statements } Assignment  Identifier [ [ Expression ] ] = Expression ; IfStatement  if ( Expression ) Statement [ else Statement ] WhileStatement  while ( Expression ) Statement

51 그림 2.7 Clite 문법: Expressions
Expression  Conjunction { || Conjunction } Conjunction  Equality { && Equality } Equality  Relation [ EquOp Relation ] EquOp  == | != Relation  Addition [ RelOp Addition ] RelOp  < | <= | > | >= Addition  Term { AddOp Term } AddOp  + | - Term  Factor { MulOp Factor } MulOp  * | / | % Factor  [ UnaryOp ] Primary UnaryOp  - | ! Primary  Identifier [ [ Expression ] ] | Literal | ( Expression ) | Type ( Expression )

52 그림 2.7 Clite 문법: 어휘 정의 Identifier  Letter { Letter | Digit }
Letter  a | b | ... | z | A | B | ... | Z Digit  0 | 1 | ... | 9 Literal  Integer | Boolean | Float | Char Integer  Digit { Digit } Boolean  true | False Float  Integer . Integer Char  ‘ ASCII Char ‘

53 이 문법에서 빠진 구문 관련 이슈 주석 공백문자의 역할
<=를 하나의 기호로 취급하는지, 아니면 <와 =를 두 개의 기호로 취급하는지의 구별 if와 같은 키워드와 식별자의 구별 이 이슈는 다음의 두 단계로 구분하여 설명한다. 어휘 단계 구문 단계

54 2.3.1 어휘 구문구조 입력: 프로그래머가 입력한 ASCII 문자 스트림
어휘 구문구조 입력: 프로그래머가 입력한 ASCII 문자 스트림 출력: 다음과 같이 분류된 토큰(token) 또는 기본 기호의 스트림 식별자Identifiers e.g., Stack, x, i, push 리터럴Literals e.g., 123, 'x', 3.25, true 키워드Keywords bool char else false float if int main true while 연산자Operators = || && == != < <= > >= + - * / ! 구두점Punctuation ; , { } ( )

55 공백문자(Whitespace) 공백문자는 빈칸(space), 탭(tab)문자, 줄바꿈(end-of- line) 문자, 주석 내부의 문자들을 말한다. 토큰 내부에는 공백문자가 포함될 수 없다. (문자 또는 문자열 제외) 예: >= 토큰 한 개 > = 토큰 두 개

56 Pascal의 공백 문자 예 while a < b do 인정

57 주석(Comments) 문법에 정의되어 있지 않음 Clite 는 C++ 형식을 따라 // 를 사용

58 식별자(Identifier) 문자로 시작하여 문자 또는 숫자의 나열
Clite 문법에 따르면 if 는 식별자도 되고 키워드도 된다 대부분의 언어는 식별자는 키워드와 구별하여 다르게 취급한다 일부 언어에서 식별자를 미리 정해주기도 한다. 필요에 따라 프로그래머가 재정의할 수도 있다. Identifier  Letter { Letter | Digit }

59 식별자의 재정의는 위험 program confusing; const true = false; begin
if (a<b) = true then f(a) else …

60 식별자의 대소문자는 구별해야 하나? 구식 언어: 구별하지 않는다. 왜? Pascal: 구별하지 않음 Modula: 구별
구식 언어: 구별하지 않는다. 왜? Pascal: 구별하지 않음 Modula: 구별 C, C++: 구별 Java: 구별 PHP: 일부는 구별하고, 일부는 구별하지 않음. 이렇게 하면, 직교성에는 어떤 영향이?

61 2.3.2 구체 구문구조 Based on a parse of its Tokens IfStatement 의 문법 규칙은 모호함
C는 ; 를 문장 종결자로 사용 Algol-60, Pascal 은 ; 를 문장 분리자로 사용 IfStatement 의 문법 규칙은 모호함 “비대칭 성택문 모호성은 else 없는 가장 가까운 if와 해당 else를 연결하여 해결한다.” [Stroustrup, 1991]

62 Clite의 계산식(Expressions)
13의 문법 규칙 메타 중괄호의 사용 – 연산자는 좌결합 C++ 는 계산식을 정의하는 문법 규칙이 4쪽에 달함 [Stroustrup] C 는 우선순위와 결합성을 문법으로 정의하지 않고, 모호한 계산식 문법을 그대로 사용 [Kernighan and Ritchie]

63 결합성과 우선순위 Clite 연산자 결합성 단항 - ! 없음 * / 좌결합 + - 좌결합
단항 - ! 없음 * / 좌결합 좌결합 < <= > >= 없음 == != 없음 && 좌결합 || 좌결합

64 Clite 동등/관계 연산자 … 결합성은 없음. (Ada에서 따온 아이디어) C++에서는 좌결합임 C++에서 다음 관계식은
if (a < x < b) 다음 관계식과 의미가 다르다. if (a < x && x < b) 전자는 항상 true가 된다! 왜? 연산자에 결합성을 부여한 설계가 바람직하였나?

65 2.4 컴파일러(Compilers)와 실행기 (Interpreters)
추상구문 중간 코드 중간코드 소스 프로그램 토큰 기계코드 어휘 분석기 구문 분석기 의미 분석기 코드성능향상기 코드 생성기

66 Stages in translating a program

67 Translation environments

68 어휘 분석기 입력: 문자 스트림 출력: 토큰 스트림 어휘분석을 따로 하는 이유
속도: 성능향상 부분을 제외하고, 컴파일 총 시간의 75%가 어휘 분석 설계가 간단 기종 마다 다른 문자열 사용 (이식성 향상) 줄바꿈 문자의 관례도 기종마다 다름 (이식성 향상)

69 파서(구문분석기) BNF/EBNF 문법 기반 입력: 토큰 스트림 출력: 추상 구문 트리 (파스 트리)
추상 구문: 파스트리에서 더 이상 필요없는 구둣점 및 비단말자를 제거한 트리

70 의미 분석 식별자의 선언 여부 검사 타입 검사 타입변환 연산자 삽입 묵시적 타입 변환  명시적 타입 변환

71 코드 성능향상 컴파일하면서 상수 계산식 실행 캐시 수행 성능 향상을 위하여 코드 재배치 공통 부분계산식 삭제
불필요한 코드 삭제

72 코드 생성 출력: 기계 코드 명령 선택 레지스터 관리
핍홀 성능향상 : 코드 패턴에 따른 최적화(연속적인 명령어 순서를 의미적으로 등등하고 더 효율적인 명령어로 ) load ax, X  inc X add ax, 1 store ax, X

73 실행기(Interpreter) 컴파일러 단계 중 마지막 두 단계를 대체 입력: 혼합형 실행기 순수형 실행기:
혼합형: 중간 코드 순수형: ASCII 문자 스트림 혼합형 실행기 Java, Perl, Python, Haskell, Scheme 순수형 실행기: 대부분 Basic 언어, shell 명령

74 2.5 구문구조와 의미구조의 연결 출력: 파스트리는 효율적이지 않음 예: 그림 2.9

75 z = x + 2*y; 의 파스 트리 그림 2.9

76 더 효율적인 트리 찾기 파스트리의 모양은 프로그램의 의미를 드러낸다.
파스트리의 모양은 프로그램의 의미를 드러낸다. 따라서 모양은 그대로 유지한 채, 비효율적인 부분이 제거된 트리로 만들면 좋겠다. 분리자/구둣점과 같은 단말자 기호 제거 사소하게 루트가 되는 비단말자 모두 제거 나머지 비단말자는 모두 해당 입새 단말자로 대치 예: 그림 2.10

77 z = x + 2*y; 에 대한 추상 구문 트리 그림 2.10

78 추상 구문구조(Abstract Syntax)
Removes “구문적 설탕(syntactic sugar)”을 제거하고, 꼭 필요한 부분만 가지고 있다. 예: 동일한 의미를 가진 다음 두 루프 구조를 보자. Pascal while i < n do begin i := i + 1; end; C/C++ while (i < n) { i = i + 1; } 이 두 루프에서 꼭 필요한 정보는 루프라는 사실과 종료 조건은 i < n이라는 사실과 몸통에서 i의 현재 값을 1씩 증가한다는 사실이다.

79 Clite 저장문의 추상 구문구조 Assignment = Variable target; Expression source
Expression = VariableRef | Value | Binary | Unary VariableRef = Variable | ArrayRef Variable = String id ArrayRef = String id; Expression index Value = IntValue | BoolValue | FloatValue | CharValue Binary = Operator op; Expression term1, term2 Unary = UnaryOp op; Expression term Operator = ArithmeticOp | RelationalOp | BooleanOp IntValue = Integer intValue …

80 추상 구문구조를 Java Class로 표현 abstract class Expression { }
abstract class VariableRef extends Expression { } class Variable extends VariableRef { String id; } class Value extends Expression { … } class Binary extends Expression { Operator op; Expression term1, term2; } class Unary extends Expression { UnaryOp op; Expression term;

81 추상 구문 트리의 예 이진 노드의 형식 x+2*y 에 대한 추상구문트리 (그림 2.13) + 2 y * x
op term1 term2 이진 노드의 형식 x+2*y 에 대한 추상구문트리 (그림 2.13) Binary Binary Operator Variable Value + 2 y * x

82 Clite 다른 부분의 추상구문구조 (선언 및 문장) 그림 2.14