26｜프로그래밍 언어의 구문·BNF·파스 트리·형식 언어

프로그래밍 언어로 작성한 문장은 아무 문자나 임의의 순서로 나열한다고 만들어지지 않습니다. 각 언어는 사용할 수 있는 문자와 단어, 문장을 결합하는 규칙을 정해 두며 번역기는 이 규칙에 따라 소스 코드가 올바른지 분석합니다.

이 장에서는 프로그래밍 언어의 구문을 구성하는 문자 집합·식별자·연산자·키워드·예약어·주석·구분 문자를 정리합니다. 이어 BNF·EBNF·구문 도표·파스 트리의 관계를 예제로 살펴보고, 형식 언어의 문법 계층과 정규 표현의 위치까지 연결합니다.

프로그래밍 언어의 구문은 무엇인가?

프로그래밍 언어의 구문(Syntax)은 올바른 프로그램 문장을 만드는 형식 규칙입니다. 소스 코드는 먼저 문자 흐름에서 의미 있는 토큰으로 나뉘고, 이후 토큰의 배열이 문법 규칙에 맞는지 분석됩니다.

분석 단계	입력	주요 작업	출력
어휘 분석	문자의 연속	공백·주석을 처리하고 식별자·키워드·리터럴·연산자·구분자를 인식	토큰의 연속
구문 분석	토큰의 연속	문법 규칙에 따라 토큰의 구조와 결합 순서를 확인	파스 트리 또는 구문 구조
의미 분석	구문 구조	자료형·선언·사용 범위·연산 의미의 타당성을 확인	의미가 부여된 구조

언어의 구문 요소에는 무엇이 있는가?

언어의 구문 요소에는 문자 집합·식별자·연산자·핵심어·예약어·주석·구분 문자·잡음어 등이 있습니다. 실제 언어 명세에서는 식별자·키워드·리터럴·연산자·구분자 등을 토큰으로 분류하고, 공백과 주석은 토큰 경계를 정하거나 분석 과정에서 제거하는 입력 요소로 다루기도 합니다.

구문 요소	의미	예시	주의점
문자 집합	프로그램 작성에 사용할 수 있는 문자와 부호의 집합	영문자, 숫자, 한글, 특수 문자	허용 문자와 인코딩은 언어별로 다름
식별자 Identifier	변수·함수·클래스 등에 붙이는 이름	total, studentCount	키워드·예약어와 같은 이름을 사용할 수 없는 경우가 많음
리터럴 Literal	소스 코드에 직접 적은 고정된 값	10, 3.14, "ABC"	자료형별 표기 규칙을 따름
연산자 Operator	산술·비교·논리·대입 등의 연산 기호	+ - * / == && =	우선순위와 결합 방향을 확인
키워드 Keyword	언어 문법에서 특별한 의미를 가진 단어	if, while, class	문맥에 따라 키워드가 되는 언어도 있음
예약어 Reserved Word	일반 식별자로 사용할 수 없도록 확보한 단어	return, switch	키워드와 예약어의 범위가 항상 같지는 않음
주석 Comment	코드의 의도와 설명을 기록하는 부분	// 설명	일반적으로 실행 의미에서 제외됨
구분 문자 Separator	문장이나 구성 요소의 경계를 표시하는 기호	( ) { } [ ] , ;	언어별 분류가 다를 수 있음
잡음어 Noise Word	추가 정보보다 가독성과 자연스러움을 높이는 단어	문장형 업무 언어의 보조 단어	모든 언어가 별도 범주로 사용하지는 않음

하나의 문장은 어떤 토큰으로 나뉘는가?

total = price * count + 100; // 배송비 추가

입력 부분	토큰 종류	역할
total	식별자	계산 결과를 저장할 변수
=	대입 연산자	오른쪽 결과를 왼쪽 변수에 저장
price	식별자	가격을 나타내는 변수
*	산술 연산자	가격과 수량을 곱함
count	식별자	수량을 나타내는 변수
+	산술 연산자	배송비를 더함
100	정수 리터럴	코드에 직접 작성한 값
;	구분 문자	문장의 끝을 표시
// 배송비 추가	주석	계산 의도를 설명

BNF는 문법을 어떻게 정의하는가?

BNF(Backus–Naur Form)는 프로그래밍 언어의 문맥 자유 문법을 형식적으로 표현하는 대표적인 표기법입니다. 왼쪽의 비단말 기호가 오른쪽의 단말·비단말 기호 조합으로 어떻게 만들어지는지를 생성 규칙으로 정의합니다.

표기	의미	예
::=	왼쪽 비단말 기호를 오른쪽 표현으로 정의	<문장> ::= <대입문>
|	여러 생성 규칙 중 하나를 선택	<항> ::= <식별자> | <숫자>
< >	추가 규칙으로 다시 정의되는 비단말 기호	<표현식>
따옴표로 묶은 기호	실제 입력에 나타나는 단말 기호	"=", "+"

<대입문> ::= <식별자> "=" <표현식> 
<표현식> ::= <항> | <표현식> "+" <항>  
<항> ::= <식별자> | <숫자> 
<식별자> ::= "x" | "a"
<숫자> ::= "0" | "1" | "2" | "3"

• <대입문>·<표현식>·<항>은 비단말 기호입니다.
• x·a·3·=·+는 단말 기호입니다.
• |는 오른쪽의 대안 중 하나를 선택한다는 의미입니다.
• 시작 기호에서 생성 규칙을 반복 적용하여 실제 문장을 유도합니다.

이 BNF는 등호 왼쪽에 식별자를 두고, 오른쪽에 하나 이상의 항으로 이루어진 표현식을 배치하는 대입문의 구조를 정의합니다. <표현식>은 하나의 <항>이 되거나 다시 <표현식> + <항>으로 확장될 수 있으므로 x = a, x = 3, x = a + 3과 같은 문장을 만들 수 있습니다. 이 예제에서는 식별자를 x와 a, 숫자를 0부터 3까지만 정의했으므로 그 밖의 문자와 숫자는 별도의 생성 규칙을 추가하지 않는 한 사용할 수 없습니다.

EBNF는 BNF를 어떻게 확장하는가?

EBNF(Extended Backus–Naur Form)는 반복·생략·묶음과 같은 구조를 더 간결하게 표현하도록 BNF를 확장한 표기법입니다. 괄호와 반복 기호의 정확한 의미는 표준이나 문서마다 다를 수 있으므로 해당 문서가 제시한 규칙을 먼저 확인해야 합니다.

교재 기준 표기	의미	예
{ }	안의 요소를 0회 이상 반복	<문자> { <문자> | <숫자> }
[ ]	안의 요소를 생략하거나 한 번 사용	[ "+" | "-" ] <숫자>
( )	여러 요소를 하나의 단위로 묶음	( <항> | <숫자> ) → 묶인 대안 중 하나를 선택
|	대안 중 하나를 선택	<문자> | <숫자>

<대입문> ::= <식별자> "=" <항> { "+" <항> } [ ";" ]
<항> ::= <식별자> | <숫자>
<식별자> ::= <문자> { <문자> | <숫자> }

이 EBNF는 BNF의 재귀 규칙을 반복과 선택 기호로 간결하게 표현한 예입니다. 대입문에는 식별자·등호·항이 반드시 한 번씩 나타나며, { "+" <항> }은 + 항을 0회 이상 반복할 수 있음을 뜻합니다. [ ";" ]은 문장 끝의 세미콜론을 생략하거나 한 번 사용할 수 있음을 나타냅니다. 또한 식별자는 문자로 시작하고 그 뒤에 문자 또는 숫자를 반복할 수 있으므로 x, total, count1과 같은 이름을 만들 수 있습니다. 단, <문자>와 <숫자>가 실제로 어떤 문자를 포함하는지는 별도의 생성 규칙에서 정의해야 합니다.

구문 도표는 문법을 어떻게 그림으로 표현하는가?

구문 도표(Syntax Diagram)는 BNF나 EBNF의 생성 규칙을 상자·원·화살표로 표현한 그래픽 표기법입니다. 시작 지점에서 화살표를 따라 끝까지 이동할 수 있는 경로가 문법상 허용되는 토큰 순서를 나타냅니다.

도형·기호	표현 대상	의미
사각형	비단말 기호	다른 문법 규칙을 참조하는 구성 요소
원 또는 둥근 도형	단말 기호	실제 입력에 나타나는 키워드·연산자·리터럴
화살표	흐름 방향	문법 요소를 읽고 결합하는 순서
분기 경로	선택	여러 대안 중 한 경로를 선택
되돌아가는 경로	반복	특정 요소를 여러 번 사용

이 구문 도표는 식별자와 등호 뒤에 항을 하나 배치한 다음, 필요에 따라 + 항을 반복하는 대입문의 흐름을 나타냅니다. 첫 번째 항에서 바로 끝으로 이동하면 x = a와 같은 문장이 되고, 반복 경로를 한 번 이용하면 x = a + 3, 여러 번 이용하면 x = a + 3 + 2와 같은 문장이 됩니다. 시작 지점에서 화살표를 따라 끝까지 도달할 수 있는 토큰의 순서가 문법에서 허용되는 문장입니다. 이 도표에서는 + 항의 반복 구조에 집중하기 위해 EBNF 예제의 선택적 세미콜론 [ ";" ]은 생략했습니다.

파스 트리는 문장의 구조를 어떻게 보여주는가?

파스 트리(Parse Tree)는 입력 문장이 문법의 시작 기호에서 어떤 생성 규칙을 거쳐 만들어졌는지를 트리로 표현한 것입니다. 루트에는 시작 기호, 내부 노드에는 비단말 기호, 잎 노드에는 실제 입력을 구성하는 단말 기호가 놓입니다.

• 루트 노드는 문법의 시작 기호인 <대입문>입니다.
• 비단말 노드는 생성 규칙을 적용할 때마다 자식 노드로 확장됩니다.
• 잎 노드를 왼쪽에서 오른쪽으로 읽으면 x = a + 3이 됩니다.
• 하나의 문장에 서로 다른 파스 트리가 만들어지면 문법이 모호할 수 있습니다.

이 파스 트리는 문장 x = a + 3이 앞에서 정의한 BNF의 생성 규칙에 따라 만들어지는 과정을 보여줍니다. 루트 노드인 <대입문>은 <식별자>, 등호, <표현식>으로 확장되고, 왼쪽 식별자는 x가 됩니다. 오른쪽 표현식은 <표현식> + <항>으로 확장되며, 각각 식별자 a와 숫자 3으로 변환됩니다. 트리의 잎 노드를 왼쪽에서 오른쪽으로 읽으면 원래 입력 문장인 x = a + 3이 완성됩니다.

트리 안에 <표현식>이 두 번 나타나는 것은 중복 오류가 아니라 재귀적인 생성 규칙을 적용했기 때문입니다. 바깥쪽 표현식은 전체 a + 3을 나타내고, 안쪽 표현식은 덧셈의 왼쪽 부분인 a를 나타냅니다. 이처럼 시작 기호에서 생성 규칙을 적용해 입력 전체를 단말 기호까지 유도할 수 있으면 해당 문장은 문법에 맞게 작성된 것으로 판단할 수 있습니다.

형식 언어는 무엇인가?

형식 언어(Formal Language)는 유한한 기호 집합인 알파벳과 형식 문법을 사용하여 정확하게 정의한 문자열의 집합입니다. 어떤 문자열이 언어에 포함되는지를 문맥적 해석이 아니라 형식 규칙으로 판정합니다.

구성 개념	의미	예
알파벳	문자열을 만드는 유한한 기호의 집합	Σ = {0, 1}
문자열	알파벳의 기호를 유한한 순서로 나열한 것	0101
빈 문자열	길이가 0인 문자열	ε
언어	정해진 조건이나 문법을 만족하는 문자열의 집합	짝수 개의 1을 포함하는 이진 문자열 집합
문법	언어의 문자열을 생성하는 형식 규칙	시작 기호와 생성 규칙

이 예제에서는 알파벳을 Σ = {0, 1}로 정의하므로 문자열은 0과 1만 사용하여 만들 수 있습니다. 0101은 알파벳의 기호를 유한한 순서로 나열한 문자열이고, ε는 문자가 하나도 없는 길이 0의 빈 문자열입니다.

언어는 이러한 문자열 전체가 아니라 특정 조건이나 문법을 만족하는 문자열만 모은 집합입니다. 표에서 제시한 언어는 1의 개수가 짝수인 이진 문자열의 집합입니다. 따라서 ε와 0은 1이 0개이므로 포함되고, 11과 0101은 1이 각각 2개이므로 포함됩니다. 반면 1, 01, 111처럼 1의 개수가 홀수인 문자열은 이 언어에 포함되지 않습니다.

문법은 이러한 언어에 속하는 문자열을 생성하는 형식 규칙입니다. 시작 기호에서 생성 규칙을 반복 적용하여 만들 수 있는 모든 단말 문자열을 모으면 그 문법이 정의하는 형식 언어가 됩니다.

형식 문법의 계층 구조는 어떻게 구분되는가?

형식 문법은 생성 규칙에 허용되는 제약의 정도에 따라 Type 0부터 Type 3까지 구분합니다. 번호가 커질수록 생성 규칙은 더 제한적이고 이를 인식하는 계산 모델은 더 단순해집니다.

유형	문법·언어	규칙의 특징	대표 인식 모델	주요 연결
Type 0	무제한 문법 재귀 열거 언어	생성 규칙의 형식에 가장 적은 제한	튜링 기계	일반적인 계산 가능성
Type 1	문맥 의존 문법 문맥 의존 언어	주변 문맥에 따라 비단말 기호를 치환	선형 한정 오토마타	문맥 조건을 포함한 언어
Type 2	문맥 자유 문법 문맥 자유 언어	규칙의 왼쪽이 하나의 비단말 기호	푸시다운 오토마타	프로그래밍 언어의 주요 구문
Type 3	정규 문법 정규 언어	선형 형태로 제한된 생성 규칙	유한 오토마타	토큰 패턴과 어휘 분석

정규 표현은 형식 언어에서 어떤 역할을 하는가?

정규 표현(Regular Expression)은 정규 언어에 속하는 문자열 패턴을 간결하게 기술하는 형식 표기입니다. 컴파일러의 어휘 분석에서는 식별자·숫자·공백·연산자 등의 토큰 패턴을 정의하는 데 활용할 수 있습니다.

정규 표현 예	나타내는 패턴	일치 예
[A-Za-z]	영문자 한 글자	A, z
[0-9]+	숫자 한 글자 이상	7, 2026
[A-Za-z][A-Za-z0-9]*	영문자로 시작하고 이후 영문자나 숫자가 반복되는 식별자	count1
ab*	a 뒤에 b가 0회 이상 반복	a, ab, abb
a|b	a 또는 b	a, b

• 정규 표현은 정규 언어를 표현하고 유한 오토마타로 인식할 수 있습니다.
• 정규 표현 자체는 유한한 길이지만 반복을 통해 무한한 문자열 집합을 나타낼 수 있습니다.
• 모든 문맥 자유 언어를 정규 표현만으로 표현할 수 있는 것은 아닙니다.
• 임의 깊이의 괄호 중첩처럼 재귀적인 구조는 일반적인 정규 언어의 범위를 벗어납니다.

시험에서 자주 혼동되는 개념

이번 장 핵심 요약

1. 프로그래밍 언어의 구문은 올바른 프로그램 문장을 만드는 형식 규칙입니다.
2. 어휘 분석은 문자 흐름을 식별자·키워드·리터럴·연산자·구분자 등의 토큰으로 나눕니다.
3. 구문 분석은 토큰 배열이 문법 규칙에 맞는지 확인합니다.
4. 식별자는 프로그램 구성 요소에 붙이는 이름이며 언어의 명명 규칙을 따라야 합니다.
5. 키워드는 문법상 특별한 의미를 가지고 예약어는 일반 식별자로 사용할 수 없습니다.
6. 주석은 사람의 이해와 유지보수를 돕지만 일반적으로 실행 의미에서 제외됩니다.
7. BNF는 비단말 기호를 단말·비단말 기호의 조합으로 정의합니다.
8. EBNF는 반복·생략·묶음을 확장 기호로 간결하게 표현합니다.
9. 구문 도표는 문법의 선택과 반복을 흐름으로 표현합니다.
10. 파스 트리는 시작 기호에서 입력 문장이 생성되는 문법적 구조입니다.
11. 형식 언어는 알파벳 위에서 문법이나 형식 조건으로 정의한 문자열의 집합입니다.
12. Type 0은 튜링 기계, Type 1은 선형 한정 오토마타와 연결됩니다.
13. Type 2 문맥 자유 문법은 푸시다운 오토마타와 연결됩니다.
14. Type 3 정규 문법은 유한 오토마타와 연결됩니다.
15. 정규 표현은 정규 언어의 패턴을 표현하며 주로 어휘 분석에 활용됩니다.
16. 정규 표현은 유한하게 작성되지만 무한한 문자열 집합을 나타낼 수 있습니다.

복습 문제

프로그램의 설명을 기록하여 판독성을 높이지만 일반적으로 실행 의미에는 영향을 주지 않는 구문 요소는?

주석입니다.

변수·함수·클래스 등에 붙이는 이름은?

식별자입니다.

언어 문법에서 특별한 의미를 가진 단어는?

키워드 또는 핵심어입니다.

일반 식별자로 사용할 수 없도록 언어가 확보한 단어는?

예약어입니다.

BNF에서 정의를 나타내는 대표 기호는?

::=입니다.

BNF에서 여러 대안 중 하나를 선택하는 기호는?

|입니다.

EBNF에서 교재 기준으로 반복되는 부분을 나타내는 기호는?

{ }입니다.

EBNF에서 생략 가능한 요소를 나타내는 기호는?

[ ]입니다.

문법 규칙을 상자·원·화살표의 흐름으로 표현하는 방법은?

구문 도표 또는 구문 다이어그램입니다.

입력 문장이 문법 규칙에 따라 유도된 구조를 트리로 표현한 것은?

파스 트리입니다.

파스 트리의 잎 노드에는 주로 무엇이 놓이는가?

입력을 구성하는 단말 기호가 놓입니다.

Type 0 문법을 인식하는 대표 계산 모델은?

튜링 기계입니다.

Type 1 문법을 인식하는 대표 계산 모델은?

선형 한정 오토마타입니다.

Type 2 문맥 자유 문법을 인식하는 대표 계산 모델은?

푸시다운 오토마타입니다.

Type 3 정규 문법을 인식하는 대표 계산 모델은?

유한 오토마타입니다.

정규 언어의 문자열 패턴을 기술하는 형식 표기는?

정규 표현입니다.

토큰 패턴은 주로 어떤 문법 계층과 관련되는가?

Type 3 정규 문법과 정규 언어입니다.

중첩된 프로그램 문장 구조를 표현하는 데 주로 사용하는 문법은?

Type 2 문맥 자유 문법입니다.