ANSI C Recursive Decent Parser generated from BNF

cparser.cpp

// Auto Generated From ANSI C BNF using grammar adapted from Section A13 of The
// C programming language, 2nd edition, by Brian W. Kernighan and Dennis M.
// Ritchie, Prentice Hall, 1988.

struct state_t {};
bool lexer_found(const char *);
state_t state_save();
void state_restore(state_t&);
bool parse_integer_constant();
bool parse_character_constant();
bool parse_floating_constant();
bool parse_enumeration_constant();
bool parse_identifier();
bool parse_string();

struct parser_t {
  bool parse_storage_class_specifier();
  bool parse_expression_statement();
  bool parse_selection_statement();
  bool parse_constant();
  bool parse_unary_expression();
  bool parse_struct_or_union_specifier();
  bool parse_exclusive_or_expression();
  bool parse_initializer();
  bool parse_enumerator_list();
  bool parse_struct_declaration();
  bool parse_pointer();
  bool parse_and_expression();
  bool parse_external_declaration();
  bool parse_type_specifier();
  bool parse_specifier_qualifier();
  bool parse_compound_statement();
  bool parse_inclusive_or_expression();
  bool parse_iteration_statement();
  bool parse_type_name();
  bool parse_postfix_expression();
  bool parse_typedef_name();
  bool parse_enumerator();
  bool parse_relational_expression();
  bool parse_statement();
  bool parse_unary_operator();
  bool parse_cast_expression();
  bool parse_init_declarator();
  bool parse_struct_declarator_list();
  bool parse_logical_or_expression();
  bool parse_constant_expression();
  bool parse_assignment_operator();
  bool parse_struct_or_union();
  bool parse_declaration_specifier();
  bool parse_assignment_expression();
  bool parse_parameter_type_list();
  bool parse_parameter_declaration();
  bool parse_direct_declarator();
  bool parse_declarator();
  bool parse_additive_expression();
  bool parse_primary_expression();
  bool parse_declaration();
  bool parse_logical_and_expression();
  bool parse_shift_expression();
  bool parse_equality_expression();
  bool parse_jump_statement();
  bool parse_struct_declarator();
  bool parse_function_definition();
  bool parse_parameter_list();
  bool parse_multiplicative_expression();
  bool parse_type_qualifier();
  bool parse_labeled_statement();
  bool parse_abstract_declarator();
  bool parse_enum_specifier();
  bool parse_translation_unit();
  bool parse_initializer_list();
  bool parse_conditional_expression();
  bool parse_direct_abstract_declarator();
  bool parse_expression();
};

// <storage_class_specifier>
//  | auto
//  | register
//  | static
//  | extern
//  | typedef
bool parser_t::parse_storage_class_specifier() {
  state_t state = state_save();

  if (lexer_found("auto"))
    return true;
  state_restore(state);

  if (lexer_found("register"))
    return true;
  state_restore(state);

  if (lexer_found("static"))
    return true;
  state_restore(state);

  if (lexer_found("extern"))
    return true;
  state_restore(state);

  if (lexer_found("typedef"))
    return true;

  return false;
}

// <expression_statement>
//  | {<expression>}? ;
bool parser_t::parse_expression_statement() {
  state_t state = state_save();

  do {
    {
      state_t temp = state_save();
      if (!parse_expression())
        state_restore(temp);
    }
    if (!lexer_found(";"))
      break;
    return true;
  } while (0);

  return false;
}

// <selection_statement>
//  | if ( <expression> ) <statement>
//  | if ( <expression> ) <statement> else <statement>
//  | switch ( <expression> ) <statement>
bool parser_t::parse_selection_statement() {
  state_t state = state_save();

  if (lexer_found("if") &&
      lexer_found("(") &&
      parse_expression() &&
      lexer_found(")") &&
      parse_statement())
    return true;
  state_restore(state);

  if (lexer_found("if") &&
      lexer_found("(") &&
      parse_expression() &&
      lexer_found(")") &&
      parse_statement() &&
      lexer_found("else") &&
      parse_statement())
    return true;
  state_restore(state);

  if (lexer_found("switch") &&
      lexer_found("(") &&
      parse_expression() &&
      lexer_found(")") &&
      parse_statement())
    return true;

  return false;
}

// <constant>
//  | <integer_constant>
//  | <character_constant>
//  | <floating_constant>
//  | <enumeration_constant>
bool parser_t::parse_constant() {
  state_t state = state_save();

  if (parse_integer_constant())
    return true;
  state_restore(state);

  if (parse_character_constant())
    return true;
  state_restore(state);

  if (parse_floating_constant())
    return true;
  state_restore(state);

  if (parse_enumeration_constant())
    return true;

  return false;
}

// <unary_expression>
//  | <postfix_expression>
//  | ++ <unary_expression>
//  | -- <unary_expression>
//  | <unary_operator> <cast_expression>
//  | sizeof <unary_expression>
//  | sizeof <type_name>
bool parser_t::parse_unary_expression() {
  state_t state = state_save();

  if (parse_postfix_expression())
    return true;
  state_restore(state);

  if (lexer_found("++") &&
      parse_unary_expression())
    return true;
  state_restore(state);

  if (lexer_found("--") &&
      parse_unary_expression())
    return true;
  state_restore(state);

  if (parse_unary_operator() &&
      parse_cast_expression())
    return true;
  state_restore(state);

  if (lexer_found("sizeof") &&
      parse_unary_expression())
    return true;
  state_restore(state);

  if (lexer_found("sizeof") &&
      parse_type_name())
    return true;

  return false;
}

// <struct_or_union_specifier>
//  | <struct_or_union> <identifier> { {<struct_declaration>}+ }
//  | <struct_or_union> { {<struct_declaration>}+ }
//  | <struct_or_union> <identifier>
bool parser_t::parse_struct_or_union_specifier() {
  state_t state = state_save();

  do {
    if (!parse_struct_or_union())
      break;
    if (!parse_identifier())
      break;
    if (!lexer_found("{"))
      break;
    if (parse_struct_declaration())
      while (parse_struct_declaration());
    else
      break;
    if (!lexer_found("}"))
      break;
    return true;
  } while (0);
  state_restore(state);

  do {
    if (!parse_struct_or_union())
      break;
    if (!lexer_found("{"))
      break;
    if (parse_struct_declaration())
      while (parse_struct_declaration());
    else
      break;
    if (!lexer_found("}"))
      break;
    return true;
  } while (0);
  state_restore(state);

  if (parse_struct_or_union() &&
      parse_identifier())
    return true;

  return false;
}

// <exclusive_or_expression>
//  | <and_expression>
//  | <exclusive_or_expression> ^ <and_expression>
bool parser_t::parse_exclusive_or_expression() {
  state_t state = state_save();

  if (parse_and_expression())
    return true;
  state_restore(state);

  #pragma message("<exclusive_or_expression> is left recursive!")

  if (parse_exclusive_or_expression() &&
      lexer_found("^") &&
      parse_and_expression())
    return true;

  return false;
}

// <initializer>
//  | <assignment_expression>
//  | { <initializer_list> }
//  | { <initializer_list> , }
bool parser_t::parse_initializer() {
  state_t state = state_save();

  if (parse_assignment_expression())
    return true;
  state_restore(state);

  if (lexer_found("{") &&
      parse_initializer_list() &&
      lexer_found("}"))
    return true;
  state_restore(state);

  if (lexer_found("{") &&
      parse_initializer_list() &&
      lexer_found(",") &&
      lexer_found("}"))
    return true;

  return false;
}

// <enumerator_list>
//  | <enumerator>
//  | <enumerator_list> , <enumerator>
bool parser_t::parse_enumerator_list() {
  state_t state = state_save();

  if (parse_enumerator())
    return true;
  state_restore(state);

  #pragma message("<enumerator_list> is left recursive!")

  if (parse_enumerator_list() &&
      lexer_found(",") &&
      parse_enumerator())
    return true;

  return false;
}

// <struct_declaration>
//  | {<specifier_qualifier>}* <struct_declarator_list>
bool parser_t::parse_struct_declaration() {
  state_t state = state_save();

  do {
    while (parse_specifier_qualifier());
    if (!parse_struct_declarator_list())
      break;
    return true;
  } while (0);

  return false;
}

// <pointer>
//  | * {<type_qualifier>}* {<pointer>}?
bool parser_t::parse_pointer() {
  state_t state = state_save();

  do {
    if (!lexer_found("*"))
      break;
    while (parse_type_qualifier());
    {
      state_t temp = state_save();
      if (!parse_pointer())
        state_restore(temp);
    }
    return true;
  } while (0);

  return false;
}

// <and_expression>
//  | <equality_expression>
//  | <and_expression> & <equality_expression>
bool parser_t::parse_and_expression() {
  state_t state = state_save();

  if (parse_equality_expression())
    return true;
  state_restore(state);

  #pragma message("<and_expression> is left recursive!")

  if (parse_and_expression() &&
      lexer_found("&") &&
      parse_equality_expression())
    return true;

  return false;
}

// <external_declaration>
//  | <function_definition>
//  | <declaration>
bool parser_t::parse_external_declaration() {
  state_t state = state_save();

  if (parse_function_definition())
    return true;
  state_restore(state);

  if (parse_declaration())
    return true;

  return false;
}

// <type_specifier>
//  | void
//  | char
//  | short
//  | int
//  | long
//  | float
//  | double
//  | signed
//  | unsigned
//  | <struct_or_union_specifier>
//  | <enum_specifier>
//  | <typedef_name>
bool parser_t::parse_type_specifier() {
  state_t state = state_save();

  if (lexer_found("void"))
    return true;
  state_restore(state);

  if (lexer_found("char"))
    return true;
  state_restore(state);

  if (lexer_found("short"))
    return true;
  state_restore(state);

  if (lexer_found("int"))
    return true;
  state_restore(state);

  if (lexer_found("long"))
    return true;
  state_restore(state);

  if (lexer_found("float"))
    return true;
  state_restore(state);

  if (lexer_found("double"))
    return true;
  state_restore(state);

  if (lexer_found("signed"))
    return true;
  state_restore(state);

  if (lexer_found("unsigned"))
    return true;
  state_restore(state);

  if (parse_struct_or_union_specifier())
    return true;
  state_restore(state);

  if (parse_enum_specifier())
    return true;
  state_restore(state);

  if (parse_typedef_name())
    return true;

  return false;
}

// <specifier_qualifier>
//  | <type_specifier>
//  | <type_qualifier>
bool parser_t::parse_specifier_qualifier() {
  state_t state = state_save();

  if (parse_type_specifier())
    return true;
  state_restore(state);

  if (parse_type_qualifier())
    return true;

  return false;
}

// <compound_statement>
//  | { {<declaration>}* {<statement>}* }
bool parser_t::parse_compound_statement() {
  state_t state = state_save();

  do {
    if (!lexer_found("{"))
      break;
    while (parse_declaration());
    while (parse_statement());
    if (!lexer_found("}"))
      break;
    return true;
  } while (0);

  return false;
}

// <inclusive_or_expression>
//  | <exclusive_or_expression>
//  | <inclusive_or_expression> | <exclusive_or_expression>
bool parser_t::parse_inclusive_or_expression() {
  state_t state = state_save();

  if (parse_exclusive_or_expression())
    return true;
  state_restore(state);

  #pragma message("<inclusive_or_expression> is left recursive!")

  if (parse_inclusive_or_expression() &&
      lexer_found("|") &&
      parse_exclusive_or_expression())
    return true;

  return false;
}

// <iteration_statement>
//  | while ( <expression> ) <statement>
//  | do <statement> while ( <expression> ) ;
//  | for ( {<expression>}? ; {<expression>}? ; {<expression>}? ) <statement>
bool parser_t::parse_iteration_statement() {
  state_t state = state_save();

  if (lexer_found("while") &&
      lexer_found("(") &&
      parse_expression() &&
      lexer_found(")") &&
      parse_statement())
    return true;
  state_restore(state);

  if (lexer_found("do") &&
      parse_statement() &&
      lexer_found("while") &&
      lexer_found("(") &&
      parse_expression() &&
      lexer_found(")") &&
      lexer_found(";"))
    return true;
  state_restore(state);

  do {
    if (!lexer_found("for"))
      break;
    if (!lexer_found("("))
      break;
    {
      state_t temp = state_save();
      if (!parse_expression())
        state_restore(temp);
    }
    if (!lexer_found(";"))
      break;
    {
      state_t temp = state_save();
      if (!parse_expression())
        state_restore(temp);
    }
    if (!lexer_found(";"))
      break;
    {
      state_t temp = state_save();
      if (!parse_expression())
        state_restore(temp);
    }
    if (!lexer_found(")"))
      break;
    if (!parse_statement())
      break;
    return true;
  } while (0);

  return false;
}

// <type_name>
//  | {<specifier_qualifier>}+ {<abstract_declarator>}?
bool parser_t::parse_type_name() {
  state_t state = state_save();

  do {
    if (parse_specifier_qualifier())
      while (parse_specifier_qualifier());
    else
      break;
    {
      state_t temp = state_save();
      if (!parse_abstract_declarator())
        state_restore(temp);
    }
    return true;
  } while (0);

  return false;
}

// <postfix_expression>
//  | <primary_expression>
//  | <postfix_expression> [ <expression> ]
//  | <postfix_expression> ( {<assignment_expression>}* )
//  | <postfix_expression> . <identifier>
//  | <postfix_expression> -> <identifier>
//  | <postfix_expression> ++
//  | <postfix_expression> --
bool parser_t::parse_postfix_expression() {
  state_t state = state_save();

  if (parse_primary_expression())
    return true;
  state_restore(state);

  #pragma message("<postfix_expression> is left recursive!")

  if (parse_postfix_expression() &&
      lexer_found("[") &&
      parse_expression() &&
      lexer_found("]"))
    return true;
  state_restore(state);

  #pragma message("<postfix_expression> is left recursive!")

  do {
    if (!parse_postfix_expression())
      break;
    if (!lexer_found("("))
      break;
    while (parse_assignment_expression());
    if (!lexer_found(")"))
      break;
    return true;
  } while (0);
  state_restore(state);

  #pragma message("<postfix_expression> is left recursive!")

  if (parse_postfix_expression() &&
      lexer_found(".") &&
      parse_identifier())
    return true;
  state_restore(state);

  #pragma message("<postfix_expression> is left recursive!")

  if (parse_postfix_expression() &&
      lexer_found("->") &&
      parse_identifier())
    return true;
  state_restore(state);

  #pragma message("<postfix_expression> is left recursive!")

  if (parse_postfix_expression() &&
      lexer_found("++"))
    return true;
  state_restore(state);

  #pragma message("<postfix_expression> is left recursive!")

  if (parse_postfix_expression() &&
      lexer_found("--"))
    return true;

  return false;
}

// <typedef_name>
//  | <identifier>
bool parser_t::parse_typedef_name() {
  state_t state = state_save();

  if (parse_identifier())
    return true;

  return false;
}

// <enumerator>
//  | <identifier>
//  | <identifier> = <constant_expression>
bool parser_t::parse_enumerator() {
  state_t state = state_save();

  if (parse_identifier())
    return true;
  state_restore(state);

  if (parse_identifier() &&
      lexer_found("=") &&
      parse_constant_expression())
    return true;

  return false;
}

// <relational_expression>
//  | <shift_expression>
//  | <relational_expression> < <shift_expression>
//  | <relational_expression> > <shift_expression>
//  | <relational_expression> <= <shift_expression>
//  | <relational_expression> >= <shift_expression>
bool parser_t::parse_relational_expression() {
  state_t state = state_save();

  if (parse_shift_expression())
    return true;
  state_restore(state);

  #pragma message("<relational_expression> is left recursive!")

  if (parse_relational_expression() &&
      lexer_found("<") &&
      parse_shift_expression())
    return true;
  state_restore(state);

  #pragma message("<relational_expression> is left recursive!")

  if (parse_relational_expression() &&
      lexer_found(">") &&
      parse_shift_expression())
    return true;
  state_restore(state);

  #pragma message("<relational_expression> is left recursive!")

  if (parse_relational_expression() &&
      lexer_found("<=") &&
      parse_shift_expression())
    return true;
  state_restore(state);

  #pragma message("<relational_expression> is left recursive!")

  if (parse_relational_expression() &&
      lexer_found(">=") &&
      parse_shift_expression())
    return true;

  return false;
}

// <statement>
//  | <labeled_statement>
//  | <expression_statement>
//  | <compound_statement>
//  | <selection_statement>
//  | <iteration_statement>
//  | <jump_statement>
bool parser_t::parse_statement() {
  state_t state = state_save();

  if (parse_labeled_statement())
    return true;
  state_restore(state);

  if (parse_expression_statement())
    return true;
  state_restore(state);

  if (parse_compound_statement())
    return true;
  state_restore(state);

  if (parse_selection_statement())
    return true;
  state_restore(state);

  if (parse_iteration_statement())
    return true;
  state_restore(state);

  if (parse_jump_statement())
    return true;

  return false;
}

// <unary_operator>
//  | &
//  | *
//  | +
//  | -
//  | ~
//  | !
bool parser_t::parse_unary_operator() {
  state_t state = state_save();

  if (lexer_found("&"))
    return true;
  state_restore(state);

  if (lexer_found("*"))
    return true;
  state_restore(state);

  if (lexer_found("+"))
    return true;
  state_restore(state);

  if (lexer_found("-"))
    return true;
  state_restore(state);

  if (lexer_found("~"))
    return true;
  state_restore(state);

  if (lexer_found("!"))
    return true;

  return false;
}

// <cast_expression>
//  | <unary_expression>
//  | ( <type_name> ) <cast_expression>
bool parser_t::parse_cast_expression() {
  state_t state = state_save();

  if (parse_unary_expression())
    return true;
  state_restore(state);

  if (lexer_found("(") &&
      parse_type_name() &&
      lexer_found(")") &&
      parse_cast_expression())
    return true;

  return false;
}

// <init_declarator>
//  | <declarator>
//  | <declarator> = <initializer>
bool parser_t::parse_init_declarator() {
  state_t state = state_save();

  if (parse_declarator())
    return true;
  state_restore(state);

  if (parse_declarator() &&
      lexer_found("=") &&
      parse_initializer())
    return true;

  return false;
}

// <struct_declarator_list>
//  | <struct_declarator>
//  | <struct_declarator_list> , <struct_declarator>
bool parser_t::parse_struct_declarator_list() {
  state_t state = state_save();

  if (parse_struct_declarator())
    return true;
  state_restore(state);

  #pragma message("<struct_declarator_list> is left recursive!")

  if (parse_struct_declarator_list() &&
      lexer_found(",") &&
      parse_struct_declarator())
    return true;

  return false;
}

// <logical_or_expression>
//  | <logical_and_expression>
//  | <logical_or_expression> || <logical_and_expression>
bool parser_t::parse_logical_or_expression() {
  state_t state = state_save();

  if (parse_logical_and_expression())
    return true;
  state_restore(state);

  #pragma message("<logical_or_expression> is left recursive!")

  if (parse_logical_or_expression() &&
      lexer_found("||") &&
      parse_logical_and_expression())
    return true;

  return false;
}

// <constant_expression>
//  | <conditional_expression>
bool parser_t::parse_constant_expression() {
  state_t state = state_save();

  if (parse_conditional_expression())
    return true;

  return false;
}

// <assignment_operator>
//  | =
//  | *=
//  | /=
//  | %=
//  | +=
//  | -=
//  | <<=
//  | >>=
//  | &=
//  | ^=
//  | |=
bool parser_t::parse_assignment_operator() {
  state_t state = state_save();

  if (lexer_found("="))
    return true;
  state_restore(state);

  if (lexer_found("*="))
    return true;
  state_restore(state);

  if (lexer_found("/="))
    return true;
  state_restore(state);

  if (lexer_found("%="))
    return true;
  state_restore(state);

  if (lexer_found("+="))
    return true;
  state_restore(state);

  if (lexer_found("-="))
    return true;
  state_restore(state);

  if (lexer_found("<<="))
    return true;
  state_restore(state);

  if (lexer_found(">>="))
    return true;
  state_restore(state);

  if (lexer_found("&="))
    return true;
  state_restore(state);

  if (lexer_found("^="))
    return true;
  state_restore(state);

  if (lexer_found("|="))
    return true;

  return false;
}

// <struct_or_union>
//  | struct
//  | union
bool parser_t::parse_struct_or_union() {
  state_t state = state_save();

  if (lexer_found("struct"))
    return true;
  state_restore(state);

  if (lexer_found("union"))
    return true;

  return false;
}

// <declaration_specifier>
//  | <storage_class_specifier>
//  | <type_specifier>
//  | <type_qualifier>
bool parser_t::parse_declaration_specifier() {
  state_t state = state_save();

  if (parse_storage_class_specifier())
    return true;
  state_restore(state);

  if (parse_type_specifier())
    return true;
  state_restore(state);

  if (parse_type_qualifier())
    return true;

  return false;
}

// <assignment_expression>
//  | <conditional_expression>
//  | <unary_expression> <assignment_operator> <assignment_expression>
bool parser_t::parse_assignment_expression() {
  state_t state = state_save();

  if (parse_conditional_expression())
    return true;
  state_restore(state);

  if (parse_unary_expression() &&
      parse_assignment_operator() &&
      parse_assignment_expression())
    return true;

  return false;
}

// <parameter_type_list>
//  | <parameter_list>
//  | <parameter_list> , ...
bool parser_t::parse_parameter_type_list() {
  state_t state = state_save();

  if (parse_parameter_list())
    return true;
  state_restore(state);

  if (parse_parameter_list() &&
      lexer_found(",") &&
      lexer_found("..."))
    return true;

  return false;
}

// <parameter_declaration>
//  | {<declaration_specifier>}+ <declarator>
//  | {<declaration_specifier>}+ <abstract_declarator>
//  | {<declaration_specifier>}+
bool parser_t::parse_parameter_declaration() {
  state_t state = state_save();

  do {
    if (parse_declaration_specifier())
      while (parse_declaration_specifier());
    else
      break;
    if (!parse_declarator())
      break;
    return true;
  } while (0);
  state_restore(state);

  do {
    if (parse_declaration_specifier())
      while (parse_declaration_specifier());
    else
      break;
    if (!parse_abstract_declarator())
      break;
    return true;
  } while (0);
  state_restore(state);

  do {
    if (parse_declaration_specifier())
      while (parse_declaration_specifier());
    else
      break;
    return true;
  } while (0);

  return false;
}

// <direct_declarator>
//  | <identifier>
//  | ( <declarator> )
//  | <direct_declarator> [ {<constant_expression>}? ]
//  | <direct_declarator> ( <parameter_type_list> )
//  | <direct_declarator> ( {<identifier>}* )
bool parser_t::parse_direct_declarator() {
  state_t state = state_save();

  if (parse_identifier())
    return true;
  state_restore(state);

  if (lexer_found("(") &&
      parse_declarator() &&
      lexer_found(")"))
    return true;
  state_restore(state);

  #pragma message("<direct_declarator> is left recursive!")

  do {
    if (!parse_direct_declarator())
      break;
    if (!lexer_found("["))
      break;
    {
      state_t temp = state_save();
      if (!parse_constant_expression())
        state_restore(temp);
    }
    if (!lexer_found("]"))
      break;
    return true;
  } while (0);
  state_restore(state);

  #pragma message("<direct_declarator> is left recursive!")

  if (parse_direct_declarator() &&
      lexer_found("(") &&
      parse_parameter_type_list() &&
      lexer_found(")"))
    return true;
  state_restore(state);

  #pragma message("<direct_declarator> is left recursive!")

  do {
    if (!parse_direct_declarator())
      break;
    if (!lexer_found("("))
      break;
    while (parse_identifier());
    if (!lexer_found(")"))
      break;
    return true;
  } while (0);

  return false;
}

// <declarator>
//  | {<pointer>}? <direct_declarator>
bool parser_t::parse_declarator() {
  state_t state = state_save();

  do {
    {
      state_t temp = state_save();
      if (!parse_pointer())
        state_restore(temp);
    }
    if (!parse_direct_declarator())
      break;
    return true;
  } while (0);

  return false;
}

// <additive_expression>
//  | <multiplicative_expression>
//  | <additive_expression> + <multiplicative_expression>
//  | <additive_expression> - <multiplicative_expression>
bool parser_t::parse_additive_expression() {
  state_t state = state_save();

  if (parse_multiplicative_expression())
    return true;
  state_restore(state);

  #pragma message("<additive_expression> is left recursive!")

  if (parse_additive_expression() &&
      lexer_found("+") &&
      parse_multiplicative_expression())
    return true;
  state_restore(state);

  #pragma message("<additive_expression> is left recursive!")

  if (parse_additive_expression() &&
      lexer_found("-") &&
      parse_multiplicative_expression())
    return true;

  return false;
}

// <primary_expression>
//  | <identifier>
//  | <constant>
//  | <string>
//  | ( <expression> )
bool parser_t::parse_primary_expression() {
  state_t state = state_save();

  if (parse_identifier())
    return true;
  state_restore(state);

  if (parse_constant())
    return true;
  state_restore(state);

  if (parse_string())
    return true;
  state_restore(state);

  if (lexer_found("(") &&
      parse_expression() &&
      lexer_found(")"))
    return true;

  return false;
}

// <declaration>
//  | {<declaration_specifier>}+ {<init_declarator>}*
bool parser_t::parse_declaration() {
  state_t state = state_save();

  do {
    if (parse_declaration_specifier())
      while (parse_declaration_specifier());
    else
      break;
    while (parse_init_declarator());
    return true;
  } while (0);

  return false;
}

// <logical_and_expression>
//  | <inclusive_or_expression>
//  | <logical_and_expression> && <inclusive_or_expression>
bool parser_t::parse_logical_and_expression() {
  state_t state = state_save();

  if (parse_inclusive_or_expression())
    return true;
  state_restore(state);

  #pragma message("<logical_and_expression> is left recursive!")

  if (parse_logical_and_expression() &&
      lexer_found("&&") &&
      parse_inclusive_or_expression())
    return true;

  return false;
}

// <shift_expression>
//  | <additive_expression>
//  | <shift_expression> << <additive_expression>
//  | <shift_expression> >> <additive_expression>
bool parser_t::parse_shift_expression() {
  state_t state = state_save();

  if (parse_additive_expression())
    return true;
  state_restore(state);

  #pragma message("<shift_expression> is left recursive!")

  if (parse_shift_expression() &&
      lexer_found("<<") &&
      parse_additive_expression())
    return true;
  state_restore(state);

  #pragma message("<shift_expression> is left recursive!")

  if (parse_shift_expression() &&
      lexer_found(">>") &&
      parse_additive_expression())
    return true;

  return false;
}

// <equality_expression>
//  | <relational_expression>
//  | <equality_expression> == <relational_expression>
//  | <equality_expression> != <relational_expression>
bool parser_t::parse_equality_expression() {
  state_t state = state_save();

  if (parse_relational_expression())
    return true;
  state_restore(state);

  #pragma message("<equality_expression> is left recursive!")

  if (parse_equality_expression() &&
      lexer_found("==") &&
      parse_relational_expression())
    return true;
  state_restore(state);

  #pragma message("<equality_expression> is left recursive!")

  if (parse_equality_expression() &&
      lexer_found("!=") &&
      parse_relational_expression())
    return true;

  return false;
}

// <jump_statement>
//  | goto <identifier> ;
//  | continue ;
//  | break ;
//  | return {<expression>}? ;
bool parser_t::parse_jump_statement() {
  state_t state = state_save();

  if (lexer_found("goto") &&
      parse_identifier() &&
      lexer_found(";"))
    return true;
  state_restore(state);

  if (lexer_found("continue") &&
      lexer_found(";"))
    return true;
  state_restore(state);

  if (lexer_found("break") &&
      lexer_found(";"))
    return true;
  state_restore(state);

  do {
    if (!lexer_found("return"))
      break;
    {
      state_t temp = state_save();
      if (!parse_expression())
        state_restore(temp);
    }
    if (!lexer_found(";"))
      break;
    return true;
  } while (0);

  return false;
}

// <struct_declarator>
//  | <declarator>
//  | <declarator> : <constant_expression>
//  | : <constant_expression>
bool parser_t::parse_struct_declarator() {
  state_t state = state_save();

  if (parse_declarator())
    return true;
  state_restore(state);

  if (parse_declarator() &&
      lexer_found(":") &&
      parse_constant_expression())
    return true;
  state_restore(state);

  if (lexer_found(":") &&
      parse_constant_expression())
    return true;

  return false;
}

// <function_definition>
//  | {<declaration_specifier>}* <declarator> {<declaration>}* <compound_statement>
bool parser_t::parse_function_definition() {
  state_t state = state_save();

  do {
    while (parse_declaration_specifier());
    if (!parse_declarator())
      break;
    while (parse_declaration());
    if (!parse_compound_statement())
      break;
    return true;
  } while (0);

  return false;
}

// <parameter_list>
//  | <parameter_declaration>
//  | <parameter_list> , <parameter_declaration>
bool parser_t::parse_parameter_list() {
  state_t state = state_save();

  if (parse_parameter_declaration())
    return true;
  state_restore(state);

  #pragma message("<parameter_list> is left recursive!")

  if (parse_parameter_list() &&
      lexer_found(",") &&
      parse_parameter_declaration())
    return true;

  return false;
}

// <multiplicative_expression>
//  | <cast_expression>
//  | <multiplicative_expression> * <cast_expression>
//  | <multiplicative_expression> / <cast_expression>
//  | <multiplicative_expression> % <cast_expression>
bool parser_t::parse_multiplicative_expression() {
  state_t state = state_save();

  if (parse_cast_expression())
    return true;
  state_restore(state);

  #pragma message("<multiplicative_expression> is left recursive!")

  if (parse_multiplicative_expression() &&
      lexer_found("*") &&
      parse_cast_expression())
    return true;
  state_restore(state);

  #pragma message("<multiplicative_expression> is left recursive!")

  if (parse_multiplicative_expression() &&
      lexer_found("/") &&
      parse_cast_expression())
    return true;
  state_restore(state);

  #pragma message("<multiplicative_expression> is left recursive!")

  if (parse_multiplicative_expression() &&
      lexer_found("%") &&
      parse_cast_expression())
    return true;

  return false;
}

// <type_qualifier>
//  | const
//  | volatile
bool parser_t::parse_type_qualifier() {
  state_t state = state_save();

  if (lexer_found("const"))
    return true;
  state_restore(state);

  if (lexer_found("volatile"))
    return true;

  return false;
}

// <labeled_statement>
//  | <identifier> : <statement>
//  | case <constant_expression> : <statement>
//  | default : <statement>
bool parser_t::parse_labeled_statement() {
  state_t state = state_save();

  if (parse_identifier() &&
      lexer_found(":") &&
      parse_statement())
    return true;
  state_restore(state);

  if (lexer_found("case") &&
      parse_constant_expression() &&
      lexer_found(":") &&
      parse_statement())
    return true;
  state_restore(state);

  if (lexer_found("default") &&
      lexer_found(":") &&
      parse_statement())
    return true;

  return false;
}

// <abstract_declarator>
//  | <pointer>
//  | <pointer> <direct_abstract_declarator>
//  | <direct_abstract_declarator>
bool parser_t::parse_abstract_declarator() {
  state_t state = state_save();

  if (parse_pointer())
    return true;
  state_restore(state);

  if (parse_pointer() &&
      parse_direct_abstract_declarator())
    return true;
  state_restore(state);

  if (parse_direct_abstract_declarator())
    return true;

  return false;
}

// <enum_specifier>
//  | enum <identifier> { <enumerator_list> }
//  | enum { <enumerator_list> }
//  | enum <identifier>
bool parser_t::parse_enum_specifier() {
  state_t state = state_save();

  if (lexer_found("enum") &&
      parse_identifier() &&
      lexer_found("{") &&
      parse_enumerator_list() &&
      lexer_found("}"))
    return true;
  state_restore(state);

  if (lexer_found("enum") &&
      lexer_found("{") &&
      parse_enumerator_list() &&
      lexer_found("}"))
    return true;
  state_restore(state);

  if (lexer_found("enum") &&
      parse_identifier())
    return true;

  return false;
}

// <translation_unit>
//  | {<external_declaration>}*
bool parser_t::parse_translation_unit() {
  state_t state = state_save();

  do {
    while (parse_external_declaration());
    return true;
  } while (0);

  return false;
}

// <initializer_list>
//  | <initializer>
//  | <initializer_list> , <initializer>
bool parser_t::parse_initializer_list() {
  state_t state = state_save();

  if (parse_initializer())
    return true;
  state_restore(state);

  #pragma message("<initializer_list> is left recursive!")

  if (parse_initializer_list() &&
      lexer_found(",") &&
      parse_initializer())
    return true;

  return false;
}

// <conditional_expression>
//  | <logical_or_expression>
//  | <logical_or_expression> ? <expression> : <conditional_expression>
bool parser_t::parse_conditional_expression() {
  state_t state = state_save();

  if (parse_logical_or_expression())
    return true;
  state_restore(state);

  if (parse_logical_or_expression() &&
      lexer_found("?") &&
      parse_expression() &&
      lexer_found(":") &&
      parse_conditional_expression())
    return true;

  return false;
}

// <direct_abstract_declarator>
//  | ( <abstract_declarator> )
//  | {<direct_abstract_declarator>}? [ {<constant_expression>}? ]
//  | {<direct_abstract_declarator>}? ( {<parameter_type_list>}? )
bool parser_t::parse_direct_abstract_declarator() {
  state_t state = state_save();

  if (lexer_found("(") &&
      parse_abstract_declarator() &&
      lexer_found(")"))
    return true;
  state_restore(state);

  #pragma message("<direct_abstract_declarator> is left recursive!")

  do {
    {
      state_t temp = state_save();
      if (!parse_direct_abstract_declarator())
        state_restore(temp);
    }
    if (!lexer_found("["))
      break;
    {
      state_t temp = state_save();
      if (!parse_constant_expression())
        state_restore(temp);
    }
    if (!lexer_found("]"))
      break;
    return true;
  } while (0);
  state_restore(state);

  #pragma message("<direct_abstract_declarator> is left recursive!")

  do {
    {
      state_t temp = state_save();
      if (!parse_direct_abstract_declarator())
        state_restore(temp);
    }
    if (!lexer_found("("))
      break;
    {
      state_t temp = state_save();
      if (!parse_parameter_type_list())
        state_restore(temp);
    }
    if (!lexer_found(")"))
      break;
    return true;
  } while (0);

  return false;
}

// <expression>
//  | <assignment_expression>
//  | <expression> , <assignment_expression>
bool parser_t::parse_expression() {
  state_t state = state_save();

  if (parse_assignment_expression())
    return true;
  state_restore(state);

  #pragma message("<expression> is left recursive!")

  if (parse_expression() &&
      lexer_found(",") &&
      parse_assignment_expression())
    return true;

  return false;
}