형식 언어 (3) - 형식 문법 표현 방법

형식 언어 (3) - 형식 문법 표현 방법

형식 언어(formal language)는 규칙적인 구조와 규칙에 따라 생성된 문자열의 집합입니다.
이러한 규칙은 문법(grammar)이라고도 하며, 형식 언어는 이러한 문법에 따라 생성된 문자열들의 집합으로 구성됩니다.

형식 문법은 크게 2 가지 방법으로 정의 할 수 있습니다.
생성 규칙 만을 가지고 표현하거나 G = Vn,Vt, P, S로 정의하는 것입니다

오늘의 규칙

1. 대문자로 표기된 기호와 시작 기호를 나타내는 기호 S는 논터미널 기호입니다.
2. < >로 묶어서 나타낸 기호도 논터미널 기호입니다.
3. 소문자 영문자, 연산자 기호, 구분자, 숫자 등은 터미널 기호입니다.
4. 대문자 끝부분의 기호는 터미널과 논터미널 기호를 나타내는 문법 기호입니다.
5. 소문자 영문자는 터미널 기호들로 이루어진 문자열을 나타냅니다.
6. α, β 등 그리스어 소문자는 문법 기호로 구성된 문자열을 나타냅니다.
7. 생성 규칙의 왼쪽에 있는 기호가 시작 기호입니다.
8. 생성 규칙의 왼쪽에 같은 기호로 구성된 생성 규칙이 여러 개 있을 때 축약해서 사용할 수 있습니다.
   • α → β1 | β2 와 같이 표현

문법 G = Vn,Vt, P, S 정의

• 기호(논터미널,터미널)이 모여 문법 기호(어휘)가 되는 것입니다

연습 문제 1

연습 문제 2

• 연산자는 터미널 기호
• 보통은 생성 규칙 쪽 왼쪽에 처음 나타나는 기호가 시작 기호이다.
  • E