ANSI C Yacc Grammar
- ANSI C언어의 Yacc(BNF) 표기
ANSI C Yacc grammar (URL)
%token IDENTIFIER CONSTANT STRING_LITERAL SIZEOF
%token PTR_OP INC_OP DEC_OP LEFT_OP RIGHT_OP LE_OP GE_OP EQ_OP NE_OP
%token AND_OP OR_OP MUL_ASSIGN DIV_ASSIGN MOD_ASSIGN ADD_ASSIGN
%token SUB_ASSIGN LEFT_ASSIGN RIGHT_ASSIGN AND_ASSIGN
%token XOR_ASSIGN OR_ASSIGN TYPE_NAME
%token TYPEDEF EXTERN STATIC AUTO REGISTER
%token CHAR SHORT INT LONG SIGNED UNSIGNED FLOAT DOUBLE CONST VOLATILE VOID
%token STRUCT UNION ENUM ELLIPSIS
%token CASE DEFAULT IF ELSE SWITCH WHILE DO FOR GOTO CONTINUE BREAK RETURN
// Lexical Analyzer에 미리 정의되어 있는 Token들을 명시해놓은 코드이다.
%start translation_unit
%%
// Translation_unit 라는 이름을 가진 Non-Terminal에서 이 문법이 시작(start)됨을 알린다.
// 본 Post의 상단에 가까울수록 Leaf에 가까운 문법이다. (우선순위가 높다.)
// 즉, 내려갈수록 파스 트리의 Root에 가까워져 우선 순위가 낮아진다.
primary_expression
: IDENTIFIER
| CONSTANT
| STRING_LITERAL
| '(' expression ')'
;
// IDENTIFIER, CONSTANT, STRING_LITERAL, '(' expression ')' 중 하나가 primary_expression으로 Reduce된다.
// 즉, primary_expression은 식별자, 상수, 문자열 상수, 소괄호 수식 중 하나로 정의된다.
postfix_expression
: primary_expression
| postfix_expression '[' expression ']'
| postfix_expression '(' ')'
| postfix_expression '(' argument_expression_list ')'
| postfix_expression '.' IDENTIFIER
| postfix_expression PTR_OP IDENTIFIER
| postfix_expression INC_OP
| postfix_expression DEC_OP
;
// PTR_OP(->), INC_OP(++), DEC_OP(--)
// postfix_expression은 Left-Recursion로써 정의되었다.
// 즉, [], (), (argument_expression_list) .IDENTIFIER, ->IDENTIFIER, ++, --가 연속된 Statement는
// Lexical Analyzer가 왼쪽부터 처리해 나간다.
argument_expression_list
: assignment_expression
| argument_expression_list ',' assignment_expression
;
unary_expression
: postfix_expression
| INC_OP unary_expression
| DEC_OP unary_expression
| unary_operator cast_expression
| SIZEOF unary_expression
| SIZEOF '(' type_name ')'
;
// unary_expression은 단항 연산을 지원하는 문법이다.
// \(\texttt{k++}\)와 \(\texttt{++k}\)
// \(\texttt{k++}\) : Post-increment이다. postfix_expression -> primary_expression -> ... -> Leaf
// \(\texttt{++k}\) : Pre-incerment이다. unary_expression -> postfix_expression -> primary_expression -> ... -> Leaf
// 즉, 후위 연산자 토큰이 전위 연산자 토큰보다 Leaf에 더 가까우므로 연산자 우선 순위에 우위에 있다.
// 즉, Lexical Analyzer는 \(\texttt{k++}\)를 \(\texttt{++k}\)보다 먼저 처리한다.
unary_operator
: '&'
| '*'
| '+'
| '-'
| '~'
| '!'
;
cast_expression
: unary_expression
| '(' type_name ')' cast_expression
;
multiplicative_expression
: cast_expression
| multiplicative_expression '*' cast_expression
| multiplicative_expression '/' cast_expression
| multiplicative_expression '%' cast_expression
;
// multiplicative_expression에서는 * 토큰, / 토큰, % 토큰은 문법적으로 동일한 우선 순위를 갖도록 정의한다.
// *, /, % 토큰은 Left-Recursion으로써 정의되어, 서로 Left-Associativity를 만족한다.
// 즉, *, /, % 토큰들로 구성된 Statement는 Lexical Analyzer가 왼쪽(Left)부터 해석한다.
additive_expression
: multiplicative_expression
| additive_expression '+' multiplicative_expression
| additive_expression '-' multiplicative_expression
;
// additive_expression에서는 + 토큰, - 토큰은 문법적으로 동일한 우선 순위를 갖도록 정의한다.
// additive_expression은 multiplicative_express보다 Root에 가까워 문법적 우선 순위가 낮다.
// 즉, +, - 토큰은 *, /, % 토큰보다 우선 순위가 낮다.
// +, - 토큰은 Left-Recursion으로써 정의되어, 서로 Left-Associativity를 만족한다.
// 즉, +, - 토큰들로 구성된 Statement는 Lexical Analyzer가 왼쪽(Left)부터 해석한다.
shift_expression
: additive_expression
| shift_expression LEFT_OP additive_expression
| shift_expression RIGHT_OP additive_expression
;
relational_expression
: shift_expression
| relational_expression '<' shift_expression
| relational_expression '>' shift_expression
| relational_expression LE_OP shift_expression
| relational_expression GE_OP shift_expression
;
equality_expression
: relational_expression
| equality_expression EQ_OP relational_expression
| equality_expression NE_OP relational_expression
;
// equality_expression에서는 EQ_OP(==) 토큰과 NE_OP(!=) 토큰은 문법적으로 동일한 우선 순위를 갖도록 정의한다.
// ==토큰과 !=토큰은 Left-Recursion으로써 정의되어, 서로 Left-Associativity를 만족한다.
// 즉 ==, !=토큰들로 구성된 Statement는 Lexical Analyzer가 왼쪽(Left)부터 해석한다.
and_expression
: equality_expression
| and_expression '&' equality_expression
;
exclusive_or_expression
: and_expression
| exclusive_or_expression '^' and_expression
;
// exclusive_or_expression는 Left-Recursion으로써 정의되었다.
// 재귀적 반복이 종결되면 and_expression으로 Reduce된다.
// 즉, ^토큰은 &토큰보다 우선 순위가 낮다.
inclusive_or_expression
: exclusive_or_expression
| inclusive_or_expression '|' exclusive_or_expression
;
// inclusive OR은 일반적인 OR 연산을 의미한다.
// 우선 순위 : &(and) > ^(exclusive_or) > |(inclusive_or)
logical_and_expression
: inclusive_or_expression
| logical_and_expression AND_OP inclusive_or_expression
;
// AND_OP(&&)
logical_or_expression
: logical_and_expression
| logical_or_expression OR_OP logical_and_expression
;
// OR_OP(||)
conditional_expression
: logical_or_expression
| logical_or_expression '?' expression ':' conditional_expression
;
// conditional_expression은 삼항 연산 문법을 제공한다.
// Right_Recursion으로써 문법을 정의한다.
// 즉, 삼항 연산이 중첩되어있는 Statement는 Lexical Analyzer가 오른쪽(Right)부터 해석한다.
assignment_expression
: conditional_expression
| unary_expression assignment_operator assignment_expression
;
// assignment_expression은 대입(배정) 연산 문법을 제공한다.
// Right-Recursion으로써 문법을 정의한다.
// 즉, 대입 연산이 중첩되어있는 Statement는 Lexical Analyzer가 오른쪽(Right)부터 해석한다.
assignment_operator
: '='
| MUL_ASSIGN
| DIV_ASSIGN
| MOD_ASSIGN
| ADD_ASSIGN
| SUB_ASSIGN
| LEFT_ASSIGN
| RIGHT_ASSIGN
| AND_ASSIGN
| XOR_ASSIGN
| OR_ASSIGN
;
expression
: assignment_expression
| expression ',' assignment_expression
;
// Left-Recursion으로써 문법을 정의한다.
// expression은 다수의 수식이 Comma로 구분되어 반복되면, Lexical Analyzer는 가장 왼쪽(Left)부터 해석한다.
constant_expression
: conditional_expression
;
// 삼항 연산을 처리하는 conditional_expression은 곧바로 constant_expression으로 Reduce된다.
declaration
: declaration_specifiers ';'
| declaration_specifiers init_declarator_list ';'
;
declaration_specifiers
: storage_class_specifier
| storage_class_specifier declaration_specifiers
| type_specifier
| type_specifier declaration_specifiers
| type_qualifier
| type_qualifier declaration_specifiers
;
// declaration_specifiers는 크게 storage_class_specifier, type_specifier, type_qualifier로 구분된다.
// storage_class_specifier, type_specifier, type_qualifier는 모두 Right_Recursion으로써 정의된다.
// 즉, 이에 해당되는 지정자들이 연속될 경우, Lexical Analyzer는 오른쪽(Right)부터 해석한다.
// \(\texttt{static struct int}\)의 경우, \(\texttt{int} \to \texttt{struct} \to \texttt{static}\) 순서로 해석된다.
init_declarator_list
: init_declarator
| init_declarator_list ',' init_declarator
;
// init_declarator_list는 Left-Recursion으로써 정의되었다.
// 즉, Comma로 구분되어 반복될 경우, Lexical Analyzer는 왼쪽(Left)부터 해석한다.
init_declarator
: declarator
| declarator '=' initializer
;
// init_declarator는 변수의 선언, 변수의 선언 및 초기화에 관한 문법을 제공한다.
storage_class_specifier
: TYPEDEF
| EXTERN
| STATIC
| AUTO
| REGISTER
;
type_specifier
: VOID
| CHAR
| SHORT
| INT
| LONG
| FLOAT
| DOUBLE
| SIGNED
| UNSIGNED
| struct_or_union_specifier
| enum_specifier
| TYPE_NAME
;
struct_or_union_specifier
: struct_or_union IDENTIFIER '{' struct_declaration_list '}'
| struct_or_union '{' struct_declaration_list '}'
| struct_or_union IDENTIFIER
;
struct_or_union
: STRUCT
| UNION
;
struct_declaration_list
: struct_declaration
| struct_declaration_list struct_declaration
;
struct_declaration
: specifier_qualifier_list struct_declarator_list ';'
;
specifier_qualifier_list
: type_specifier specifier_qualifier_list
| type_specifier
| type_qualifier specifier_qualifier_list
| type_qualifier
;
// specifier_qualifier_list는 Right_recursion으로써 정의되었다.
// 즉, type_specifier, type_qualifier이 연속될 경우, Lexical Analyzer는 오른쪽(Right)부터 해석한다.
struct_declarator_list
: struct_declarator
| struct_declarator_list ',' struct_declarator
;
struct_declarator
: declarator
| ':' constant_expression
| declarator ':' constant_expression
;
enum_specifier
: ENUM '{' enumerator_list '}'
| ENUM IDENTIFIER '{' enumerator_list '}'
| ENUM IDENTIFIER
;
enumerator_list
: enumerator
| enumerator_list ',' enumerator
;
enumerator
: IDENTIFIER
| IDENTIFIER '=' constant_expression
;
type_qualifier
: CONST
| VOLATILE
;
declarator
: pointer direct_declarator
| direct_declarator
;
direct_declarator
: IDENTIFIER
| '(' declarator ')'
| direct_declarator '[' constant_expression ']'
| direct_declarator '[' ']'
| direct_declarator '(' parameter_type_list ')'
| direct_declarator '(' identifier_list ')'
| direct_declarator '(' ')'
;
pointer
: '*'
| '*' type_qualifier_list
| '*' pointer
| '*' type_qualifier_list pointer
;
// pointer는 Right-Recursion으로 정의됨으로써, Asterisk(*)가 연속되는 것을 허용하는 문법을 제공한다.
type_qualifier_list
: type_qualifier
| type_qualifier_list type_qualifier
;
parameter_type_list
: parameter_list
| parameter_list ',' ELLIPSIS
;
// ELLIPSIS : ... (3개의 Dot들이 연속된 형태이다. Multiple Argument에 대응하기 위한(매개변수의 개수가 미정일 때 사용하는) 연산자이다.)
parameter_list
: parameter_declaration
| parameter_list ',' parameter_declaration
;
parameter_declaration
: declaration_specifiers declarator
| declaration_specifiers abstract_declarator
| declaration_specifiers
;
identifier_list
: IDENTIFIER
| identifier_list ',' IDENTIFIER
;
type_name
: specifier_qualifier_list
| specifier_qualifier_list abstract_declarator
;
abstract_declarator
: pointer
| direct_abstract_declarator
| pointer direct_abstract_declarator
;
direct_abstract_declarator
: '(' abstract_declarator ')'
| '[' ']'
| '[' constant_expression ']'
| direct_abstract_declarator '[' ']'
| direct_abstract_declarator '[' constant_expression ']'
| '(' ')'
| '(' parameter_type_list ')'
| direct_abstract_declarator '(' ')'
| direct_abstract_declarator '(' parameter_type_list ')'
;
// direct_declarator와 유사하나, direct_declarator는 IDENTIFIER로 곧바로 Reduce될 수 있는 반면,
// direct_abstract_declarator는 그럴 수 없다.
// 위 문법에 의하여 ( )[ ]( )[80]과 같은 문법이 허용된다.
// 즉, 무언가를 선언할 때, identifier는 필요하지 않고, type만 필요한 경우 사용하는 문법이다.
// type_name 문법, parameter_declaration 문법 사용시 필요한 문법이다.
initializer
: assignment_expression
| '{' initializer_list '}'
| '{' initializer_list ',' '}'
;
// init_declarator의 일부로써, initializer가 사용된다.
// \(\texttt{{ i = 4, j = 8, }}\) 문장의 경우 첫 번째 Comma는 initializer에 해당되는 Comma이며,
// 두 번째 Comma는 initializer_list의 Comma이다.
initializer_list
: initializer
| initializer_list ',' initializer
;
statement
: labeled_statement
| compound_statement
| expression_statement
| selection_statement
| iteration_statement
| jump_statement
;
labeled_statement
: IDENTIFIER ':' statement
| CASE constant_expression ':' statement
| DEFAULT ':' statement
;
// IDENTIFIER는 레이블 이름로 해석된다.
// \(\texttt{switch}\)문에서 주로 사용하는 jump문에 대한 문법이다.
compound_statement
: '{' '}'
| '{' statement_list '}'
| '{' declaration_list '}'
| '{' declaration_list statement_list '}'
;
// C언어에서는 선언이 나온 후, 문장이 나온다.
declaration_list
: declaration
| declaration_list declaration
;
statement_list
: statement
| statement_list statement
;
expression_statement
: ';'
| expression ';'
;
// expression_statement는 세미 콜론만 단독으로 있어도 Statement로 간주하는 문법을 제공한다.
// 즉, 단독으로 위치한 세미콜론도 expression_statement로 Ruduce되는 하나의 문장이다.
selection_statement
: IF '(' expression ')' statement
| IF '(' expression ')' statement ELSE statement
| SWITCH '(' expression ')' statement
;
// selection_statement는 \(\texttt{if}\)와 \(\texttt{switch}\)문에 소괄호가 없는 것을 허용하지 않는 문법을 제공한다.
iteration_statement
: WHILE '(' expression ')' statement
| DO statement WHILE '(' expression ')' ';'
| FOR '(' expression_statement expression_statement ')' statement
| FOR '(' expression_statement expression_statement expression ')' statement
;
jump_statement
: GOTO IDENTIFIER ';'
| CONTINUE ';'
| BREAK ';'
| RETURN ';'
| RETURN expression ';'
;
// jump : 프로그램의 Flow를 바꾼다.
// \(\texttt{return (1);}\) 에서 (1)이 통채로 expression으로 Reduce된다.
translation_unit
: external_declaration
| translation_unit external_declaration
;
// external_declaration이 한 번 이상 Recursive하게 반복되는 구조이다.
// translation_unit은 Left-Recursion으로써 구현되었다.
external_declaration
: function_definition
| declaration
;
// external_declaration은 함수 정의, 외부 변수 선언 문법을 제공한다.
// 즉, 외부에 선언될 수 있는 것은 함수, 변수로 제한한다.
function_definition
: declaration_specifiers declarator declaration_list compound_statement
| declaration_specifiers declarator compound_statement
| declarator declaration_list compound_statement
| declarator compound_statement
;
// 본 Post의 하단에 가까울수록 Root에 가까운 문법이다. (우선순위가 낮다.)
// 즉, 올라갈수록 파스 트리의 Leaf에 가까워져 우선 순위가 높아진다.
%%
#include
extern char yytext[];
extern int column;
yyerror(s)
char *s;
{
fflush(stdout);
printf("\n%*s\n%*s\n", column, "^", column, s);
}
ANSI C Yacc Grammar
- ANSI C언어의 Yacc(BNF) 표기
ANSI C Yacc grammar (URL)
%token IDENTIFIER CONSTANT STRING_LITERAL SIZEOF
%token PTR_OP INC_OP DEC_OP LEFT_OP RIGHT_OP LE_OP GE_OP EQ_OP NE_OP
%token AND_OP OR_OP MUL_ASSIGN DIV_ASSIGN MOD_ASSIGN ADD_ASSIGN
%token SUB_ASSIGN LEFT_ASSIGN RIGHT_ASSIGN AND_ASSIGN
%token XOR_ASSIGN OR_ASSIGN TYPE_NAME
%token TYPEDEF EXTERN STATIC AUTO REGISTER
%token CHAR SHORT INT LONG SIGNED UNSIGNED FLOAT DOUBLE CONST VOLATILE VOID
%token STRUCT UNION ENUM ELLIPSIS
%token CASE DEFAULT IF ELSE SWITCH WHILE DO FOR GOTO CONTINUE BREAK RETURN
// Lexical Analyzer에 미리 정의되어 있는 Token들을 명시해놓은 코드이다.
%start translation_unit
%%
// Translation_unit 라는 이름을 가진 Non-Terminal에서 이 문법이 시작(start)됨을 알린다.
// 본 Post의 상단에 가까울수록 Leaf에 가까운 문법이다. (우선순위가 높다.)
// 즉, 내려갈수록 파스 트리의 Root에 가까워져 우선 순위가 낮아진다.
primary_expression
: IDENTIFIER
| CONSTANT
| STRING_LITERAL
| '(' expression ')'
;
// IDENTIFIER, CONSTANT, STRING_LITERAL, '(' expression ')' 중 하나가 primary_expression으로 Reduce된다.
// 즉, primary_expression은 식별자, 상수, 문자열 상수, 소괄호 수식 중 하나로 정의된다.
postfix_expression
: primary_expression
| postfix_expression '[' expression ']'
| postfix_expression '(' ')'
| postfix_expression '(' argument_expression_list ')'
| postfix_expression '.' IDENTIFIER
| postfix_expression PTR_OP IDENTIFIER
| postfix_expression INC_OP
| postfix_expression DEC_OP
;
// PTR_OP(->), INC_OP(++), DEC_OP(--)
// postfix_expression은 Left-Recursion로써 정의되었다.
// 즉, [], (), (argument_expression_list) .IDENTIFIER, ->IDENTIFIER, ++, --가 연속된 Statement는
// Lexical Analyzer가 왼쪽부터 처리해 나간다.
argument_expression_list
: assignment_expression
| argument_expression_list ',' assignment_expression
;
unary_expression
: postfix_expression
| INC_OP unary_expression
| DEC_OP unary_expression
| unary_operator cast_expression
| SIZEOF unary_expression
| SIZEOF '(' type_name ')'
;
// unary_expression은 단항 연산을 지원하는 문법이다.
// \(\texttt{k++}\)와 \(\texttt{++k}\)
// \(\texttt{k++}\) : Post-increment이다. postfix_expression -> primary_expression -> ... -> Leaf
// \(\texttt{++k}\) : Pre-incerment이다. unary_expression -> postfix_expression -> primary_expression -> ... -> Leaf
// 즉, 후위 연산자 토큰이 전위 연산자 토큰보다 Leaf에 더 가까우므로 연산자 우선 순위에 우위에 있다.
// 즉, Lexical Analyzer는 \(\texttt{k++}\)를 \(\texttt{++k}\)보다 먼저 처리한다.
unary_operator
: '&'
| '*'
| '+'
| '-'
| '~'
| '!'
;
cast_expression
: unary_expression
| '(' type_name ')' cast_expression
;
multiplicative_expression
: cast_expression
| multiplicative_expression '*' cast_expression
| multiplicative_expression '/' cast_expression
| multiplicative_expression '%' cast_expression
;
// multiplicative_expression에서는 * 토큰, / 토큰, % 토큰은 문법적으로 동일한 우선 순위를 갖도록 정의한다.
// *, /, % 토큰은 Left-Recursion으로써 정의되어, 서로 Left-Associativity를 만족한다.
// 즉, *, /, % 토큰들로 구성된 Statement는 Lexical Analyzer가 왼쪽(Left)부터 해석한다.
additive_expression
: multiplicative_expression
| additive_expression '+' multiplicative_expression
| additive_expression '-' multiplicative_expression
;
// additive_expression에서는 + 토큰, - 토큰은 문법적으로 동일한 우선 순위를 갖도록 정의한다.
// additive_expression은 multiplicative_express보다 Root에 가까워 문법적 우선 순위가 낮다.
// 즉, +, - 토큰은 *, /, % 토큰보다 우선 순위가 낮다.
// +, - 토큰은 Left-Recursion으로써 정의되어, 서로 Left-Associativity를 만족한다.
// 즉, +, - 토큰들로 구성된 Statement는 Lexical Analyzer가 왼쪽(Left)부터 해석한다.
shift_expression
: additive_expression
| shift_expression LEFT_OP additive_expression
| shift_expression RIGHT_OP additive_expression
;
relational_expression
: shift_expression
| relational_expression '<' shift_expression
| relational_expression '>' shift_expression
| relational_expression LE_OP shift_expression
| relational_expression GE_OP shift_expression
;
equality_expression
: relational_expression
| equality_expression EQ_OP relational_expression
| equality_expression NE_OP relational_expression
;
// equality_expression에서는 EQ_OP(==) 토큰과 NE_OP(!=) 토큰은 문법적으로 동일한 우선 순위를 갖도록 정의한다.
// ==토큰과 !=토큰은 Left-Recursion으로써 정의되어, 서로 Left-Associativity를 만족한다.
// 즉 ==, !=토큰들로 구성된 Statement는 Lexical Analyzer가 왼쪽(Left)부터 해석한다.
and_expression
: equality_expression
| and_expression '&' equality_expression
;
exclusive_or_expression
: and_expression
| exclusive_or_expression '^' and_expression
;
// exclusive_or_expression는 Left-Recursion으로써 정의되었다.
// 재귀적 반복이 종결되면 and_expression으로 Reduce된다.
// 즉, ^토큰은 &토큰보다 우선 순위가 낮다.
inclusive_or_expression
: exclusive_or_expression
| inclusive_or_expression '|' exclusive_or_expression
;
// inclusive OR은 일반적인 OR 연산을 의미한다.
// 우선 순위 : &(and) > ^(exclusive_or) > |(inclusive_or)
logical_and_expression
: inclusive_or_expression
| logical_and_expression AND_OP inclusive_or_expression
;
// AND_OP(&&)
logical_or_expression
: logical_and_expression
| logical_or_expression OR_OP logical_and_expression
;
// OR_OP(||)
conditional_expression
: logical_or_expression
| logical_or_expression '?' expression ':' conditional_expression
;
// conditional_expression은 삼항 연산 문법을 제공한다.
// Right_Recursion으로써 문법을 정의한다.
// 즉, 삼항 연산이 중첩되어있는 Statement는 Lexical Analyzer가 오른쪽(Right)부터 해석한다.
assignment_expression
: conditional_expression
| unary_expression assignment_operator assignment_expression
;
// assignment_expression은 대입(배정) 연산 문법을 제공한다.
// Right-Recursion으로써 문법을 정의한다.
// 즉, 대입 연산이 중첩되어있는 Statement는 Lexical Analyzer가 오른쪽(Right)부터 해석한다.
assignment_operator
: '='
| MUL_ASSIGN
| DIV_ASSIGN
| MOD_ASSIGN
| ADD_ASSIGN
| SUB_ASSIGN
| LEFT_ASSIGN
| RIGHT_ASSIGN
| AND_ASSIGN
| XOR_ASSIGN
| OR_ASSIGN
;
expression
: assignment_expression
| expression ',' assignment_expression
;
// Left-Recursion으로써 문법을 정의한다.
// expression은 다수의 수식이 Comma로 구분되어 반복되면, Lexical Analyzer는 가장 왼쪽(Left)부터 해석한다.
constant_expression
: conditional_expression
;
// 삼항 연산을 처리하는 conditional_expression은 곧바로 constant_expression으로 Reduce된다.
declaration
: declaration_specifiers ';'
| declaration_specifiers init_declarator_list ';'
;
declaration_specifiers
: storage_class_specifier
| storage_class_specifier declaration_specifiers
| type_specifier
| type_specifier declaration_specifiers
| type_qualifier
| type_qualifier declaration_specifiers
;
// declaration_specifiers는 크게 storage_class_specifier, type_specifier, type_qualifier로 구분된다.
// storage_class_specifier, type_specifier, type_qualifier는 모두 Right_Recursion으로써 정의된다.
// 즉, 이에 해당되는 지정자들이 연속될 경우, Lexical Analyzer는 오른쪽(Right)부터 해석한다.
// \(\texttt{static struct int}\)의 경우, \(\texttt{int} \to \texttt{struct} \to \texttt{static}\) 순서로 해석된다.
init_declarator_list
: init_declarator
| init_declarator_list ',' init_declarator
;
// init_declarator_list는 Left-Recursion으로써 정의되었다.
// 즉, Comma로 구분되어 반복될 경우, Lexical Analyzer는 왼쪽(Left)부터 해석한다.
init_declarator
: declarator
| declarator '=' initializer
;
// init_declarator는 변수의 선언, 변수의 선언 및 초기화에 관한 문법을 제공한다.
storage_class_specifier
: TYPEDEF
| EXTERN
| STATIC
| AUTO
| REGISTER
;
type_specifier
: VOID
| CHAR
| SHORT
| INT
| LONG
| FLOAT
| DOUBLE
| SIGNED
| UNSIGNED
| struct_or_union_specifier
| enum_specifier
| TYPE_NAME
;
struct_or_union_specifier
: struct_or_union IDENTIFIER '{' struct_declaration_list '}'
| struct_or_union '{' struct_declaration_list '}'
| struct_or_union IDENTIFIER
;
struct_or_union
: STRUCT
| UNION
;
struct_declaration_list
: struct_declaration
| struct_declaration_list struct_declaration
;
struct_declaration
: specifier_qualifier_list struct_declarator_list ';'
;
specifier_qualifier_list
: type_specifier specifier_qualifier_list
| type_specifier
| type_qualifier specifier_qualifier_list
| type_qualifier
;
// specifier_qualifier_list는 Right_recursion으로써 정의되었다.
// 즉, type_specifier, type_qualifier이 연속될 경우, Lexical Analyzer는 오른쪽(Right)부터 해석한다.
struct_declarator_list
: struct_declarator
| struct_declarator_list ',' struct_declarator
;
struct_declarator
: declarator
| ':' constant_expression
| declarator ':' constant_expression
;
enum_specifier
: ENUM '{' enumerator_list '}'
| ENUM IDENTIFIER '{' enumerator_list '}'
| ENUM IDENTIFIER
;
enumerator_list
: enumerator
| enumerator_list ',' enumerator
;
enumerator
: IDENTIFIER
| IDENTIFIER '=' constant_expression
;
type_qualifier
: CONST
| VOLATILE
;
declarator
: pointer direct_declarator
| direct_declarator
;
direct_declarator
: IDENTIFIER
| '(' declarator ')'
| direct_declarator '[' constant_expression ']'
| direct_declarator '[' ']'
| direct_declarator '(' parameter_type_list ')'
| direct_declarator '(' identifier_list ')'
| direct_declarator '(' ')'
;
pointer
: '*'
| '*' type_qualifier_list
| '*' pointer
| '*' type_qualifier_list pointer
;
// pointer는 Right-Recursion으로 정의됨으로써, Asterisk(*)가 연속되는 것을 허용하는 문법을 제공한다.
type_qualifier_list
: type_qualifier
| type_qualifier_list type_qualifier
;
parameter_type_list
: parameter_list
| parameter_list ',' ELLIPSIS
;
// ELLIPSIS : ... (3개의 Dot들이 연속된 형태이다. Multiple Argument에 대응하기 위한(매개변수의 개수가 미정일 때 사용하는) 연산자이다.)
parameter_list
: parameter_declaration
| parameter_list ',' parameter_declaration
;
parameter_declaration
: declaration_specifiers declarator
| declaration_specifiers abstract_declarator
| declaration_specifiers
;
identifier_list
: IDENTIFIER
| identifier_list ',' IDENTIFIER
;
type_name
: specifier_qualifier_list
| specifier_qualifier_list abstract_declarator
;
abstract_declarator
: pointer
| direct_abstract_declarator
| pointer direct_abstract_declarator
;
direct_abstract_declarator
: '(' abstract_declarator ')'
| '[' ']'
| '[' constant_expression ']'
| direct_abstract_declarator '[' ']'
| direct_abstract_declarator '[' constant_expression ']'
| '(' ')'
| '(' parameter_type_list ')'
| direct_abstract_declarator '(' ')'
| direct_abstract_declarator '(' parameter_type_list ')'
;
// direct_declarator와 유사하나, direct_declarator는 IDENTIFIER로 곧바로 Reduce될 수 있는 반면,
// direct_abstract_declarator는 그럴 수 없다.
// 위 문법에 의하여 ( )[ ]( )[80]과 같은 문법이 허용된다.
// 즉, 무언가를 선언할 때, identifier는 필요하지 않고, type만 필요한 경우 사용하는 문법이다.
// type_name 문법, parameter_declaration 문법 사용시 필요한 문법이다.
initializer
: assignment_expression
| '{' initializer_list '}'
| '{' initializer_list ',' '}'
;
// init_declarator의 일부로써, initializer가 사용된다.
// \(\texttt{{ i = 4, j = 8, }}\) 문장의 경우 첫 번째 Comma는 initializer에 해당되는 Comma이며,
// 두 번째 Comma는 initializer_list의 Comma이다.
initializer_list
: initializer
| initializer_list ',' initializer
;
statement
: labeled_statement
| compound_statement
| expression_statement
| selection_statement
| iteration_statement
| jump_statement
;
labeled_statement
: IDENTIFIER ':' statement
| CASE constant_expression ':' statement
| DEFAULT ':' statement
;
// IDENTIFIER는 레이블 이름로 해석된다.
// \(\texttt{switch}\)문에서 주로 사용하는 jump문에 대한 문법이다.
compound_statement
: '{' '}'
| '{' statement_list '}'
| '{' declaration_list '}'
| '{' declaration_list statement_list '}'
;
// C언어에서는 선언이 나온 후, 문장이 나온다.
declaration_list
: declaration
| declaration_list declaration
;
statement_list
: statement
| statement_list statement
;
expression_statement
: ';'
| expression ';'
;
// expression_statement는 세미 콜론만 단독으로 있어도 Statement로 간주하는 문법을 제공한다.
// 즉, 단독으로 위치한 세미콜론도 expression_statement로 Ruduce되는 하나의 문장이다.
selection_statement
: IF '(' expression ')' statement
| IF '(' expression ')' statement ELSE statement
| SWITCH '(' expression ')' statement
;
// selection_statement는 \(\texttt{if}\)와 \(\texttt{switch}\)문에 소괄호가 없는 것을 허용하지 않는 문법을 제공한다.
iteration_statement
: WHILE '(' expression ')' statement
| DO statement WHILE '(' expression ')' ';'
| FOR '(' expression_statement expression_statement ')' statement
| FOR '(' expression_statement expression_statement expression ')' statement
;
jump_statement
: GOTO IDENTIFIER ';'
| CONTINUE ';'
| BREAK ';'
| RETURN ';'
| RETURN expression ';'
;
// jump : 프로그램의 Flow를 바꾼다.
// \(\texttt{return (1);}\) 에서 (1)이 통채로 expression으로 Reduce된다.
translation_unit
: external_declaration
| translation_unit external_declaration
;
// external_declaration이 한 번 이상 Recursive하게 반복되는 구조이다.
// translation_unit은 Left-Recursion으로써 구현되었다.
external_declaration
: function_definition
| declaration
;
// external_declaration은 함수 정의, 외부 변수 선언 문법을 제공한다.
// 즉, 외부에 선언될 수 있는 것은 함수, 변수로 제한한다.
function_definition
: declaration_specifiers declarator declaration_list compound_statement
| declaration_specifiers declarator compound_statement
| declarator declaration_list compound_statement
| declarator compound_statement
;
// 본 Post의 하단에 가까울수록 Root에 가까운 문법이다. (우선순위가 낮다.)
// 즉, 올라갈수록 파스 트리의 Leaf에 가까워져 우선 순위가 높아진다.
%%
#include
extern char yytext[];
extern int column;
yyerror(s)
char *s;
{
fflush(stdout);
printf("\n%*s\n%*s\n", column, "^", column, s);
}
