I have received a lot of messages requesting the C BNF Grammar. Instead
of posting to each individual person, I decided to post it on the net.
The parser has one shift/reduce conflict on the if and if-else
constructs. You would also see a token called TYPEDEF_NAME in the
grammar which is actually an IDENTIFIER, but is named so in order to
prevent conflicts. You would have to handle it using start conditions or
some such thing in your lexical analyzer.
Hope this helps
======================CUT HERE===============================
#! /bin/sh
# This is a shell archive. Remove anything before this line, then unpack
# it by saving it into a file and typing "sh file". To overwrite existing
# files, type "sh file -c". You can also feed this as standard input via
# unshar, or by typing "sh <file", e.g.. If this archive is complete, you
# will see the following message at the end:
# "End of shell archive."
# Contents: c_parser.y
# Wrapped by chittamu at umvlsi.ecs.umass.edu on Fri Nov 17 11:16:20 1989
PATH=/bin:/usr/bin:/usr/ucb ; export PATH
if test -f c_parser.y -a "${1}" != "-c" ; then
echo shar: Will not over-write existing file \"c_parser.y\"
else
echo shar: Extracting \"c_parser.y\" \(31676 characters\)
sed "s/^X//" >c_parser.y <<'END_OF_c_parser.y'
X%right CONDITION COLON
X%left LOGICAL_OR
X%left LOGICAL_AND
X%left INCLUSIVE_OR
X%left EXCLUSIVE_OR
X%left AMPERSAND
X%left EQUAL NOT_EQUAL
X%left LEFT_SHIFT RIGHT_SHIFT
X%left PLUS MINUS
X%left STAR DIVIDE MODULUS
X%left INCREMENT DECREMENT
X%left DOT LEFT_PARENTHESIS LEFT_BRACKET
X%right LOGICAL_NEGATE ONES_COMPLEMENT
X%left LESS_THAN GREATER_THAN LESS_THAN_EQUAL GREATER_THAN_EQUAL
X%left COMMA
X%token SEMI_COLON
X%token LEFT_BRACE RIGHT_BRACE
X%token RIGHT_PARENTHESIS RIGHT_BRACKET
X%right ASSIGN MULTIPLY_ASSIGN DIVIDE_ASSIGN MODULUS_ASSIGN ADD_ASSIGN
X%right SUBTRACT_ASSIGN LEFT_SHIFT_ASSIGN RIGHT_SHIFT_ASSIGN
X%right AND_ASSIGN OR_ASSIGN XOR_ASSIGN
X%token MEMBER_OF_STRUCT
X%token AUTO_TOKEN BREAK_TOKEN
X%token CASE_TOKEN CHAR_TOKEN
X%token CHAR_TOKEN CONST_TOKEN
X%token CONTINUE_TOKEN DEFAULT_TOKEN
X%token DO_TOKEN DOUBLE_TOKEN
X%token ELSE_TOKEN ENUM_TOKEN
X%token ENUM_TOKEN EXTERN_TOKEN
X%token FLOAT_TOKEN FOR_TOKEN
X%token GOTO_TOKEN IF_TOKEN
X%token INT_TOKEN LONG_TOKEN
X%token REGISTER_TOKEN RETURN_TOKEN
X%token SHORT_TOKEN SIGNED_TOKEN
X%token SIZEOF_TOKEN STATIC_TOKEN
X%token STRUCT_TOKEN SWITCH_TOKEN
X%token TYPEDEF_TOKEN UNION_TOKEN
X%token UNSIGNED_TOKEN VOID_TOKEN
X%token VOLATILE_TOKEN WHILE_TOKEN
X
X%token IDENTIFIER
X%token TYPEDEF_NAME
X%token INTEGER_CONSTANT FLOATING_CONSTANT
X%token CHARACTER_CONSTANT ENUMERATION_CONSTANT
X%token STRING_LITERAL
X
X%start Translation_Unit
X
X%%
X
X
XTranslation_Unit : Translation_Unit
X External_Declaration
X | External_Declaration
X ;
X
XExternal_Declaration : Function_Definition
X | Declaration
X ;
X
XFunction_Definition : Declaration_Specifiers
X Declarator
X Declaration_List
X Compound_Statement
X | Declaration_Specifiers
X error
X Compound_Statement
X | Declarator
X Compound_Statement
X ;
X
XDeclaration : Declaration_Specifiers
X Init_Declarator_List
X SEMI_COLON
X | Declaration_Specifiers
X error
X SEMI_COLON
X | Declaration_Specifiers
X SEMI_COLON
X ;
X
XDeclaration_List : Declaration
X | Declaration_List
X Declaration
X ;
X
XDeclaration_Specifiers : Storage_Class_Specifier
X | Storage_Class_Specifier Declaration_Specifiers
X | Type_Specifier
X | Type_Specifier Declaration_Specifiers
X | Type_Qualifier
X | Type_Qualifier Declaration_Specifiers
X ;
X
XStorage_Class_Specifier : AUTO_TOKEN
X | REGISTER_TOKEN
X | STATIC_TOKEN
X | EXTERN_TOKEN
X | TYPEDEF_TOKEN
X ;
X
XType_Specifier : VOID_TOKEN
X | CHAR_TOKEN
X | SHORT_TOKEN
X | INT_TOKEN
X | LONG_TOKEN
X | FLOAT_TOKEN
X | DOUBLE_TOKEN
X | SIGNED_TOKEN
X | UNSIGNED_TOKEN
X | Struct_Or_Union_Specifier
X | Enum_Specifier
X | TYPEDEF_NAME
X ;
X
XType_Qualifier : CONST_TOKEN
X | VOLATILE_TOKEN
X ;
X
XStruct_Or_Union_Specifier : Struct_Or_Union
X IDENTIFIER
X | Struct_Or_Union
X Identifier_Opt
X Struct_Definition
X | Struct_Or_Union
X error
X Struct_Definition
X ;
X
XStruct_Definition : LEFT_BRACE
X Struct_Declaration_List
X RIGHT_BRACE
X | LEFT_BRACE
X error
X RIGHT_BRACE
X ;
X
XIdentifier_Opt : IDENTIFIER
X |
X ;
X
XStruct_Or_Union : STRUCT_TOKEN
X | UNION_TOKEN
X ;
X
XStruct_Declaration_List : Struct_Declaration_List
X Struct_Declaration
X | Struct_Declaration
X ;
X
XInit_Declarator_List : Init_Declarator
X | Init_Declarator_List
X COMMA
X Init_Declarator
X | error
X COMMA
X Init_Declarator
X ;
X
XInit_Declarator : Declarator
X | Declarator
X ASSIGN
X Initializer
X | error
X ASSIGN
X Initializer
X ;
X
XStruct_Declaration : Specifier_Qualifier_List
X Struct_Declarator_List
X SEMI_COLON
X | error
X SEMI_COLON
X ;
X
XSpecifier_Qualifier_List : Type_Specifier
X | Type_Specifier
X Specifier_Qualifier_List
X | Type_Qualifier
X | Type_Qualifier
X Specifier_Qualifier_List
X ;
X
XStruct_Declarator_List : Struct_Declarator
X | Struct_Declarator_List
X COMMA
X Struct_Declarator
X | error
X COMMA
X Struct_Declarator
X ;
X
XStruct_Declarator : Declarator
X | Declarator
X COLON
X Constant_Expression
X | error
X COLON
X Constant_Expression
X | COLON
X Constant_Expression
X ;
X
XEnum_Specifier : ENUM_TOKEN
X Identifier_Opt
X Enumerators_Definition
X | ENUM_TOKEN
X error
X Enumerators_Definition
X | ENUM_TOKEN
X IDENTIFIER
X ;
X
XEnumerators_Definition : LEFT_BRACE
X Enumerator_List
X RIGHT_BRACE
X | LEFT_BRACE
X error
X RIGHT_BRACE
X ;
X
XEnumerator_List : Enumerator
X | Enumerator_List
X COMMA
X Enumerator
X | error
X COMMA
X Enumerator
X ;
X
XEnumerator : IDENTIFIER
X | IDENTIFIER
X ASSIGN
X Constant_Expression
X ;
X
XDeclarator : Pointer
X Direct_Declarator
X | Direct_Declarator
X ;
X
XDirect_Declarator : IDENTIFIER
X | LEFT_PARENTHESIS
X Declarator
X RIGHT_PARENTHESIS
X | LEFT_PARENTHESIS
X error
X RIGHT_PARENTHESIS
X | Direct_Declarator
X LEFT_BRACKET
X Constant_Expression_Opt
X RIGHT_BRACKET
X | Direct_Declarator
X LEFT_BRACKET
X error
X RIGHT_BRACKET
X | Direct_Declarator
X LEFT_PARENTHESIS
X Parameter_Type_List
X RIGHT_PARENTHESIS
X | Direct_Declarator
X LEFT_PARENTHESIS
X Identifier_List_Opt
X RIGHT_PARENTHESIS
X | Direct_Declarator
X LEFT_PARENTHESIS
X error
X RIGHT_PARENTHESIS
X ;
X
XConstant_Expression_Opt : Constant_Expression
X |
X ;
X
XIdentifier_List_Opt : Identifier_List
X |
X ;
X
XPointer : STAR
X | STAR
X Pointer
X | STAR
X Type_Qualifier_List
X | STAR
X Type_Qualifier_List
X Pointer
X ;
X
XType_Qualifier_List : Type_Qualifier_List
X Type_Qualifier
X | Type_Qualifier
X ;
X
XParameter_Type_List : Parameter_List
X | Parameter_List
X COMMA
X DOT
X DOT
X DOT
X | error
X COMMA
X DOT
X DOT
X DOT
X ;
X
XParameter_List : Parameter_Declaration
X | Parameter_List
X COMMA
X Parameter_Declaration
X | error
X COMMA
X Parameter_Declaration
X ;
X
XParameter_Declaration : Declaration_Specifiers
X Declarator
X | Declaration_Specifiers
X Abstract_Declarator
X | Declaration_Specifiers
X ;
X
XIdentifier_List : IDENTIFIER
X | Identifier_List
X COMMA
X IDENTIFIER
X | error
X COMMA
X IDENTIFIER
X ;
X
XInitializer : Assignment_Expression
X | LEFT_BRACE
X Initializer_List
X RIGHT_BRACE
X | LEFT_BRACE
X error
X RIGHT_BRACE
X | LEFT_BRACE
X Initializer_List
X COMMA
X RIGHT_BRACE
X | LEFT_BRACE
X error
X COMMA
X RIGHT_BRACE
X ;
X
XInitializer_List : Initializer
X | Initializer_List
X COMMA
X Initializer
X ;
X
XType_Name : Specifier_Qualifier_List
X Abstract_Declarator
X | Specifier_Qualifier_List
X ;
X
XAbstract_Declarator : Pointer
X | Pointer
X Direct_Abstract_Declarator
X | Direct_Abstract_Declarator
X ;
X
XDirect_Abstract_Declarator : LEFT_PARENTHESIS
X Abstract_Declarator
X RIGHT_PARENTHESIS
X | LEFT_PARENTHESIS
X Parameter_Type_List_Opt
X RIGHT_PARENTHESIS
X/* | LEFT_PARENTHESIS
X error
X RIGHT_PARENTHESIS
X Causes 4 reduce/reduce conflicts
X*/ | LEFT_BRACKET
X Constant_Expression_Opt
X RIGHT_BRACKET
X | LEFT_BRACKET
X error
X RIGHT_BRACKET
X | Direct_Abstract_Declarator
X LEFT_BRACKET
X Constant_Expression_Opt
X RIGHT_BRACKET
X | Direct_Abstract_Declarator
X LEFT_BRACKET
X error
X RIGHT_BRACKET
X | Direct_Abstract_Declarator
X LEFT_PARENTHESIS
X Parameter_Type_List_Opt
X RIGHT_PARENTHESIS
X | Direct_Abstract_Declarator
X LEFT_PARENTHESIS
X error
X RIGHT_PARENTHESIS
X ;
X
XParameter_Type_List_Opt : Parameter_Type_List
X |
X ;
X
X
XStatement : Labeled_Statement
X | Expression_Statement
X | Compound_Statement
X | Selection_Statement
X | Iteration_Statement
X | Jump_Statement
X ;
X
XLabeled_Statement : IDENTIFIER
X COLON
X Statement
X | CASE_TOKEN
X Constant_Expression
X COLON
X Statement
X | CASE_TOKEN
X error
X COLON
X Statement
X | DEFAULT_TOKEN
X COLON
X Statement
X ;
X
XExpression_Statement : Expression_Opt
X SEMI_COLON
X | error
X SEMI_COLON
X ;
X
XExpression_Opt : Expression
X |
X ;
X
XCompound_Statement : LEFT_BRACE
X RIGHT_BRACE
X | LEFT_BRACE
X Declaration_List
X RIGHT_BRACE
X | LEFT_BRACE
X Statement_List
X RIGHT_BRACE
X | LEFT_BRACE
X Declaration_List
X Statement_List
X RIGHT_BRACE
X | LEFT_BRACE
X error
X RIGHT_BRACE
X ;
X
XStatement_List : Statement_List Statement
X | Statement
X ;
X
XSelection_Statement : If_Statement
X | If_Else_Statement
X | Switch_Statement
X ;
X
XIf_Statement : IF_TOKEN
X If_Condition
X Statement
X ;
X
XIf_Condition : LEFT_PARENTHESIS
X Expression
X RIGHT_PARENTHESIS
X | LEFT_PARENTHESIS
X error
X RIGHT_PARENTHESIS
X ;
X
XIf_Else_Statement : IF_TOKEN
X If_Condition
X IfStatement_Else
X Statement
X ;
X
XIfStatement_Else : Statement
X ELSE_TOKEN
X | error
X ELSE_TOKEN
X ;
X
XSwitch_Statement : SWITCH_TOKEN
X Switch_Expression
X Statement
X ;
X
XSwitch_Expression : LEFT_PARENTHESIS
X Expression
X RIGHT_PARENTHESIS
X | LEFT_PARENTHESIS
X error
X RIGHT_PARENTHESIS
X ;
X
XIteration_Statement : While_Statement
X | Do_While_Statement
X | For_Statement
X ;
X
XWhile_Statement : WHILE_TOKEN
X While_Condition
X Statement
X ;
X
XWhile_Condition : LEFT_PARENTHESIS
X Expression
X RIGHT_PARENTHESIS
X | LEFT_PARENTHESIS
X error
X RIGHT_PARENTHESIS
X ;
X
XDo_While_Statement : DO_TOKEN
X Do_Statement
X Do_Condition
X SEMI_COLON
X ;
X
XDo_Statement : Statement
X WHILE_TOKEN
X | error
X WHILE_TOKEN
X ;
X
XDo_Condition : LEFT_PARENTHESIS
X Expression
X RIGHT_PARENTHESIS
X | LEFT_PARENTHESIS
X error
X RIGHT_PARENTHESIS
X ;
X
XFor_Statement : FOR_TOKEN
X LEFT_PARENTHESIS
X First_For_Expression
X Second_For_Expression
X Third_For_Expression
X Statement
X ;
X
XFirst_For_Expression : Expression_Opt
X SEMI_COLON
X | error
X SEMI_COLON
X ;
X
XSecond_For_Expression : Expression_Opt
X SEMI_COLON
X | error
X SEMI_COLON
X ;
X
XThird_For_Expression : Expression_Opt
X RIGHT_PARENTHESIS
X | error
X RIGHT_PARENTHESIS
X ;
X
XJump_Statement : GOTO_TOKEN
X IDENTIFIER
X SEMI_COLON
X | CONTINUE_TOKEN
X SEMI_COLON
X | BREAK_TOKEN
X SEMI_COLON
X | RETURN_TOKEN
X Expression_Opt
X SEMI_COLON
X | RETURN_TOKEN
X error
X SEMI_COLON
X ;
X
XExpression : Assignment_Expression
X | Expression
X COMMA
X Assignment_Expression
X | error
X COMMA
X Assignment_Expression
X ;
X
XAssignment_Expression : Conditional_Expression
X | Unary_Expression
X Assignment_Operator
X Assignment_Expression
X ;
X
XAssignment_Operator : ASSIGN
X | MULTIPLY_ASSIGN
X | DIVIDE_ASSIGN
X | MODULUS_ASSIGN
X | ADD_ASSIGN
X | SUBTRACT_ASSIGN
X | LEFT_SHIFT_ASSIGN
X | RIGHT_SHIFT_ASSIGN
X | AND_ASSIGN
X | OR_ASSIGN
X | XOR_ASSIGN
X ;
X
XConditional_Expression : Logical_OR_Expression
X | First_Condition_Expression
X Second_Condition_Expression
X Conditional_Expression
X ;
X
XFirst_Condition_Expression : Logical_OR_Expression
X CONDITION
X | error
X CONDITION
X ;
X
XSecond_Condition_Expression : Expression
X COLON
X | error
X COLON
X ;
X
XConstant_Expression : Conditional_Expression
X ;
X
XLogical_OR_Expression : Logical_AND_Expression
X | Logical_OR_Expression
X LOGICAL_OR
X Logical_AND_Expression
X | error
X LOGICAL_OR
X Logical_AND_Expression
X ;
X
XLogical_AND_Expression : Inclusive_OR_Expression
X | Logical_AND_Expression
X LOGICAL_AND
X Inclusive_OR_Expression
X | error
X LOGICAL_AND
X Inclusive_OR_Expression
X ;
X
XInclusive_OR_Expression : Exclusive_OR_Expression
X | Inclusive_OR_Expression
X INCLUSIVE_OR
X Exclusive_OR_Expression
X | error
X INCLUSIVE_OR
X Exclusive_OR_Expression
X ;
X
XExclusive_OR_Expression : AND_Expression
X | Exclusive_OR_Expression
X EXCLUSIVE_OR
X AND_Expression
X | error
X EXCLUSIVE_OR
X AND_Expression
X ;
X
XAND_Expression : Equality_Expression
X | AND_Expression
X AMPERSAND
X Equality_Expression
X | error
X AMPERSAND
X Equality_Expression
X ;
X
XEquality_Expression : Relational_Expression
X | Equality_Expression
X EQUAL
X Relational_Expression
X | Equality_Expression
X NOT_EQUAL
X Relational_Expression
X | error
X Equality_Token
X Relational_Expression
X ;
X
XEquality_Token : EQUAL
X | NOT_EQUAL
X ;
X
XRelational_Expression : Shift_Expression
X | Relational_Expression
X LESS_THAN
X Shift_Expression
X | Relational_Expression
X GREATER_THAN
X Shift_Expression
X | Relational_Expression
X LESS_THAN_EQUAL
X Shift_Expression
X | Relational_Expression
X GREATER_THAN_EQUAL
X Shift_Expression
X | error
X Relational_Token
X Shift_Expression
X ;
X
XRelational_Token : LESS_THAN
X | GREATER_THAN
X | LESS_THAN_EQUAL
X | GREATER_THAN_EQUAL
X ;
X
XShift_Expression : Additive_Expression
X | Shift_Expression
X LEFT_SHIFT
X Additive_Expression
X | Shift_Expression
X RIGHT_SHIFT
X Additive_Expression
X | error
X Shift_Token
X Additive_Expression
X ;
X
XShift_Token : LEFT_SHIFT
X | RIGHT_SHIFT
X ;
X
XAdditive_Expression : Multiplicative_Expression
X | Additive_Expression
X PLUS
X Multiplicative_Expression
X | Additive_Expression
X MINUS
X Multiplicative_Expression
X | error
X Additive_Token
X Multiplicative_Expression
X ;
X
XAdditive_Token : PLUS
X | MINUS
X ;
X
XMultiplicative_Expression : Cast_Expression
X | Multiplicative_Expression
X STAR
X Cast_Expression
X | Multiplicative_Expression
X DIVIDE
X Cast_Expression
X | Multiplicative_Expression
X MODULUS
X Cast_Expression
X | error
X Multiplicative_Token
X Cast_Expression
X ;
X
XMultiplicative_Token : STAR
X | DIVIDE
X | MODULUS
X ;
X
XCast_Expression : Unary_Expression
X | LEFT_PARENTHESIS
X Type_Name
X RIGHT_PARENTHESIS
X Cast_Expression
X ;
X
XUnary_Expression : Postfix_Expression
X | INCREMENT
X Unary_Expression
X | DECREMENT
X Unary_Expression
X | Unary_Operator
X Cast_Expression
X | SIZEOF_TOKEN
X Unary_Expression
X | SIZEOF_TOKEN
X LEFT_PARENTHESIS
X Type_Name
X RIGHT_PARENTHESIS
X ;
X
XUnary_Operator : AMPERSAND
X | STAR
X | PLUS
X | MINUS
X | LOGICAL_NEGATE
X | ONES_COMPLEMENT
X ;
X
XPostfix_Expression : Primary_Expression
X | Postfix_Expression
X LEFT_BRACKET
X Expression
X RIGHT_BRACKET
X | Postfix_Expression
X LEFT_PARENTHESIS
X RIGHT_PARENTHESIS
X | Postfix_Expression
X LEFT_PARENTHESIS
X Argument_Expression_List
X RIGHT_PARENTHESIS
X | Postfix_Expression
X LEFT_PARENTHESIS
X error
X RIGHT_PARENTHESIS
X | Postfix_Expression
X DOT
X IDENTIFIER
X | Postfix_Expression
X MEMBER_OF_STRUCT
X IDENTIFIER
X | Postfix_Expression
X INCREMENT
X | Postfix_Expression
X DECREMENT
X ;
X
XPrimary_Expression : IDENTIFIER
X | Constant
X | STRING_LITERAL
X | LEFT_PARENTHESIS
X Expression
X RIGHT_PARENTHESIS
X | LEFT_PARENTHESIS
X error
X RIGHT_PARENTHESIS
X ;
X
XArgument_Expression_List : Assignment_Expression
X | Argument_Expression_List
X COMMA
X Assignment_Expression
X ;
X
XConstant : INTEGER_CONSTANT
X | CHARACTER_CONSTANT
X | FLOATING_CONSTANT
X | ENUMERATION_CONSTANT
X ;
X
X
X%%
END_OF_c_parser.y
if test 31676 -ne `wc -c <c_parser.y`; then
echo shar: \"c_parser.y\" unpacked with wrong size!
fi
# end of overwriting check
fi
echo shar: End of shell archive.
exit 0
--
-Satish.
chittamu at cs.umass.edu
--
The Theory of Objectivity: E = mc++