1. concrete syntax / abstract syntax
프로그래밍 언어의 문법은 크게 concrete syntax와 abstract syntax로 구성되어 있음.
concrete syntax는 프로그램을 실제 문자열로 표현하는 방법을 다루는 거고, abstract syntax는 이 표현의 대상인 프로그램을 문법적 측면에서 정의함. abstract syntax에서는 프로그램을 문자열로 직접 다루지 않음.

예를 들어서 덧셈, 곱셈, 상수, 괄호가 있는 concrete syntax는 CFG를 사용해서 아래처럼 정의할 수 있음

E -> T | T '+' E
T -> U | U '*' T
U -> N | '(' E ')'
N -> '0' | '1' | '2' | ...

이 문법에서는 E(expression), T(term), U(unit) 을 구분하고 있지만 얘들은 concrete syntax 수준에만 있는 것들이고, abstract syntax에서는 이런 구분이 불필요함.

E -> N | E + E | E * E
N -> natural number

abstract syntax에서는 애초에 프로그램이 트리로 표현되기 때문에 괄호나 fixity에 따른 구분(E, T, U)이 없음. concrete syntax에서 그런 구분이 필요한 이유는 syntax tree를 문자열로 표현했을 때 ambiguity가 발생하지 않도록 세심한 처리가 필요하기 때문임. 예를 들어서 concrete syntax를
E -> N | E '+' E | E '*' E
이렇게 정의하면 "2 * 3 + 4" 를 (2 * 3) + 4 로 읽어야 하는지 2 * (3 + 4) 로 읽어야 하는지 알 수 없게 됨.

파서가 하는 일은 먼저 concrete syntax에 기반해서 문자열을 concrete syntax tree(parse tree랑 같은 뜻임)로 바꾸고, 그걸 다시 abstract syntax tree로 변환한다고 보면 됨.
https://ropas.snu.ac.kr/~dreameye/PL/slide/PL2.pdf 이 자료에도 concrete/abstract syntax에 대한 설명이 나오는데, 개인적으로 concrete syntax에 대한 설명은 약간 아쉬움. "프로그램을 읽는 방법"이라는 표현은 concrete syntax보다는 뒤에서 설명할 generative grammar와 parsing algorithm의 차이를 대비시키기에 더 어울린다고 생각함.

2. generative grammar & algorithm / analytic grammar
그럼 concrete syntax를 어떻게 정의할 수 있을까?

가장 흔하게 사용되는 방법은 Noam Chomsky가 만든 generative grammar인데, generative grammar는 말이 되는 문자열을 만드는 방법을 제시함으로서 문법을 정의함. 아까 예로 든 CFG(context free grammar)나 regular language, context sensitive language 등이 전부 generative grammar의 일종임.

generative grammar의 특징중 하나는 문법이 애매할 수 있다는 점임. 문자열을 만드는 방법만 제시하니까 A방법으로 만든 문자열하고 B방법으로 만든 문자열이 충돌할 수 있는거지. 자연어에서는 이런 ambiguity가 필수적이지만 프로그래밍 언어에서는 피해야 하기 때문에 아까 말했듯이 문법을 설계할 때 주의해야 함.

그리고 generative grammar는 문장을 만드는 법만 알려주고 읽는 법(파싱하는 법)은 안알려줌. 그래서 별도의 파싱 알고리즘이 필요하고 어떤 알고리즘으로 파싱될 수 있느냐에 따라서 LL(k)니 LR(k)니 LALR이니 하는 구분이 생김.

이렇게 문법 정의랑 알고리즘이 따로 노는게 불편해서 나온게 PEG 같은 analytic grammar임. analytic grammar는 문법을 정의할 때 애초에 파싱하는 방법을 고려해서 애매함, 비결정성이 없게 만듬

개인적으로는 analytic grammar 보다는 generative grammar가 더 맘에 듬. 일단 비결정성 자체가 굉장한 추상화인데 그걸 빼버리는 점이 별로. 단적으로 regex를 NFA로 표현하는건 쉽지만 DFA로 표현하는건 까다로움.


1번은 사람들이 parse tree랑 AST는 아는데 concrete/abstract syntax는 생각보다 잘 모르는것 같아서 얘기한거고
2번은 generative grammar와 parsing algorithm의 구분에 대해서 얘기하고 싶었는데 찾아보니 analytic grammar란 것도 있길래 추가해서 써봄