Chapter4.1 언어 구문 추가 - BNF
구문은 프로그래밍 언어의 구조를 의미
프로그래밍 언어의 정의 -> 언어 구문 + 언어 의미로 구성
4.1 언어 구문
오늘날 컴퓨터 대부분 -> 두 개의 문자 코드계를 사용
- IBM에서 제안한 EBCDIC(extended binary coded decimal intercahnge code) -> 8비트
- ANSI에서 제안한 ASCII 코드 -> 7비트
프로그래밍 언어의 어휘 구조는 프로그래밍 언어 알파벳 문자로 구성된 단어 즉 어휘 토큰이다.
번역기는 일반적으로 어휘 분석 단계에서 입력 프로그램의 일련의 문자들을 토큰으로 구분하고, 구문 분석 단계에서 이를 처리하여 구문구조를 결정한다.
한 개 이상의 어휘 토큰을 가지고 구문적으로 허용된 프로그램의 일부 구조를 언어구성자라고 한다. 이러한 언어 구성자를 부르는 이름이 식별자라는 토큰이다.
번역 과정의 속도 향상, 프로그램 신뢰성 향상을 위해 프로그래밍 언어는 일부 식별자를 미리 정의하여 사용. 정의된 식별자 중 일부를 재 정의할 수 없도록 정의하여 사용 -> 이를 예약어라고 한다. ex) c에서는 if, while, int 등 32개의 예약어가 있으며, scanf, printf, strcnp #define 등은 예약어가 아닌 미리 정의된 식별자로 간주
문맥 자유 문법과 BNF
구문 형식을 정의하는 가장 보편적인 기법 -> BNF 표기법 Algol 60 구문을 정의할 때 최초로 사용
BNF -> 생성 규칙들(production rule)의 집합 모든 정상적인 프로그램을 이 생성 규칙들을 가지고 산출한다는 것이 이론적으로 가능. 이 생성 규칙은 또한 작성된 프로그램이 구문에 맞는 프로그램인지 아닌지를 인식하기 위한 구문 규율로도 사용. 이 규칙의 왼쪽 정의될 대상(object)이 표현. 오른쪽에는 그 대상에 대한 정의가 나타난다.
ex) BNF 표기법에 의한 식별자 정의
<identifier> ::=<letter>| <identifier><letter>|<identified><digit>
<letter> ::A|b|c|...|X|Y|Z
<digit> ::=0|1|2|...|8|9
-
’::=’는 “정의된다”는 것을 의미. 즉 구문 구조 이름인 좌측이 ‘::=’기호 다음에 따르는 우측으로 대체될 수 있다는 의미이다. 또한 특수기호인 ‘ ‘는 택일을 의미한다. 그러므로 위 표의 첫 번째 정의는 세 개의 정의가 합쳐진 형태이다. -
각 괄호(<>)로 묶여진 기호는 비단말(nonterminal) 기호라고 칭하는데, BNF 규율로 다시 정의될 대상이라는 것을 의미한다.
-
각 괄호로 묶이지 않은 기호는 단말(terminal)기호라고 하며, 이 단말 기호에는 각 언어에서 사용되는 알파벳 문자 집합과 예약어가 있다.
-
BNF 표기에서 사용된 특수기호들(::==, , <>)을** 메타 기호**라 부르며, 메타 기호는 표현하려는 언어의 일부분이 아니라 그 언어를 표현하려고 사용된 특수 기호이다.
위의 예제처럼 모든 생성 규칙에서 정의 될 대상이 하나의 비단말 기호로 구성된다면 이 문법을 문맥 자유 문법(context-free grammar)이라 한다. 이것은 각 비단말 기호가 어디에 나타날지라도 그에 해당하는 우측 선택으로 언제나 대치될 수 있다는 것을 의미한다. (즉 좌측 비단말 기호가 어디에 나타날지라도 그에 해당하는 우측 선택으로 언제나 대치될 수 있다는 것을 의미한다.) 한편 특수한 문맥에 의존하여 대치되는 문법을 문맥 의존 문법(context sensitive grammear)이라 한다. 일반적으로 프로그래밍 언어에서 이러한 문맥 의존성에 관한 사항은 구문론적 문제보다는 의미론적 문제로 처리한다.
일반적 BNF 표기법, 모든 프로그래밍 언어를 표기 가능 but 보기 쉽고 간결하게 표현할 수 있는 확장된 EBNF(Extend BNF)를 사용. EBNF는 특수한 기호를 갖는 메타기호 더 사용. 반복되는 부분 간결하게 표현 가능 ex) {a}는 a가 0번 이상 반복될 수 있다는 것을 의미.
① BNF 표현
<compound-statement> ::=begin <statement-list> end
<statement-list> ::=<statement>|<statement-list>;<statement>
② EBNF 표현
<compound-statement> ::=begin <statement< {; <statement>} end
EBNF -> 반복되는 최대 횟수와 최소 횟수도 나타낼 수 있는데, 영문자로 시작하여 최고 8개의 문자를 가질 수 있는 식별자를 다음과 같이 표현할 수 있다.
<identifier-name> ::=<letter> {<alphanumeric>}70
<alphanumeric> ::=<letter> | <digit>
<letter> ::= A | B | C | ...| X | Y | Z
<digit> ::=0 | 1 | 2 | ... | 8 | 9
중괄호 뒤 0은 최소 횟수, 7은 최대 횟수를 나타내며, 이것을 BNF로 정의한다면 매우 긴 표현이 될 것이다. 선택적인 부분(optional part)을 표시할 때에는 []로 나타낸다. 즉, [x]는 x가 나타나지 않거나 한 번 나타날 수 있음을 의미. 따라서 [x]는 {x}¹₀과 같은 의미.
ex) if 문장에서 else 부분이 선택적으로 나타낼 수 있다면 다음과 같이 EBNF로 표현 가능
<if-statement> ::=if <condition> then <statement> [else < statement >]
그리고 괄호와 택일 연산자(|)을 사용하여
<expression> ::=<expresstion> + <expresstion> |
<expresstion> - <expresstion> |
<expresstion> * <expresstion> |
<expresstion> / <expresstion>
이것을
<expresstion> ::=<expresstion> ( + | - | * | / ) <expresstion>
이렇게 간단히 나타낼 수 있다.
{},[], | ,(),::=과 같이 EBNF 사용되는 메타기호를 언어에서 단말 기호로 사용하는 경우 혼동이 생기는데, 이를 피하기 위해 메타 기호를 단말 기호로 사용할 때는 ‘와’로 묶어 다음과 같이 표현한다. |
<BNF-rule> ::= <left-part> '::=' <right-part>'
<right-part> ::= <right-part-element> {'|' <right-part-element> }
표 4.3 Subpascal 시작부에 대한 EBNF 생략
4.1.3 구문도표
구문에 대한 형식 정의 방법 ->EBNF 외에도 구문 도표 존재. 순서도와 비슷
- 단말 - 원
- 비단말 -> 사각형
- 문법 순서도로 나타낸다.
- 생성 규칙
- A ::= {a}
- A ::= [a]
-
A ::={𝛂1 𝛂2}𝛃
예제가 있으나 옮기기 어려워서 직접 그려보는 걸로 대체.
4.1.4 파스 트리와 추상 구문 트리 (AST)
한 표현이 주어진 BNF에 의하여 작성될 수 있는지 없는지를 확인하기 위해서, 주어진 BNF를 이용하여 그 대상을 근(root)으로 하고 단말 노드들을 왼쪽에서 오른쪽으로 나열한 것이 검증하고자 하는 표현과 같이 되는 트리를 작성하게 되는데 이 트리를 파스트리(parse tree)라고 한다.
주어진 표현에 대해서 파스트리 존재 ? -> BNF에 의하여 작성 가능 존재 x -> BNF 작성 불가
이 역시 작성방법-> 직접 그려보는 걸로 대체해야함.
어떤 트리는 파스트리의 본질적 구조를 나타냄 -> 추상 구문 트리 혹은 단순히 구문 트리라고 한다.
4.1.5 모호성, 결합성 및 우선 순위
개념이 다소 어려움. (앞부분 이해x 생략)
동일 스트링에 대해서 서로 다른 파스 (또는 구문)트리가 발생하면 이러한 문법을 모호(ambiguous)하다고 한다. 모호한 문법은 어떠한 명확한 구조를 표현하지 않기 때문에 어려움을 야기한다. -> 모호함이 없도록 개정 혹은 모호성 제거 규칙을 기술.
이후 어려워서 생략.
참고자료
프로그래밍 언어 개념 - 원유헌 저