[Programming Language Theory] ANSI C Yacc Grammar

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);
}