LL(1) parser ¶
- 처음 한 글자를 보고 구분할 수 있어야 함.
- LL(1) parser에서 불가능한 경우
- A ::= AB (left recursive가 발생하기 때문에 처리 불가.) elimination 필요.
- A ::= BC | BD (left common prefix로 첫 글자인 B하나만으로 두 경우의 구분이 불가.) factorization 필요.
- A ::= AB (left recursive가 발생하기 때문에 처리 불가.) elimination 필요.
- FIRST(A) : non-terminal A의 첫 토큰의 집합.
- FOLLOW(A) : non-terminal A의 뒤에 올 수 있는 토큰의 집합.
- LL(1) parser이기 위해서는 A ::= B | C에서 FIRST(B)와 FIRST(C)의 교집합이 공집합이어야 한다.
- 만약 FIRST(B)가 empty를 가지고 있을 경우 FOLLOW(A)와 FIRST(C)의 교집합도 공집합이어야 한다.
- LL(1) parser이기 위해서는 A ::= B | C에서 FIRST(B)와 FIRST(C)의 교집합이 공집합이어야 한다.
- LR parser에서도 stack을 사용했었는데 LL(1) parser에서 stack을 사용하는 것과 비교했을 때 stack에 들어가는 정보에 차이가 있음.
- LR parser에서는 입력으로 들어온 토큰들을 stack으로 관리했었는데(실제 값인 1이나 + 같은것들) LL(1) parser의 table은 지금 parsing하고자 하는 심볼(Number나 Factor같은것들)이 stack에 들어와야 함.
- LR parser에서는 입력으로 들어온 토큰들을 stack으로 관리했었는데(실제 값인 1이나 + 같은것들) LL(1) parser의 table은 지금 parsing하고자 하는 심볼(Number나 Factor같은것들)이 stack에 들어와야 함.
Chomsky Hierarchy ¶
α, β -> terminal or non-terminal A, B -> non-terminal a, b, c -> terminal 이라고 할 때
- Type-0 : unrestricted grammars
- α -> β로 변경될 수 있는 문법. Type-0은 프로그래밍 언어적으로 별로 중요하지 않다고 함.
- α -> β로 변경될 수 있는 문법. Type-0은 프로그래밍 언어적으로 별로 중요하지 않다고 함.
- Type-1 : context sensitive grammars
- αAβ -> αBβ로 변경될 수 있는 문법. 앞 뒤에 특정 컨텍스트가 있을 경우에 변경됨. 이 경우에는 α, β가 특정 컨텍스트에 해당함.
- αAβ -> αBβ로 변경될 수 있는 문법. 앞 뒤에 특정 컨텍스트가 있을 경우에 변경됨. 이 경우에는 α, β가 특정 컨텍스트에 해당함.
- Type-2 : context free grammars
- A -> αBβ로 변경될 수 있는 문법. 컨텍스트에 영향 없이 변경. α가 A를 가져서 다시 A로 돌아갈 수 있는 경우도 있음.
- A -> αBβ로 변경될 수 있는 문법. 컨텍스트에 영향 없이 변경. α가 A를 가져서 다시 A로 돌아갈 수 있는 경우도 있음.
- Type-3 : regular grammars
- A -> a | aB로 변경될 수 있는 문법. 변경됐을 때 다시 A로 돌아갈 수 있는 방법이 없음.
- A -> a | aB로 변경될 수 있는 문법. 변경됐을 때 다시 A로 돌아갈 수 있는 방법이 없음.
- Type들은 포함관계가 있으며 Type-0이 Type-1을 포함하고 1이 2를 포함하는 식임.
- Type-1와 Type-2의 차이는 주변 컨텍스트에 관계없이 produce가 가능한가의 여부.
- 1 + 2의 결과와 "1" + 2의 결과가 다르게 해석되는 것이 type-1의 요소에 해당하는 것. 같은 1이지만 1의 주변에 다른 컨텍스트("")가 있는 것에 따라서 1을 숫자/문자로 다르게 해석하기 때문임.
- syntax analysis과정이 Type-2에 해당하는 요소까지만 다룬 것이고 Type-1(context sensitive)의 요소들을 다루기 위해서 semantic analysis를 수행하는 것임.
- 컴파일러에서는 크게 static한 semantic과 dynamic한 semantic이 있음. 컴파일러가 수행하는 semantic 분석은 static한 분석이고 devide by zero, out of index같은건 체크를 runtime으로 미룬 것으로 dynamic한 것임.
class Shape class Circle class Square area(Shape) Shape s area(s)
- 위의 케이스에서 s가 Shape타입인지 확인하는게 static semantic analysis이고 실제 런타임에 들어온건 Circle이나 Square일 경우 이를 처리하는건 dynamic semantic analysis에 해당함.
- 언어마다 static/dynamic한 처리에는 차이가 있을 수 있음.
- Java의 경우 실행시 null값 확인을 하지만 C#같은 경우는 nullable이 아니면 null을 못넣음. 이 경우 null의 처리에 대해서 java는 dynamic한데 C#은 static하다는 것임.
- Java의 경우 실행시 null값 확인을 하지만 C#같은 경우는 nullable이 아니면 null을 못넣음. 이 경우 null의 처리에 대해서 java는 dynamic한데 C#은 static하다는 것임.
수식 파서 ¶
- 이전의 과정에서 생성된 AST에 attribute를 추가해야 semantic analysis가 가능함.
- AST에서 root에서 leaf쪽으로 타고 내려가는 attribute들을 inherit attribute라고 하고 반대로 leaf에서 root쪽으로 전달되는 attribute들은 synthesis attribute라고 함.
- context sensitive한 판단을 하기 위해서는 leaf node쪽에 있는 context들을 root쪽까지 끌어올려야 하며, 이는 AST의 순회가 dependent한 attribute들에 따라 여러번 수행될 수 있다는 소리임.
EBNF ¶
< EBNF >
Expr ::= Term([+|-] Expr)?
Term ::= Factor ([*|/] Term)?
Factor :: = (Expr)
| Value
Value ::= Integer | Double
s : synthesis i : inherit < Synthesis, Inherit > Expr ::= Term (s) expr.isDouble = term.isDouble (i) term.type = if expr.isDouble then double else int Expr1 ::= Term [+-] Expr2 (s) expr1.isDouble = term.isDouble or expr2.isDouble (i) term.type = expr1.isDouble then double else int (i) expr2.type = expr1.isDouble then double else int Factor ::= (Expr) (s) factor.isDouble = expr.isDouble (i) expr.type = factor.isDouble then double else int Factor ::= Value (s) factor.isDouble = value.isDouble (i) value.type = factor.isDouble then double else int Value :: Decimal Integer (s) value.isDouble = false (i) value.type = value.type == double then double else int Value :: Double (s) value.isDouble = true (i) value.type = value.type == double then double else int
