New Compile Error/2014_05_24

LL(1) parser ¶

처음 한 글자를 보고 구분할 수 있어야 함.
LL(1) parser에서 불가능한 경우
- A ::= AB (left recursive가 발생하기 때문에 처리 불가.) elimination 필요.
- A ::= BC | BD (left common prefix로 첫 글자인 B하나만으로 두 경우의 구분이 불가.) factorization 필요.
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)의 교집합도 공집합이어야 한다.
LR parser에서도 stack을 사용했었는데 LL(1) parser에서 stack을 사용하는 것과 비교했을 때 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-1 : context sensitive grammars
- αAβ -> αBβ로 변경될 수 있는 문법. 앞 뒤에 특정 컨텍스트가 있을 경우에 변경됨. 이 경우에는 α, β가 특정 컨텍스트에 해당함.
Type-2 : context free grammars
- A -> αBβ로 변경될 수 있는 문법. 컨텍스트에 영향 없이 변경. α가 A를 가져서 다시 A로 돌아갈 수 있는 경우도 있음.
Type-3 : regular grammars
- A -> a | aB로 변경될 수 있는 문법. 변경됐을 때 다시 A로 돌아갈 수 있는 방법이 없음.

[edit]

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

NewCompileError/2014_05_24 (rev. 1.16)

New Compile Error/2014_05_24

LL(1) parser ¶

Chomsky Hierarchy ¶

EBNF ¶