형식언어 입문

I. Introduction

▶ : the lexical structure of tokens

- recognizer: FA(=> )

- id = l(l + d)*
sc = (string constant)

▶ CFG: the of programming languages

- recognizer : PDA(=> )

▶ CFG로 programming language를 표현할 경우의 장점:

1. 이해하기 쉽다.
2. CFG로 부터 recognizer를 구성할 수 있다.
3. 프로그램의 구조를 production rule에 의해 구분할 수 있으므로에 유용하다.

▶ CFG의 form : N. Chomsky의 grammar

A -> α, where A ∈ VN, α ∈ .

▶ recursive construction

ex) E -> E OP E | (E) | -E | id
OP -> + | - | * | / | ↑

VN = { , }
VT = { , , , , , , , }

ex) -> `if` `then`

VN : 와 사이에 기술된 symbol.
VT : 와 사이에 기술된 symbol.

▶ : α1 => α2

- start symbol로 부터 sentence를 생성하는 과정에서
nonterminal을 이 nonterminal로 시작되는 생성 규칙의
right hand side로 대치하는 과정.