컴파일러 구성론 (Compiler Construction)

예) 1. context-free 문법의 예
G = ({S, C}, {a, b}, P, S)
P : S → aCaC → aCaC → b
-----> L(G) = {anban | n ≥ 0}

2. regular 문법의 예
G = ({S, B, C}, {a, b}, P, S)
P : S → aSS → aBB → bC
C → aCC → a
-----> L(G) = {anbam | n, m ≥ 1}
(note) BNF나 syntax graph로 표현되는 Grammar = context-free grammar(CFG)

제 3 장 정규 언어

▶ 정규언어(regular language) : token의 형태를 기술하는 데 사용
표현방법 : 정규 문법(regular grammar), 정규 표현(regular expression), 유한 오토마타
(finite autommata)

3.1 정규 문법과 정규 언어
▶ 정규 문법 : N. Chomsky의 type 3 grammar
▶ compiler의 어휘분석 과정에서 인식되는 토큰(어휘)의 구조를 표현
▶ right-linear Grammar(A → aB)와 left-linear Grammar(A → Ba)
(정의 3.1) 각 생성 규칙의 형태가 다음과 같을 때 정규 문법이라고 한다.
(1) A → aB, A → a, 여기서 a ∈ VT이고 A, B ∈ VN
(2) 만약 S → ε이면, S가 다른 production의 오른쪽에 나타나지 않아야 한다.
예) S → aA, S → bB, S → b, A → bA, A → a, B → bS
(주) 정규 …(생략)