형식 언어와 유한 오토마타

Chapter 03

01. 형식 언어

02. 형식 문법

03. 문법 표기법

정규표현

정규표현

Regular Expression 은 재귀적으로 정의됨

base step

1. ∅ 는 공집합을 나타내는 정규표현

2. ε 는 공문자열을 나타내는 정규표현

3. 터미널 기호인 a 는 집합 { a } 를 나타내는 정규표현

recursive step : r, s 가 정규언어 L(r), L(s) 를 나타내는 정규표현일 때,

1. (r) + (s) 는 L(r) U L(s) 를 나타내는 정규표현

2. (r)·(s) 는 L(r)·L(s) 를 나타내는 정규표현

3. (r)*는 {L(r)}* = {ε} U {L(r)}¹ U {L(r)}² U ... 를 나타내는 정규표현

구문도표

그림이라 생략..

BNF 표기법 - Backus-Naur Form

<, >, ::=, | 등의 메타기호를 사용해서 문법을 표기함

• 메타기호는 문법기호(터미널 기호 + 논터미널 기호) 와는 다르게, 문법 자체와는 상관없는 기호들

C 언어의 식별자identifier 를 BNF 로 나타내보자( _ 없이)

<ID> ::= <E> | <ID> <E> | <ID> <N> <E> ::= a | b | ... | z <N> ::= 0 | 1 | ... | 9

시작은 항상 영문이기 때문에, prefix 가 불변이라는 특성이 있음 이를 재귀적으로 잘 표현하면 됨

단점

• 예를 들어, 최대 문자열의 길이가 10이라면?

  • <E><E><E><E><E><E><E><E><E><E>

  • 너무 번거롭다

EBNF 표기법 - Extended BNF

• BNF 에 {, }, [, ] 메타기호를 추가

• 횟수를 표현하기에 적합함

참고링크

• C 언어의 BNF 표기법
• Cpp eBNF표기법