[Compiler] 3.3. LR Parser (Bottom-up Parser)

LL Parsing과 반대로, right derivation에서 작동하며, 반대로 작동한다. 따라서 production이 아니라, reduction을 하는 것이다.

Left factoring과 left-recursive 제거가 필요 없다.

Shift-reduce

$\omega = \alpha|\beta$

• $\omega$: CFG의 sentinel form
• $\alpha$: parser에 의해 이미 검사됨. terminal일수도, non-terminal일수도 있음
• $\beta$: 아직 parser가 검사하지 않음. terminal만 있다. (아직 reduce 안했으니깐)
• | : splitter. 좌 우 substring을 구분한다. 좌에서 우로 이동하면서, 좌측 substring의 reduce 가능한 우측 끝부분을 reduce 하거나, 계속 진행한다.

e.g. input: id*id
CFG: $E\rarr T+E|T, T\rarr F*T|F, F\rarr (E)|id$

initial state: | id * id
action: shift, state: id| * id, stack:[id]
action: Reduce by F->id, state: F| * id, stack:[F]
action: shift, state: F * |id, stack:[F, *]
action: shift, state: F * id|, stack:[F, *, id]
action: Reduce by F->id, state: F * F|, stack:[F, *, F]
action: Reduce by T->F, state: F * T|, stack:[F, *, T]
action: Reduce by T->F*T, state: T|, stack:[T]
action: Reduce by E->T, state: E|, stack:[E]
ACCEPTED

Conflict

LR Parser에서는 2가지 충돌이 발생할 수 있다.

• Shift-reduce conflict
  현재 reduce 할 수 있을 때, 더 긴 문자열을 예상하고 Shift 해야하는가?
• Reduce-reduce conflict
  여러 production이 적용 가능할 때, 어떤 것을 사용해야하는가?