tagged release 0.7.1

[parrot.git] / languages / c99 / src / parser / grammar.pg

# $Id$
# Copyright (C) 2008, The Perl Foundation.

=begin overview

This is the grammar for C99 written as a sequence of Perl 6 rules.


taken from n869.pdf
google for n869.pdf

=end overview

grammar C99::Grammar is PCT::Grammar;

## A.2.4 External definitions
##

token TOP {
    ^
    <external_declaration>+
    [ $ || <.panic: Syntax error> ]
    {*}
}

rule external_declaration {
    | <declaration> {*}          #= declaration
    | <function_definition> {*}  #= function_definition
}

rule function_definition {
    <declaration_specifiers>
    <declarator>
    <declaration>*
    <compound_statement>
    {*}
}


## A.2.2
##

rule declaration {
    <declaration_specifiers>
    [ <init_declarator> [',' <init_declarator>]* ]?
    ';'
    {*}
}

rule declaration_specifiers {
    [ <type_specifier>
    | <storage_class_specifier>
    | <type_qualifier>
    | <function_specifier>
    ]+
}

rule function_specifier {
    'inline'
}

rule init_declarator {
    <declarator> ['=' <initializer>]?
    {*}
}

rule storage_class_specifier {
    | 'typedef'
    | 'extern'
    | 'static'
    | 'auto'
    | 'register'
}

rule type_specifier {
    | <builtin_type>
    | <struct_or_union_specifier>
    | <enum_specifier>
    | <typedef_name>
}

token builtin_type {
    | 'void'
    | 'char'
    | 'short'
    | 'int'
    | 'long'
    | 'float'
    | 'double'
    | 'signed'
    | 'unsigned'
    | '_Bool'
    | '_Complex'
    | '_Imaginary'
}

rule struct_or_union_specifier {
    $<type>=['struct'|'union']
    [
    | <struct_or_union_definition>
    | <pre_declaration>
    ]
}

rule struct_or_union_definition {
    <identifier>? '{' <struct_declaration>+ '}'
}

rule pre_declaration {
    <identifier>
}

rule struct_declaration {
    <specifier_qualifier_list> <struct_declarator_list>* ';'
}

rule specifier_qualifier_list {
    [
    | <type_specifier>
    | <type_qualifier>
    ]+
}

rule struct_declarator_list {
    <struct_declarator> [',' <struct_declarator>]*
}

rule struct_declarator {
    | <declarator>? ':' <constant_expression>
    | <declarator>
}

rule enum_specifier {
    | 'enum' <identifier>? '{' <enumerator_list> [',']? '}'
    | 'enum' <identifier>
}

rule enumerator_list {
    <enumerator> [',' <enumerator>]*
}

rule enumerator {
    <enumeration_constant> ['=' <constant_expression>]?
}

rule type_qualifier {
    $<qualifier>=['const'|'restrict'|'volatile']
}

rule declarator {
    <pointer>?
    <direct_declarator>
    {*}
}

rule direct_declarator {
    <declarator_prefix>
    <declarator_suffix>*
    {*}
}

rule declarator_prefix {
    | '(' <declarator> ')' {*}       #= declarator
    | <identifier> {*}               #= identifier
}

rule declarator_suffix {
    | '(' <parameter_type_list> ')' {*}    #= parameter_type_list
    | '(' <identifier_list>? ')' {*}       #= identifier_list ## old-style C parameter declarations
    | '[' <assignment_expression>? ']'
    | '[' '*' ']'
}

rule pointer {
    '*' <type_qualifier>* ['*']?
}

rule parameter_type_list {
    <parameter_list>  [$<vararg>=[',' '...']]?
    {*}
}

rule parameter_list {
    <parameter_declaration> [',' <parameter_declaration>]*
    {*}
}

rule parameter_declaration {
    <declaration_specifiers>
    [
    | <declarator> {*}               #= declarator
    | <abstract_declarator>? {*}     #= abstract_declarator
    ]
}

rule identifier_list {
    <identifier> [',' <identifier>]*
}

rule type_name {
    <specifier_qualifier_list> <abstract_declarator>?
}

rule abstract_declarator {
    | '*'
    | ['*']? <direct_abstract_declarator>
}

rule direct_abstract_declarator {
    [
    | '(' <abstract_declatator> ')'
    | '[' <assignment_expression>? ']'
    | '(' <parameter_type_list> ')'
    ]
    <direct_abstract_declarator_1>*
}

rule direct_abstract_declarator_1 {
    | '[' <assignment_expression>? ']'
    | '[' '*' ']'
    | '(' <parameter_type_list> ')'
}

rule typedef_name {

## a typedef name can be a return type specifier. This is ambiguous, because
## the parser doesn't know if it's a return type thingie or the name of the
## function. Therefore, typedef'd names must be stored in a %hash, so that
## this rule is not calling <identifier>, but inspecting the registered
## typedef'd names. For now, specify 'SOME_TYPEDEF_NAME' as the only typedef'd name.
##
    #<identifier>
    'SOME_TYPEDEF_NAME'
}

rule initializer {
    | <assignment_expression>
    | '{' <initializer_list> [',']? '}'
}

rule initializer_list {
    <initializer_item> [',' <initializer_item>]*
}

rule initializer_item {
    <designation>? <initializer>
}

rule designation {
    <designator>+ '='
}

rule designator {
    | '[' <constant_expression> ']'
    | '.' <identifier>
}


## A.2.3 Statements
##

rule statement {
    | <labeled_statement>
    | <compound_statement> {*}        #= compound_statement
    | <expression_statement> {*}      #= expression_statement
    | <if_statement> {*}              #= if_statement
    | <switch_statement>
    | <while_statement> {*}           #= while_statement
    | <do_while_statement> {*}        #= do_while_statement
    | <for1_statement> {*}            #= for1_statement
    | <for2_statement> {*}            #= for2_statement
    | <jump_statement> {*}            #= jump_statement
}

rule labeled_statement {
    | <identifier> ':' <statement>
    | 'case' <constant_expression> ':' <statement>
    | 'default' ':' <statement>
}

rule compound_statement {
    '{' <block_item>* '}'
    {*}
}

rule block_item {
    | <declaration> {*}    #= declaration
    | <statement> {*}      #= statement
}

rule expression_statement {
    <expression>? ';'
    {*}
}

rule if_statement {
    'if' '(' <expression> ')' <statement> ['else' $<else>=<statement>]?
    {*}
}

rule switch_statement {
    'switch' '(' <expression> ')' <statement>
}

rule while_statement {
    'while' '(' <expression> ')' <statement>
    {*}
}

rule do_while_statement {
    'do' <statement> 'while' '(' <expression> ')' ';'
    {*}
}

rule for1_statement {
    'for' '(' [$<init>=<expression>]? ';' [$<cond>=<expression>]? ';' [$<step>=<expression>]? ')'
    <statement>
    {*}
}

rule for2_statement {
    'for' '(' <declaration> [$<cond>=<expression>]? ';' [$<step>=<expression>]? ')' <statement>
    {*}
}

rule jump_statement {
    | 'goto' <identifier> ';' {*}         #= goto
    | 'continue' ';' {*}                  #= continue
    | 'break' ';' {*}                     #= break
    | 'return' <expression>? ';' {*}      #= return
}


## A.1.1 Lexical elements
##
##rule token {
##  | <keyword>
##  | <identifier>
##  | <constant>
##  | <c_string_literal>
##  | <punctuator>
##}

regex preprocessing_token {
  | <header_name>
  | <identifier>
  | <pp_number>
  | <character_constant>
  | <string_literal>
  | <!pound> <punctuator>
  | <universal_character_name>
  | <-[# \r\n\t]>\S* ## <-[#]-\S>\S* ##non-whitespace
}

## A.1.2 Keywords
##
token keyword {
  [ auto      | enum      | restrict  | unsigned
  | break     | extern    | return    | void
  | case      | float     | short     | volatile
  | char      | for       | signed    | while
  | const     | goto      | sizeof    | _Bool
  | continue  | if        | static    | _Complex
  | default   | inline    | struct    | _Imaginary
  | do        | int       | switch
  | double    | long      | typedef
  | else      | register  | union     ]>>

}

token reserved_word {
    <keyword>
}


token identifier {
    <!reserved_word>
    <identifier_nondigit> [ <identifier_nondigit> | <digit> ]*
    {*}
}

token identifier_nondigit {
    <alpha> | <[_]> | <universal_character_name>
}

## A.1.4 Universal character names
##
token universal_character_name {
  | '\u' <xdigit>**{4}
  | '\U' <xdigit>**{8}
}


## A.1.5 Constants
##
token constant {
    | <floating_constant> {*}       #= floating_constant
    | <integer_constant> {*}        #= integer_constant
    | <enumeration_constant> {*}    #= enumeration_constant
    | <character_constant> {*}      #= character_constant
}

token integer_constant {
    [ <decimal_constant>
    | <octal_constant>
    | <hexadecimal_constant>
    ]
    <integer_suffix>?
    {*}
}

token decimal_constant {
    <[1..9]> <digit>*
}

token octal_constant {
    0 <[0..7]>*
}

token hexadecimal_constant {
    0 <[xX]> <xdigit>+
}

token integer_suffix {
    | <[uU]> [ll?|LL?]?
    | [ll?|LL?] <[uU]>?
}

token floating_constant {
    [
    | <decimal_floating_constant>
    | <hexadecimal_floating_constant>
    ]
    {*}
}

token decimal_floating_constant {
    [
    | <fractional_constant> <exponent_part>?
    | <digit_sequence> <exponent_part>
    ]
    <floating_suffix>?
}

token hexadecimal_prefix {
  0 <[xX]>
}

token hexadecimal_floating_constant {
  <hexadecimal_prefix>
  [
  | <hexadecimal_fractional_constant>
  | <hexadecimal_digit_constant>
  ]
  <binary_exponent_part> <floating_suffix>?
}

token fractional_constant {
  | <digit_sequence>? \. <digit_sequence>
  | <digit_sequence> \.
}

token exponent_part {
  <[eE]> ['+'|'-']? <digit_sequence>
}

token digit_sequence { <digit>+ }

token hexadecimal_fractional_constant {
  | <hexadecimal_digit_sequence>? \. <hexadecimal_digit_sequence>
  | <hexadecimal_digit_sequence> \.
}

token binary_exponent_part {
  <[pP]> ['+'|'-']? <digit_sequence>
}

token hexadecimal_digit_sequence { <xdigit>+ }

token floating_suffix { <[fFlL]> }

token enumeration_constant { <identifier> }

token character_constant { [L]? \' <c_char>+ \' }

token <c_char> { <-['\\\n]> | <escape_sequence> }

token escape_sequence {
  \\
  [ <['"?\\abfnrtv]>
  | <octal_digit>**{1..3}
  | x <xdigit>+
  | <universal_character_name>
  ]
}

## A.1.6 String literals
token c_string_literal {
    [L]? <string_literal: '"'>
    {*}
}

##\" <s_char>* \"

token s_char { <-["\\\n]> | <escape_sequence> }


## A.2 Phrase structure grammar
##

## A.2.1 Expressions
##

rule constant_expression {
    <conditional_expression>
    {*}
}

rule expression {
    <assignment_expression> [',' <assignment_expression>]*
    {*}
}

rule assignment_expression {
    [<unary_expression> <assign_op>]* <conditional_expression>
    {*}
}

rule assign_op { '='|'*='|'/='|'%='|'+='|'-='|'<<='|'>>='|'&='|'^='|'|=' }

rule conditional_expression {
    <logical_expression> ['?' <expression> ':' <conditional_expression>]?
    {*}
}

rule logical_expression is optable { ... }

proto 'infix:||' is precedence('1') { ... }

proto 'infix:&&' is tighter('infix:||') { ... }

proto 'infix:|' is tighter('infix:&&') { ... }

proto 'infix:^' is tighter('infix:|') { ... }

proto 'infix:&' is tighter('infix:^') { ... }

proto 'infix:==' is tighter('infix:&') { ... }
proto 'infix:!=' is equal('infix:==') { ... }

proto 'infix:<' is tighter('infix:==') { ... }
proto 'infix:>' is equal('infix:<') { ... }
proto 'infix:>=' is equal('infix:<') { ... }
proto 'infix:<=' is equal('infix:<') { ... }

proto 'infix:<<' is tighter('infix:==') { ... }
proto 'infix:>>' is equal('infix:<<') { ... }

proto 'infix:+' is tighter('infix:<<') is pirop('n_add') { ... }
proto 'infix:-' is equal('infix:+') is pirop('n_sub') { ... }

proto 'infix:*' is tighter('infix:+') is pirop('n_mul') { ... }
proto 'infix:/' is equal('infix:*') is pirop('n_div') { ... }
proto 'infix:%' is equal('infix:*') is pirop('n_mod') { ... }

proto 'term:' is tighter('infix:*')
              is parsed(&cast_expression) { ... }


rule postfix_expression_prefix {
    | <primary_expression> {*}                                  #= primary_expression
    | '(' <type_name> ')' '{' <initializer_list> [',']? '}' {*} #= type_name
}

rule postfix_expression {
    <postfix_expression_prefix>
    <postfix_expression_suffix>*
    {*}
}

rule postfix_expression_suffix {
    | <index> {*}                           #= index
    | <arguments>  {*}                      #= arguments
    | <direct_field> {*}                    #= direct_field
    | <indirect_field> {*}                  #= indirect_field
    | <inc_or_dec> {*}                      #= inc_or_dec
}

rule inc_or_dec {
    $<op>=['++'|'--']
    {*}
}

rule index {
    '[' <expression> ']'
    {*}
}

rule direct_field {
    '.' <identifier>
    {*}
}

rule indirect_field {
    '->' <identifier>
    {*}
}

rule arguments {
    '(' <argument_expression_list>? ')'
    {*}
}

rule argument_expression_list {
    <assignment_expression> [',' <assignment_expression>]*
    {*}
}

rule unary_expression {
    | <postfix_expression> {*}              #= postfix_expression
    | <prefix_expression> {*}               #= prefix_expression
    | <unary_operator> <cast_expression>
    | 'sizeof' <unary_expression>
    | 'sizeof' '(' <type_name> ')'
}

rule prefix_expression {
    $<op>=['++'|'--'] <unary_expression>
    {*}
}

rule unary_operator {
    '&' | '*' | '+' | '-' | '~' | '!'
}

rule cast_expression {
    ['(' <type_name> ')']* <unary_expression>
    {*}
}

rule primary_expression {
    | <identifier> {*}             #= identifier
    | <constant> {*}               #= constant
    | <c_string_literal> {*}       #= c_string_literal
    | '(' <expression> ')' {*}     #= expression
}

token ws {
  [
  | '//' \N* \n
  | '/*' .*? '*/'
  | \s+
  | '#' \N* \n
  ]*
}

## A.1.7 Punctuators
##

token punctuator {
  | \[        | \]      | <[(){}.]>     | '->'
  | '++'      | '--'    | <[&*+\-~!/%]>
  | '<<'      | '>>'    | '<'    | '>'
  | '<='      | '>='    | '=='          | '!='
  | <[^|]>    | '&&'    | '||'
  | <[?:;]>   | '...'
  | <[*/%+\-&^|]>       | '<<'   | '>>' | '='
  | <[,#]>    | '##'
  | '<:'      | ':>'    | '<%'   | '%>' | '%:' | '%:%:'
}


## A.3 Preprocessing directives
##

rule pre_processing_file {
    <group>?
}

rule group {
    <group_part>+
}

rule group_part {
    | <pp_tokens>? <newline>
    | <if_section>
    | <control_line>
}

rule if_section {
    <if_group> <elif_group>* <else_group>? <endif_line>
}

rule if_group {
    | '#' 'if' <constant_expression> <newline> <group>?
    | '#' 'ifdef' <identifier> <newline> <group>?
    | '#' 'ifndef' <identifier> <newline> <group>?
}

rule elif_group {
    '#' 'elif' <constant_expression> <newline> <group>?
}

rule else_group {
    '#' 'else' <newline> <group>?
}

rule endif_line {
    '#' 'endif' <newline>
}

rule control_line {
    | '#' 'include' <pp_tokens> <newline>
    | '#' 'define' <identifier> <replacement_list> <newline>
    | '#' 'define' <identifier> <lparen> <identifier_list>? ')' <replacement_list> <newline>
    | '#' 'define' <identifier> <lparen> '...' ')' <replacement_list> <newline>
    | '#' 'define' <identifier> <lparen> <identifier_list> ',' '...' ')' <replacement_list> <newline>
    | '#' 'undef' <identifier> <newline>
    | '#' 'line' <pp_tokens> <newline>
    | '#' 'error' <pp_tokens>? <newline>
    | '#' 'pragma' <pp_tokens>? <newline>
    | '#' <newline>
}

rule pp_tokens {
    <preprocessing_token>+
}

rule preprocessing_token {
    | <header_name>
    | <identifier>
    | <pp_number>
    | <character_constant>
    | <c_string_literal>
    | <punctuator>
}

rule pp_number {
    ['.']? <digit> <pp_number_suffix>*
}

rule pp_number_suffix {
    | '.'
    | <identifier_nondigit>
    | <digit>
    | <[eEpP]> ['+'|'-']
}

rule replacement_list {
    <pp_tokens>?
}

token lparen {
    '('
}

token newline {
     \n
}

## A.1.8 Header names
token header_name {
    | \< <h_char>+ \>
    | \" <q_char>+ \"
}

token h_char { <-[\n>]> }
token q_char { <-[\n"]> }