input → lexical analysis → token! → syntax analysis → AST! → output

• context-free grammar

Derivation: start symbol S 에서 목적 string까지 가는 sequence of grammar rule applications.

string이 해당 문법의 언어에 속하는걸 보이는 것.

• leftmost derivation: always choose leftmost nonterminal to rewrite
• rightmost derivation: always choose rightmost nonterminal to rewrite
• deterministic하게 nonterminal 고르면 뭐가 좋은가? → 그냥 적용할 rule만 순서대로 넣어주면 됨
• string이 1개 초과의 parsing tree를 가진다? → ambiguous grammar

left recursion??

Expression → Expression + Term 같은 경우 생성규칙이 순환적으로 적용, 무한루프 가능…

• top-down parsing

• bottom-up parsing

recursive descent parser