JJING_LOG

Language Processor - 처리할 수 있는 프로그램 (translated or interpreted) - 두 가지 종류의 언어 프로세서 : Translator, Interpereter - translator는 한 언어로 표현된 텍스트를 받아들이고, 다른 언어로 표현된 semantically-equivalent 텍스트를 생성하는 프로그램 assembler는 assembly 언어에서 기계 언어로 translate 한다. 컴파일러는 high-level의 언어를 low-level의 언어로 번역한다. High-level Language -> Compiler(Program) -> object code 컴파일러는 구현 언어로 작성된다. - Interpreter는 소스 프로그램을 받아들이고, 소스프로그램을 ..

Semantic analyzer (의미분석) - 프로그램의 semantics은 "meaning" 이다. - 구문적으론 올바르지만 의미상 틀린 것 - 일치하지 않는 Type, 선언되지 않은 변수 사용, 잘못된 인수로 호출된 함수, access 위반 등 확인 - syntax tree에 주석 달기 -> type 정보(attribute) 포함 - tree의 할당이 적절한지 확인 ex) integer가 맞는가? - 프로그램의 syntactic 구조를 알면, 컴파일에 필요한 추가 정보를 계산한다. - 언어의 의미를 지정하기 위해 사용되는 표준 방법은 없다. -> 알고리즘은 parsing 알고리즘만큼 명확하게 표현되지 않는다. Attribute and binding - Attribute 프로그래밍 언어 구조의 모든 ..

SLR(1) Parsing = Simple LR(1) Parsing 1 -> Lookahead를 한다! - LR(0) item으로 만들어진 DFA를 그대로 사용한다. input string의 다음 token을 사용해 action을 수행하여, LR(0) parsing의 power를 높인다. DFA를 구성할 때 LR(0) || SLR(1)은 lookahead를 무시한다. -> SLR(1)은 lookahead를 하지만 만들 때 현재 parsing state의 DFA들은 LR(0) item을 그대로 쓰기 때문에 simple 일반 LR(1)은 DFA를 구성할 때 lookahead를 사용한다. - Two ways 적절한 DFA 전환이 존재하는지 확인하기 위해 transition 전에 input token을 참조한다..

Yacc (Yet Another Compiler-Compiler) parser(syntax analyzer) generator하는 프로그램 Input : BNF, Context-free grammar를 BNF로 변환 가능 Output : Parser LALR(1) Parser Compiler-Compiler (Compiler generator) compiler를 generator하는 프로그램 Input : grammar (BNF) Output : parser의 source code An (basic) overview of Yacc General format of Yacc source {declarations} (선언) // optional %% {rules} (변환 규칙) %% {programs} (사용..

Bottom-up parsing (상향식 구문 분석) 연산을 반전시켜, 문자열을 Start symbol로 Reduce 한다. Rightmost derivation Two actions in bottom-up parser Shift (이동) Input 처음 문자열을 parsing stack으로 이동 Reduce (감축) a가 있을 때, P : A -> a에 매칭되어 a -> A로 reduce 한다. Bottom-up parser example G = ({S, S'}, {(, )}, P, S') P : S' -> S S -> ( S ) S | ε Parsing stack Input Action 1 $ ( ) $ shift 2 $ ( ) $ reduce S -> ε 3 $ ( S ) $ shift 4 $ ( ..

Top-down parsing (하향식 구문 분석) input string이 있으면, leftmost derivation을 통해 parse tree를 그린다. Recursive descent parsing Predictive parsers 하나 이상의 lookahead tokens을 사용해 input string의 다음 구성을 예측한다. LL(1), LL(k) 잘 안쓰인다. 보통 bottom-up parser를 사용하지만 이를 알기 위해선 top-down을 알아야 한다. Recursive descent parsing top-level의 non-terminal에서 시작한다. start symbol에 대한 rule을 순서대로 시도 각 단계에서, 사용할 다양한 production 선택 잘못된 선택 시 back..

Pushdown automata (PDA) context-free language (CFL)은 Pushdown automata가 허용하는 language이다. Roughly speaking : PDA == [ε-NFA + "a stack"] - FSM 과 pushdown Schematic Finite state machine Pushdown automata Stack이 왜 필요할까? L = {(0^n)(1^n) | n >= 1}이 있다고 가정, CFL language이다. 이 때 몇 번까지 읽었는지 counting을 해주는 것이 stack의 역할이다. Regular Language는 몇 번까지 읽었는지 counting을 할 수 없다. Pushdown automata (PDA) PDA는 7-tuple P ..

Why normal forms? 만약 모든 grammar의 productions이 같은 형식으로 표현된다면 grammar를 사용하는 알고리즘 디자인 용이 증명 및 특성 표시 용이 대표적인 NF 2개 Chomsky Normal Form (CNF) (춈스키 정규 형태) Greibach Normal Form (그레이바하 정규 형태) Chomsky normal form (CNF) context-free grammar G는 production이 아래와 같이 표현되는 경우 Chomsky normal form이다. A -> BC // 2개의 non-terminal로 이루어진 경우 A -> a // 하나의 terminal로 이루어진 경우 S -> ε // start symbol이 ε로 가는 경우 A, B, C ∈ VN..

Context Free Grammar (CFG) context free grammar G = (VN, VT, P, S)로 구성되어있다. V_N : non-terminal symbol의 유한개 집합 V_T : terminal symbol의 유한개 집합 VN ∩ VT = ø VN ∪ VT = V P : productions 유한 집합 a -> v, a ∈ V+, b ∈ V* a ∈ VN, b ∈ V* S : start symbol Context free language (CFL) grammar로부터 생성된 Language context free grammar G=(VN, VT, P, S)가 주어졌을 때, G에 의해 생성된 언어는 집합이다. L(G) = {w | w ∈ VT* and S =*> w} => S에..

Lex Lexical Analyzer(Scanner) Generator 스캐너 프로그램을 만드는 프로그램이다. 문장 입력 stream의 lexical processing을 위해 설계된 프로그램 생성기 Input 문자열 정규표현식에 대한 High-level specification 정규식과 관련된 프로그램 조각 Output 범용 언어로 된 프로그램 입력 스트림의 식을 인식한다. 입력 스트림을 이 식과 일치하는 문자열로 분할한다. 엄밀히 C 코드가 생성된다. An overview of Lex Source에 C 코드 추가 가능 Lex lexical analysis 단계를 수행하기 위해 parser 생성기와 함께 사용한다. Scanner : Lex가 만든다. Parser : yacc이 만든다. lexical l..