랄뚜기의 코딩일기

CLR parsing SLR 방법보다 강력하다는 장점 lookahead를 구하는 과정이 복잡하고 시간이 오래 걸리며 parse table이 크다는 단점 LALR(Look ahead LR) parsing LR(1)과 같이 reduce action에서는 lookahead를 이용 Parsing table의 크기를 되도록 작게 구성 Strengths SLR 방법보다 강력 parse table의 크기가 CLR 방법보다 작음 프로그래밍 언어의 구문 구조를 대부분 편리하게 표현할 수 있음 모호하지 않은 문맥자유 문법으로 표현된 거의 모든 언어를 인식 에러를 초기에 탐지 가능 Weaknesses parse table을 만들기 위해 lookahead 기호를 구하는 것이 어려움 LALR Parser Implementati..

CLR parser SLR parser는 reduce item [A->ɑ·]에 대해서, FOLLOW(A)에는 속하지만 nonterminal A 다음에 나오지는 않는 기호들이 존재할 때 파싱이 불가능해진다.이를 해결하기 위해 Lookahead와 LR(1)을 이용한 CLR parser를 사용해야 한다. Lookahead : 한 state에서 어떤 논터미널 기호 다음에 나올 수 있는 터미널 기호 LR(1) item : LR(0) item에 lookahead 정보를 첨가한 것 LR(1) item set의 Canonical collection C1 CLOSURE 함수와 GOTO 함수가 필요 GOTO 함수는 LR(0) item set의 canonical collection C0를 구할 때와 동일 CLOSURE 함수..

Bottom-up parsing Bottom-up paring(상향식 구문 분석): Input string을 읽어가면서 reduce에 의해 start symbol을 찾아가는 방법 Input string이 start symbol로 reduce되면 올바른 문장이라고 판단, 파스트리 출력 그렇지 않으면 문법에 맞지 않은 문자으로 판단, 에러 메시지를 출력한다. Bottom-up parsing(상향식 구문 분석)은 rightmost derivation(우단 유도)의 역순이다. reduce, handle: S⇒*ɑAw⇒ɑβw의 유도 과정이 존재할 때 reduce(감축) : sentential form ɑβw에서 β를 A로 대체하는 것 handle(핸들) : β. 즉 한 sentential form에서 reduce..

Recursive-descent parsing(재귀적 하강 구문 분석) Input string을 parsing하기 위해 recursive procedure를 사용한다. - Nonterminal symbols에 대한 프로시저 및 Terminal symbols에 대한 프로시저를 각각 작성한 다음 이를 통합함으로써 구현한다. - Terminal symbol에 대한 프로시저는 production rule에 있는 terminal symbol과 input symbol이 같은지 비교하여 같은 경우 다음 input symbol을 읽게 한다. - Nonterminal symbol에 대한 프로시저는 현재의 input symbol를 생성할 수 있는 적절한 생성 규칙이 선택되도록 작성한다. 먼저 현재의 입력 기호를 보고 시작..

FIRST 즉, Nonterminal A로부터 유도되어 첫 번째 나타나는 터미널 기호들의 집합이라고 할 수 있다. Nullable Nonterminal 𝜀으로 유도되지 않으므로 nullable하다. Ringsum and FIRST Ringsum에서 A에 𝜀이 포함이 되면 빠지는 개념은 매우 중요한 개념이므로 주의하자. FOLLOW FOLLOW(A)는 어떤 문장 형태에서 논터미널 기호 A다음에 나오는 터미널 기호들의 집합이다. Sentential form에서 nonterminal A 다음에 나오는 terminal symbols의 set. $는 입력 문자열의 끝을 나타내는 symbol. FOLLOW(A) 1. 만약 A가 시작 기호이면 $는 FOLLOW(A)에 속한다. 2. 만약 B->ɑAβ,β≠𝜀인 생성규칙..

Pushdown Automata finite automata와 다른 점은 stack symbol T와 ,start symbol of stack z0가 추가되었다는 점이다. 문제를 풀 때, δ(q0,주어진 값,z0)로 시작한다. 결과가 하나라면 deterministic push-down automata DPDA가 되고 하나 이상이라면 non-deterministic push-down automata NPDA가 된다. Extended Transition Fuction of PDA Syntax Analysis 스캐너에 의해 생성된 토큰을 입력으로 받아 주어진 문법에 맞는지를 검사하고, 문법에 맞으면 파스 트리를 출력하고 맞지 않으면 에러를 출력 Syntax analysis를 담당하는 도구를 syntax ana..

Grammar Conversion Ambiguous grammar를 unambiguous로 변환. 즉, Syntax analysis의 효율이 나쁜 문법을 효율이 좋은 문법으로 변환한다는 것이다. Conversion method - Elimination of useless production rules - Elimination of epsilon production rules - Elimination of single production rules - Elimination of left-recursion - Left-factoring Elimination of useless production rules Uesless production rule - useless symbol를 가지고 있는 producti..

Context-free Grammar Context-free Grammar는 Chomsky hierarchy에서 생성 규칙의 왼쪽은 논터미널 기호 하나로 이루어져있고 오른쪽 부분은 문자열인 것을 말한다. Parse Tree Leftmost derivation : 유도 과정의 각 단계에서 sentential form의 가장 왼쪽에 있는 nonterminal symbol를 replacement하는 경우 Rightmost derivation : 유도 과정의 각 단계에서 sentential form의 가장 오른쪽에 있는 nonterminal symbol를 계속해서 replacement하는 경우 Left parse : leftmost derivation에 의해서 사용된 생성 규칙 순서 Right parse : r..

Lexical Analysis 소스 프로그램을 token 단위로 분리하여 토큰 스트림을 출력한다. Token Token은 터미널 기호들로 구성된 문법적으로 의미 있는 최소 단위이다. Special form - language designer - 예약어(Reserved word) : for, if, int 등의 언어에 이미 정의된 단어 - 연산자(operator) : +,-,*,/, a|b|c|....|Y|Z digit (d) -> 0|1|2|...|9 Recognition of Reserved Words C에서 예약어를 만드는 방법은 identifier를 만드는 방법과 동일하다. identifier인지 먼저 검사하고 별도 표에 기록되어 있는 reserved word와 비교한다. 매칭되는 것이 있으면 해당..

NFA->DFA NFA->DFA (2) 𝜀-closure가 없는 경우 State Minimization Example ( State Minimization ) Regular Grammar -> Regular Expression 주어진 Grammar G에 의해 생성되는 Language L(G)가 무엇인지를 알기 위해서 Regular Grammar를 Regular Expression으로 변환 Regular grammar를 coefficient가 regular expression으로 구성된 방정식인 regular expression equation으로 바꾸고 solution을 구함 Regular Expression -> Finite Automata