regular expression : the lexical structure of tokens

• recognizer : FA (scanner)
• id = (l + _)(l + d +_)*

CFG : the syntactic structure of programming languages

• recongnizer : PDA(parser)

CFG form : 촘스키 계층 type2

---

유도와 유도트리

sentential form(유도에서 nonterminal이 있는거)에서 어느 nonterminal을 선택할 것인가?

• leftmost derivation : 가장 왼쪽에 있는 nonterminal을 대치해나가는 방법
• rightmost derivation : 가장 오른쪽에 있는 nonterminal을 대치.

parse : parser의 출력형태

E->E+E | E*E | (E) | num
2*5+7을 만들어보자.

• left parse : leftmost 에서 적용된 생성규칙번호

top-down parsing
start symbol 로 부터 sentence 생성

E->E+E->E*E+E->2*E+E->2*5+E->2*5+7
  1    2      4      4      4
  
parse - 12444

• right parse : rightmost 에서 적용된 생성 규칙번호의 역순

bottom-up parsing
sentence 로부터 nonterminal 로 reduce되어 결국엔 start symbol로 reduce

E->E+E->E+7->E*E+7->E*5+7->2*5+7
  1    4    2      4      4
  
parse - 44241

유도트리

결과 sentence는 동일하지만 유도의 방법이 ambiguous grammar 일 수 있다.
즉, 같은 sentence를 생성하는 tree가 2개 이상 존재할 때 이 grammar를 ambiguous하다고 하며, 결정적인 파싱을 위해 ambiguous 한 grammar를 unambiguous하게 변환해야 한다.

E -> E*E | E+E | a

위와 같은 문법에서 *과 +의 연산자 우선순위가 같아서
a*a+a 는 (a*a)+a, a*(a+a)로 두가지로 계산될수있다.
그래서 아예 모호하지 않게 문법자체를 조금 수정해주면 된다.

*가 +보다 우선순위가 높기때문에 문법에서 좀더 이후에 변환되도록 해주면 된다.
E -> E+T | T
T -> T*F | F
F -> a

로 문법을 규정하면 무조건 *가 +의 우선순위가 적용된 결과가 나온다.

---

문법 변환

sentence에는 여러 문법으로 만들어질수있다.
그래서 그 각각의 문법은 equivalent하다 볼수있는데 이 문법을 좀더 그리고 필요한 내용만 적히도록 변환해주는 것이 좋다.
Useless productions은 제거, single productions 등등을 쓸수있다.

---

CFG 표기법

• BNF, EBNF, syntax diagram

BNF의 방법에서 반복, 선택등을 추가하여 EBNF를 추가한다.
E -> E+T | T는 E->a|(A{+A})로 나타낼수있다.

EBNF

{a} : a 반복
[a] : a를 선택할수도 opt
(a|b) : a아니면 b 택일

syntax diagram

원 : terminal symbol
사각형 : nonterminal symbol
화살표 : 흐름경로

---

PDA (Push-down Automata)

• pushdown list, input tape, finite state control

FA에 storage 까지 추가된다.

PDA P = {Q,Σ,Γ,δ,q0,z,F) 7개의 term
Q - 상태 심벌의 유한집합
Σ - 입력 알파벳의 유한 집합
Γ - 스택 심벌의 유한 집합
δ - 사상함수
q0 - 시작상태
z - 스택의 시작 심벌
F - 종결상태의 집합.

예를 보자
P = ({q0,q1,q2}, {0,1}, {Z,0}, δ, q0, Z, {q0})

δ(q0,0,Z) = {(q1,0Z)}
δ(q1,0,0) = {(q1,00)}
δ(q1,1,0) = {(q2,$\epsilon$)}
δ(q2,1,0) = {(q2,$\epsilon$)}
δ(q2,1,Z) = {(q1,$\epsilon$)}
δ(q2,$\epsilon$,Z) = {(q1,$\epsilon$)}

입력값이 스택으로 넘어가는 shift와 스택의 nonterminal을 묶어버리는 reduce 작업을 통해 PDA는 인식한다.

(q0, aabbaa, Z)

• (q0, abbaa, aZ)
• (q0, baa, aaZ)
• (q0, baa, baaZ)
• (q0, baa, SbaaZ)
• (q0, aa, bSbaaZ)
• (q0, aa, SaaZ)
• (q0, a, aSaaZ)
• (q0, a, SaZ)
• (q0, empty, aSaZ)
• (q0, empty, SZ)
• (q0, empty, $\epsilon$)

L = {ww^R | w = {a,b}+}

---

Le(P) : stack을 empty로 만드는 PDA에 의해 인식되는 string의 집합. 즉 종결상태에서 input, stack이 둘다 empty가 될것이다.

---

Context free, PDA

• Topdown method
  a + a * a 인식과정
  (q, a + a * a, E)
  (q, a+a*a, E+T)
  (q, a+a*a, T+T)
  (q, a+a*a, F+T)
  (q, a+a*a, a+T)
  (q, a+a*a, +T)
  (q, +a*a, T)
  (q, a*a, T*F)
  (q, a*a, F*F)
  (q, a*a, a*F)
  (q, *a, *F)
  (q, a, F)
  (q, a, a)
  (q, empty, empty)

stack에서 왼쪽이 top이다.

• Bottom-up method
  a + a * a 인식과정
  (q, a + a * a, $) shift a
  (q, +a*a, $a) reduce F->a
  (q, +a*a, $F) reduce T->F
  (q, +a*a, $T) reduce E->T
  (q, +a*a, $E) shift +
  (q, a*a, $E+) shift a
  (q, *a, $E+a) reduce F->a
  (q, *a, $E+F) reduce T->F
  (q, *a, $E+T) shift
  (q, a, $E+T) shift a
  (q, empty, $E+T*a) reduce F->a
  (q, empty, $E+T*F) reduce T->T*F
  (q, empty, $E+T) reduce E->E+T
  (q, empty, $E) accept
  (q, empty, $) end

stack에서 오르쪽이 top이다.

---

구문분석

Top-down : recursive descent parser, predictive parser
재귀적으로 계속 생성하는 문제가 생길수있다. 기계가 input과 비교도 못해서 끝나지도 않는다. 그래서 재귀없는 문법으로 바꿔줘야 동작한다. extended BNF 필요.
Bottom-up : precedence parser, shift-reduce parser
handle을 찾아서 nonterminal을 reduce할수있는데 사실 이 handle을 판단하는게 쉽지않다.
이 handle을 유지하기 위해서 stack storage 가 필요하다.
LL, RR 둘이 방향이 같으면 top
LR, RL 방향이 다르면 bottom
rightmost derivation in reverse

handle 결정방식으로 다음 세가지가 있다.
SLR(Simple LR)
LALR(LookAhead LR)
CLR(Canonical LR)