3장 context-free grammars & parsing

Parsing

Scanning 과정에서 얻은 토큰들로 parse tree나 syntax tree를 만드는 과정.

Context-Free Grammars

syntactic structure(구문 구조)를 기술하는 문법.

이런 유형의 문법을 BNF라 한다.

exp → exp op exp | (exp) | number  

첫번째 symbol인 exp는 이 구조의 이름

→ 는 두번째 symbol

exp op exp | (exp) | number 는 symbol들의 string. token일 수도 있고, name이거나 '|'

derivation은 grammar rule의 오른쪽 부분을 구조 이름으로 교체 해 가는 과정. 결국은 Token symbols의 string이 된다.

Nonterminals and terminals

구조 이름은 nonterminals

token은 terminals

left recursive

A → Aa|a

A => Aa => Aaa => Aaaa=> aaaa

right recursive

A → aA|a

A => aA => aaA => aaaA => aaaa

parse tree

유도과정(derivation)을 구조화한 트리

exp → exp op exp | (exp) | number

op → + | - | *

(25+12)*21의 parse tree

Abstract syntax trees

사용자 편의대로 파스트리를 단순화.

Non terminal이 없다.

Ambiguity(모호성)

두가지 이상의 유도 과정으로 같은 문자열을 생성할 때.

34-3*42는 (34-3) * 2 와 34-(3*42) 두가지로 생성 가능하다.

모호성을 없애기 위해 문법을 새로 작성하거나

우선순위를 주거나, 결합 순서를 주는 방법 등이 있다.

EBNF(확장 BNF)

{}

Repetition

A → Aα | β (left recursive) : A → β{α}

A → αA | β (right recursive) : A →{α}β

[]

Optional

if-stmt → if (exp) statement [ else statement]

()

choice

exp → exp (“+” | “-” | “*” ) exp | “(“ exp “)” | number

참고 및 그림 출처
한양대 이욱세 교수님 강의노트