형식언어

문법

프로그래밍 언어의 구조를 정의하는 규칙의 집합을 의미한다, Terminal Symbol,Non-Terminal Symbols, 생성 규칙, 시작 심볼의 네 가지 요소로 구성된다.

Terminal Symbol

더 이상 다른 심볼로 분해될 수 없는 언어의 가장 기본적인 단위이다. 프로그래밍 언어에서 어휘(Lexeme)또는 토큰(Token)이라고도 불리며, 실제 소스 코드에 나타나는 키워드, 연산자, 숫자, 식별자 등이 해당된다.

• 키워드: if, while, for, int
• 연산자: +, -, *, /, =
• 구두점: (, ), {, }, ;
• 상수 및 식별자:: 123, myVariable, "hello"

Non-terminal Symbol

다른 심볼들의 집합을 나타내는 추상적인 개념으로, 문장 구조나 문법적인 단위를 표현한다. 즉, 하나 이상의 terminal 심볼 또는 Non-terminal 심볼로 대체될 수 있는 변수와 같은 역할을 한다. 보통 꺾쇠(< >)로 묶어 표현한다.

• <expression> (표현식): <term> + <term> 과 같이 더 작은 단위로 나뉠 수 있습니다.
• <statement> (문장): <if-statement>, <assignment-statement> 등으로 구체화될 수 있습니다.
• <term> (항): <factor> * <factor> 등으로 구성될 수 있습니다.

생성 규칙

Non-terminal 심볼이 어떻게 terminal 심볼이나 다른 Non-terminal 심볼의 조합으로 확장될 수 있는지 정의하는 규칙이다. 언어의 문법 구조를 구체적으로 명시하며, '->' 또는 '::=' 기호를 사용하여 표현한다.

• 형식: A -> α (A는 α로 대체될 수 있다.)

예시

• <assignment> → <identifier> = <expression>;

  • 이 규칙은 '대입문' (<assignment>)이 '식별자'(<identifier>), 등호(=), '표현식'(<expression>), 세미콜론(;)의 순서로 구선됨을 정의한다.

• <expression> → <expression> + <term>

  • '표현식'은 또 다른 '표현식'과 '항'의 덧셈으로 구성될 수 있음을 나타낸다.

시작 심볼

모든 생성 규칙이 파생되기 시작하는 최상위 Non-terminal 심볼이다. 이는 문법적으로 올바른 프로그램 전체를 나타내는 가장 큰 개념의 시볼이며, 모든 유효한 문장 구조는 이 시작 심볼로부터 파생될 수 있어야 한다.

• <program>: 프로그램 전체 구조를 나타내는 시작 심볼
• <compilation-unit>: 하나의 완전한 소스 파일을 의미하는 시작 심볼

---

문법의 분류

문법은 생성 규칙에 따라 촘스키 계층(Chomsky Hierarchy)이라는 4가지 유형으로 분류된다. 아래로 갈수록 규칙이 더 엄격해지고, 문법 구조는 단순해진다.

Type 0 문법(Unrestrcted Grammar, ug)

가장 일반적인 형태의 문법으로, 생성 규칙에 아무런 제약이 없다.

• 규칙 형태: α -> β

  • a는 최소 하나 이상의 단말 또는 비단말 심볼을 포함한다(empty 안됨).
  • b는 단물 또는 비단말 심볼의 임의의 조합이거나 비어있을 수 있다.

• 인식 기계: 튜링 기계 (Turing Machine)

  • 컴퓨터로 해결할 수 있는 모든 문제를 표현할 수 있을 만큼 강력한 문법이다.

• 특징: 너무 일반적이어서 실제 프로그래밍 언어를 분석하는 데 거의 사용되지 않는다.

Type 1 문법(Context-Sensitive Grammar, csg)

규칙의 좌변(a)이 우변(b)으로 대체될 때,특정 문맥(Context) 안에서만 치환이 가능하도록 제약을 둔 문법이다.

• 규칙 형태: αAβ → αγβ (단, γ는 비어있을 수 없음)
  • 비단말 심볼 A가 γ로 바뀌기 위해서는 반드시 앞뒤에 α와 β라는 문맥이 있어야 합니다.
  • 가장 중요한 제약은 우변의 길이가 좌변의 길이보다 항상 크거나 같아야 한다는 것이다 (|αAβ| ≤ |αγβ|).
• 인식 기계: 선형 유계 오토마타 (Linear Bounded Automaton)
• 특징: 자연어의 일부 복잡한 구조를 설명하는 데 사용될 수 있으나, 프로그래밍 언어 컴파일러에서는 너무 복잡하여 잘 쓰이지 않는다.

Type 2 문법(Context-Free Grammar)

규칙을 적용할 때 주변 문맥을 전혀 고려하지 않는 문법이다. 즉, Non-terminal 심볼 하나는 언제든지 규칙의 우변으로 대체될 수 있다.

• 규칙 형태: A → β
  • 규칙의 좌변은 하나의 비단말 심볼이어야 한다.
  • β는 단말 또는 비단말 심볼의 임의의 조합이다.
• 인식 기계: 푸시다운 오토마타 (Push-down Automation)
• 특징: 대부분의 프로그래밍 언어의 구문 구조(Syntax)를 정의하는 데 가장 널리 사용된다. 예를 들어, if문, for문, 함수의 구조 등을 이 문법으로 명확하게 표현할 수 있다.

Type 3(Regular Grammar)

가장 제약이 강하고 단순한 구조를 가진 문법이다. 규칙의 우변 형태가 매우 제한적이다.

• 규칙 형태:
  • 우선형 정규 문법: A → aB 또는 A → a
  • 좌선형 정규 문법: A → Ba 또는 A → a
• 인식 기계: 유한 오토마타 (Finite Automation) / 정규 표현식 (Regular Expression)
• 특징: 컴파일러의 어휘 분석(Lexical Analysis) 단계에서 사용된다. 소스 코드를 키워드(if), 연산자(+), 식별자(myVar)와 같은 의미 있는 단위(토큰)로 분리하는 데 쓰인다. 정규 표현식이 바로 이 정규 문법에 기반한다.