5 Context-Free Grammar
무엇을공부하나? 앞에서배운 " 정규식 " 은언어의 " 어휘 (lexeme)" 를표현하는도구로사용되었다. 언어의 " 구문 (syntax)" 은 " 정규언어 " 의범위를벗어나기때문에 " 정규식 " 으로표현이불가능하다. 본장에서배우는 " 문맥자유문법 " 은언어의 " 구문 (syntax)" 을표현할수있는도구이다. 어떤 " 문맥자유문법 " G가있으면 G가표현하는언어인 L(G) 가존재한다. 본장에서는주어진프로그래밍언어의구문을 " 문맥자유문법 " 으로표현하는방법을배운다. 5 Context-Free Grammar 5-2
강의내용 문맥자유문법 (Context-Free Grammar) 유도 (Derivation) 문맥자유문법에의하여정의되는언어 파스트리 (Parse Tree) 모호한문법 (Ambiguous Grammar) 추상구문트리 (Abstract Syntax Tree) C-Minus 문맥자유문법 교재 Kenneth C. Louden, Compiler Construction Principles and Practice, PWS Publishing Company, 1997. (3.1, 3.2, 3.3, 3.4, A.2) John E. Hopcroft, Rajeev Motwani and Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation, 3rd Edition, Addison Wesley, 2006. (5.1, 5.2, 5.4) 5 Context-Free Grammar 5-3
문맥자유문법 (Context-Free Grammar) 문맥자유문법은 G는아래와같이 4개의요소 (N,, P, S) 로구성된다. 1 N은 non-terminal 심볼의유한집합, 2 는 terminal 심볼의유한집합, 3 P는생산규칙 (production rule) N->( N)* 의유한집합, 그리고 4 S N는시작 (starting) 심볼. 5 Context-Free Grammar 5-4
문맥자유문법쓰기 G exp =(N,, P, S) N={exp, op} ={+, -, *, (, ), number} P={ exp -> exp op exp exp -> ( exp ) exp -> number op -> + op -> - op -> * } S=exp 문맥자유문법을쓸때보통 production rule P 만쓰고 P의첫 rule의좌측 nonterminal 심볼을시작심볼 S라고가정한다. 5 Context-Free Grammar 5-5
유도 (Derivation) Direct derivation => 만약 A->v P 이고 u=xay 이며 v=xvy 이면 u => v 를 direct derivation 이라고한다. exp => ( exp ) ( exp ) => ( exp op exp ) ( exp op exp ) => ( exp + exp ) ( exp + exp ) => ( number + exp ) ( number + exp ) => ( number + number ) Derivation =>* Derivation =>* 은 direct derivation 이 0 회이상일어난것을의미한다. exp =>* ( number + number ) 5 Context-Free Grammar 5-6
Leftmost/Rightmost Derivation Derivation 을할때항상가장왼쪽 nonterminal 심볼을선택하면 leftmost derivation 이라고하고항상가장오른쪽 nonterminal 심볼을선택하면 rightmost derivation 이라고한다. Leftmost derivation exp => exp op exp => number op exp => number + exp => number + number Rightmost derivation exp => exp op exp => exp op number => exp + number => number + number 5 Context-Free Grammar 5-7
문맥자유문법에의하여정의되는언어 어떤문맥자유문법 G=(N,, P, S) 가있을때언어 { w * S =>* w } 을문맥자유문법 G 에의하여정의되는언어 L(G) 라고한다. number L(G) ( number + number ) L(G) number * number + number L(G) (number - number) * number L(G)... 5 Context-Free Grammar 5-8
파스트리 (Parse Tree) 어떤문맥자유문법 G=(N,, P, S) 가있을때파스트리 (parse tree) 혹은구문트리 (syntax tree) 는다음조건을만족하는 " 라벨을가지는 ordered 트리 " 이다. 각노드는라벨 L N 를가진다. 루트노드의라벨은 S 이다. 만약한노드가내부 (internal) 노드이며라벨 A 를가지면 A N 이다. 만약한노드가잎 (leaf) 노드이며라벨 v 를가지면 v 이다. 만약한내부노드가라벨 A 를가지며 A->x 1... x n P 이면이노드의자식노드는각각라벨 x 1,..., x n 을가진다. 5 Context-Free Grammar 5-9
파스트리 스트링 "number + number" 에대한파스트리 5 Context-Free Grammar 5-10
파스트리와 Derivation 하나의파스트리는같은스트링을만드는다른여러개의다른 derivation 을표현할수있다. ( 내부노드에숫자 ) exp => exp op exp => number op exp => number + exp => number + number exp => exp op exp => exp op number => exp + number => number + number 5 Context-Free Grammar 5-11
파스트리 스트링 "( number - number ) * number" 에대한파스트리 5 Context-Free Grammar 5-12
모호한문법 (Ambiguous Grammar) 어떤문맥자유문법 G 가있을때스트링 w L(G) 에대하여서로다른 2 개이상의파스트리가존재하면이문법을 " 모호한문법 " 이라고한다. 아래문법은스트링 "number - number * number" 에대하여오른쪽그림과같이 2 개의서로다른파스트리를가지므로모호한문법이다. exp -> exp op exp exp -> ( exp ) exp -> number op -> + - * 5 Context-Free Grammar 5-13
추상구문트리 (Abstract Syntax Tree) 파스트리는컴파일러가코드를생성하는데꼭필요한정보이외의불필요한정보도포함하고있다. 추상구문트리 (abstract syntax tree) 는컴파일러가꼭필요로하는정보만을가진트리이다. ( 컴파일러설계자가고안함 ) number number 파스트리 추상구문트리 5 Context-Free Grammar 5-14
C-Minus 문맥자유문법 - 1/4 1. program -> var_declaration_list fun_declaration_list 2. var_declaration_list -> var_declaration_list var_declaration empty 3. fun_declaration_list -> fun_declaration_list fun_declaration fun_declaration 4. var_declaration -> type_specifier var SEMICOLON type_specifier var LBRACKET num RBRACKET SEMICOLON 5. type_specifier -> INT VOID 6. var -> ID 7. num -> NUM 8. fun_declaration -> type_specifier var LPAR params RPAR LBRACE local_declarations statement_list RBRACE 9. params -> param_list VOID 10. param_list -> param_list COMMA param param 5 Context-Free Grammar 5-15
C-Minus 문맥자유문법 - 2/4 11. param -> type_specifier var type_specifier var LBRACKET RBRACKET 12. local_declarations -> local_declarations var_declaration empty 13. statement_list -> statement_list statement empty 14. statement -> compound_stmt expression_stmt selection_stmt iteration_stmt funcall_stmt return_stmt input_stmt output_stmt 15. compound_stmt -> LBRACE statement_list RBRACE 16. expression_stmt -> expression SEMICOLON SEMICOLON 17. expression -> var ASSIGN expression var LBRACKET expression RBRACKET ASSIGN expression simple_expression 18. simple_expression -> additive_expression relop additive_expression additive_expression 5 Context-Free Grammar 5-16
C-Minus 문맥자유문법 - 3/4 19. relop -> LT LE GT GE EQ NE 20. additive_expression -> additive_expression addop term term 21. addop -> PLUS MINUS 22. term -> term mulop factor factor 23. mulop -> MULTIPLY DIVIDE 24. factor -> LPAR expression RPAR var var LBRACKET expression RBRACKET num PLUS num MINUS num 25. selection_stmt -> IF LPAR expression RPAR statement ELSE statement 26. iteration_stmt -> WHILE LPAR expression RPAR statement 27. funcall_stmt -> var ASSIGN call var LBRACKET expression RBRACKET ASSIGN call call 5 Context-Free Grammar 5-17
C-Minus 문맥자유문법 - 4/4 28. call -> var LPAR args RPAR 29. args -> arg_list empty 30. arg_list -> arg_list COMMA expression expression 31. return_stmt -> RETURN SEMICOLON RETURN expression SEMICOLON 32. input_stmt -> INPUT var SEMICOLON INPUT var LBRACKET expression RBRACKET SEMICOLON 33. output_stmt -> OUTPUT expression SEMICOLON 34. empty -> 5 Context-Free Grammar 5-18