mojo's Blog

Semantic Analysis: ● Syntax tree와 symbol table을 이용하여 소스 프로그램이 언어 정의에 의미적으로 (semantically) 일치하는지 검사 ● identifier가 프로그램 내의 수식과 문장에서 해당 언어의 type 규칙에 따라 올바르게 사용되고 있는지를 검사하는 data type checking 수행, 그 결과를 syntax tree 혹은 symbol table에 저장 의미 분석기(semantic analyzer)가 수행 ● 입력: ○ parsing으로 얻은 parse tree 또는 syntax tree ● 출력: ○ Semantic analysis가 이뤄진 parse tree 또는 syntax tree ○ Syntax directed translation을 이용하..

LALR Parser Implementation 1. 파싱표를 구성하기가 쉽지만 파싱표의 크기가 커지는 LR(1)을 가지고 구성 ● 같은 코어를 가진 LR(1) item을 묶어서 하나의 state로 구성 2. 효율적으로 파싱표를 구성할 수 있는 LR(0)과 lookahead를 가지고 구성 ● LR(1) item의 lookahead를 합한 것으로 구성 Example : LALR parse table을 구해보도록 하자. P: S -> CC C -> cC C -> d I3, I6는 같은 코어이므로 lookahead 를 합친다. I36 = {[S → c•C, c/d/$], [C → •cC, c/d/$], [C → •c, c/d/$]} I4, I7는 같은 코어이므로 lookahead 를 합친다. I47 = {[C..

Canonical Collection of LR(1) item sets [알고리즘] Canonical Collection of LR(1) item sets 입력 : Augmented Grammar G' 출력 : Canonical Collection of LR(1) item sets function CLOSURE(I); begin repeat for each item [A → α•Bβ, a]∈I, each production rule B → 𝛄 ∈ G’ first(βa)에 포함되는 each terminal b에 대해서 do I = I U {[B → •𝛄, b]} end for until 더 이상 I에 새로운 item이 추가되지 않을 때 end function GOTO(I, X); begin [A → α•X..

Example ) 다음 문법에 대한 SLR parsing table을 만들어보자. P: ① S → L = R ② S → R ③ L → ＊R ④ L → id ⑤ R → L 1. Augmented grammar 를 만든다. S' -> S 를 추가해주면 끝이다. P: S' -> S ① S → L = R ② S → R ③ L → ＊R ④ L → id ⑤ R → L 2. Canonical collection 을 계산한다. I0 = CLOSURE([S' -> •S]) = {[S' -> •S], [S -> •L = R], [S -> •R], [L -> •*R], [L ->•id], [R -> •L]} GOTO(I0, S) = CLOSURE([S' -> S•]) = {[S' -> S•]} = I1 GOTO(I0, L)..

Canonical collection LR(0) item set의 canonical collection C0 - C0 = {CLOSURE ({[S′ →•S])} ∪ {GOTO (I, X) | I ∈ C0, X ∈ V} Example: LR(0) item set의 canonical collection을 구해보자. P: ① E → E ＋ T ② E → T ③ T → T ＊ F ④ T → F ⑤ F → (E) ⑥ F → id (1) Augmented grammar 를 추가한다. S' -> E (2) CLOSURE 를 구한다. I0 = CLOSURE([S' -> •E]) = {[S' -> •E], [E -> •E + T], [E -> •T], [T -> •T * F], [T -> •F], [F -> •(E)],..

Bottom-up Parsing Bottom-up parsing: - Input string을 읽어가면서 reduce에 의해 start symbol을 찾아가는 방법 - Input string이 start symbol로 reduce되면 올바른 문장이라고 판단, 파스 트리 출력 - 그렇지 않으면 문법에 맞지 않은 문장으로 판단, 에러 메시지를 출력한다. reduce, handle: S ⇒* αAw ⇒ αβw의 유도 과정이 존재할 때 - reduce: sentential form αβw에서 β를 A로 대체하는 것 - handle: β. 즉 한 sentential form에서 reduce되는 부분. ex ) rightmost derivation 과정을 보이고 parse tree를 그리고 handle 을 찾기 S..