Here 'tis: ANSI C parser

Hi all,


I've written a prototype ANSI C parser, which follows at the end of
this posting. Look it over. Perhaps I should post it to some sources
group. I'm open to suggestions.


I am aware that there are other parsers floating around, but I think this
one has some features which may prove useful, or at least interesting,
in the area of recognizing typedef-names.


At least two other parsers which have been submitted previously had some
measure of typedef-name capability.


One of them I have not seen, but according to the author, who was gracious
enough to correspond with me, it requires that typedef-names and only
typedef-names begin with capital letters. As I intend to use this as the
basis of real utilities, that was obviously not sufficient. I might have
used that one as a starting-point, but I was unable to obtain it via ftp,
due to technical problems.


I obtained the other off of the net about a year or two ago. I was unable
to understand much of the code without great difficulty. Maybe the fault
was all within my addled brain (synapse-rot), but there it is. I felt I
could never trust the program.


So I undertook to write a parser prototype that was straight-forward enough to
read and understand, and which has the capacity for defining and re-defining
typedef-names in a scoped name-space. You may judge whether or not I
succeeded. In any case, it will require quite a bit more work to make
it into anything real. If you do build something out of it, please send
me a copy!


It could probably be sped up by obviating a lot of calls to
malloc and free, and by streamlining the name-space lookup, which currently
searches a stack of hash-tables. It has no error-recovery. I may work on that
at a later date, but it's really not nearly so important as it used to
be when you submitted a program to a sysop and got your syntax-error
messages back the next day. (Nowdays turn-around is so fast that when I
get a bunch of messages from a compiler, I usually just fix the first
one and then feed it back to the compiler right away without even reading
the others, because fixing one thing often clears up several error-messages.)


The program has not been tested very much at all. If you find mistakes,
please let me know!


My email address is sun!megatest!djones.






Happy parsing,




Dave
[Works OK for me once I changed the oldspeak index and rindex into
strchr and strrchr in the lexer. -John]


#! /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: DISCLAIMER README emalloc.c gram.y hash.c hash.h main.c
# makefile name-space.c parse scan.l types.h
# Wrapped by djones@prometheus on Mon Sep 9 19:39:45 1991
PATH=/bin:/usr/bin:/usr/ucb ; export PATH
if test -f DISCLAIMER -a "${1}" != "-c" ; then
    echo shar: Will not over-write existing file \"DISCLAIMER\"
else
echo shar: Extracting \"DISCLAIMER\" \(65 characters\)
sed "s/^X//" >DISCLAIMER <<'END_OF_DISCLAIMER'
X
XThis software may work, or it may not. Use it at your own risk.
END_OF_DISCLAIMER
if test 65 -ne `wc -c <DISCLAIMER`; then
        echo shar: \"DISCLAIMER\" unpacked with wrong size!
fi
# end of overwriting check
fi
if test -f README -a "${1}" != "-c" ; then
    echo shar: Will not over-write existing file \"README\"
else
echo shar: Extracting \"README\" \(7753 characters\)
sed "s/^X//" >README <<'END_OF_README'
X
XThis is a bare-bones prototype for an ANSI C parser.
X
XIt is based on _The C Programming Language,
XSecond Edition_, Kernighan and Ritchie, Printice Hall, 1988.
X
XThe program is relatively untested, but I think it may be instructive.
XUse it at your own risk.
X
XI would appreciate receiving any bug-fixes or improvements you may add.
XBut do me a favor: If you modify anything, please remove my name from all
Xthe files. No offense intended. You understand.
X
XThe program is designed to take as input the output of a C-preprocessor
Xsuch as cpp. That is to say, it does not handle #include, #ifdef, et cetera,
Xbut it DOES handle #line directives. It eats #pragma directives, but
Xdoes nothing with them.
X
XThis first version does not do any semantic analysis except as needed
Xto recognize typedef-names.
X
XCHANGES TO THE GRAMMAR
X
XSurprisingly few changes to the published grammar were needed to accommodate
Xthe recognition of typedef-names by the scanner, e.g.,
X
X1) the terminal-symbol TYPEDEF_NAME was introduced and the production
X reducing identifier to typedef_name was removed; The symbol identifier
X was replace by the terminal symbol IDENTIFIER.
X
X2) empty-productions for scanner feedback were introduced.
X
X3) The non-terminal symbols "function_declarator" and
X "direct_function_declarator" were added to the grammar, to replace
X "declarator" and its derived rules in extern function definitions.
X
X4) The non-terminal symbol type-specifier was split into two parts:
X
X actual_type_specifier: VOID | CHAR | INT | FLOAT | DOUBLE
X | TYPEDEF_NAME | struct_or_union_specifier | enum_specifier
X
X type_adjective: SHORT | LONG | SIGNED | UNSIGNED
X
X
XAdditionally, there seems to be a bug in the published grammar.
XClassic C compilers happily accept this file:
X
X foo();
X bar() { foo(); }
X
XTo make that work, I added the production "untyped_declaration", which
Xonly applies at the global level.
X
XFinally, one %prec directive was introduced to silence the
Xyacc warning about the well-known shift/reduce conflict on ELSE.
X
X
X
XCONCERNING TYPEDEF-NAMES AND SCANNER FEEDBACK
X
XThere are several kinds of name-spaces in C: a name-space for each
Xstruct or union, a separate name-space for labels, et cetera.
XThe scanner must be aware of the name-space which differentiates
Xtypedef-names from identifiers and enumeration-constants. In order for
Xthe scanner to make that distinction, a scoped symbol table is necessary.
XThis first version of the parser maintains only as much info there as is
Xnecessary to handle typedef-names.
X
XThe identifier/typedef-name distinction is only
Xuseful in contexts where the name-space applies. In other
Xcontexts the distinction may be inapplicable, or in cases where
Xtypedef-names are not legal, a semantic-analysis phase
Xmight potentially be able to generate a better error message if the parser
Xdid not flag a syntax error. In those contexts, we therefore use a
Xproduction that reduces TYPEDEF_NAMEs, ENUMERATION_CONSTANTS,
Xand IDENTIFIERs to the non-terminal symbol "identifier".
X
XEven with that production, it is still necessary to disable
Xrecognition of typedef-names by the scanner in some contexts. This
Xrequirement could be obviated only at the expense of approximately tripling
Xthe size of the grammar.
X
XThe scanner therefore has a boolean state-variable called "idents_only"
Xwhich specifies whether the scanner should return a token of type
XTYPEDEF_NAME or ENUMERATION_CONSTANT when applicable, or should only
Xreturn IDENTIFIER.
X
XProductions which interact with the name-space routines are prefixed
Xwith "NS_".
X
XThe production "NS_td" turns typedef-recognition on, and "NS_ntd" turns
Xit off. Notice that the state-change is necessarily effective only
XAFTER parsing the token which triggers it. Because original yacc uses
X"lazy lookahead", the routine lex_sync() is necessary to assure that
Xthe trigger-token is actually parsed before the scanner state-variable
Xidents_only is toggled.
X
XSee routine lex_sync() in file types.c.
X
XThe mechanism that toggles whether the scanner recognizes typedef_names
Xas such is a little convoluted. It would be nice if the "NS_td" and "NS_ntd"
Xnon-terminals could occur in matched sets within single production-rules.
XHowever, doing so would require that much of the grammar be duplicated.
XInstead, we will turn it off when an actual type-specifier is encountered in
Xa declaration, and turn it back on at the end of each production that
Xincludes a type-specifier, after any declarators to which the type-specifier
Xapplies. Here is the rationale:
X
XThe _Annotated Reference Manual_ specifies that typedef-names may be
Xredefined within an inner scope in declarations which contain
Xa "type-specifier" [sic].
X
X typedef char T1;
X typedef char T2;
X
X foo() {
X int T1, b; /* This redefines "T1" */
X static T2; /* But this does not re-define "T2". It is
X * "legal", but declares nothing.
X */
X }
X
X T1 ch; /* This is legal. */
X
XI interpret this to mean that to redefine a type-name, the declaration
Xmust contain something that actually names a type; the type must not
Xbe merely implied. The rationale is to be able to parse things with
Xonly a one-token lookahead. Therefore I think the following should
Xdeclare nothing, just as the "static T2" above declares nothing.
X
X typedef int T1;
X
X foo() {
X short T1; /* declares nothing. */
X short T1 i; /* declares i */
X }
X
XThere are four reserved words that can derive "type-specifier" in
Xthe original grammar which do not name a specific type:
XSHORT, LONG, SIGNED, UNSIGNED. I changed the grammar accordingly, calling
Xthose four "type-adjectives", and the others "actual-type-specifiers".
X
XIf I am wrong about this, somebody let me know.
X
XWe must turn typedef-recognition off in declarator-lists
Xand such when an actual-type-specifier is found, then back on again
Xafter any related declarator is finished.
X
XBy inspecting the grammar we find that there are five productions
Xwhich can derive a type-specifier indirectly:
X
X o function-definition
X o declaration
X o parameter-declaration
X o type-name
X o struct-declaration
X
XThose derive productions containing either "declaration-specifiers"
Xor "specifier-qualifier-list" which in turn derive "type-specifier".
X
XTypedef-recognition must be turned back on at or before the end of each of
Xthese five constructs, but only after any declarators that the constructs
Xapply to have been parsed. The production NS_td does the job.
X
XNow a note concerning the addition of the non-terminal symbol
X"function_declarator". A declarator for a function introduces a
Xnew scope in the name-space to accommodate its parameters. That
Xscope is destroyed either at the end of the declarator, or in the
Xcase of a function-definition, at the end of the compound-statement that
Xis the body of the definition. To distiguish the two cases, I added
Xthe non-terminal symbols "function_declarator" and
X"direct_function_declarator". They open the name-space scope, but do
Xnot close it as "declarator" and "direct_declarator" do. Furthermore,
XI did not duplicate the productions for non-function declarators such
Xas array-declarators. Therefore some illegal programs will now be flagged with
Xsyntax errors, where previously detection of the error would have been
Xpostponed until the semantic analysis phase. For example,
X
X int foo[3] { int i = 1; }
X
XUnder the original grammar, that was a "syntactically legal" program,
Xbecause "foo[3]" constituted a declarator, and the whole thing was therefore
Xa function_definition. Now, because "foo[3]" is not a function_declarator,
Xit produces a syntax error. If you think it was better the other way,
Xjust add the other kinds of declarators to the the rules for
Xfunction-declarator.
X
XHave fun, and good luck.
END_OF_README
if test 7753 -ne `wc -c <README`; then
        echo shar: \"README\" unpacked with wrong size!
fi
# end of overwriting check
fi
if test -f emalloc.c -a "${1}" != "-c" ; then
    echo shar: Will not over-write existing file \"emalloc.c\"
else
echo shar: Extracting \"emalloc.c\" \(351 characters\)
sed "s/^X//" >emalloc.c <<'END_OF_emalloc.c'
Xextern char* malloc();
X
X/* Malloc that complains and exits when memory is used up.
X */
Xchar* emalloc(size)
X int size;
X{
X static char msg[] = "C-parser out of memory\n";
X char* retval = malloc((unsigned)size);
X
X if(retval == 0) {
X /* fprintf might call malloc(), so... */
X write(2, msg, sizeof(msg));
X exit(-1);
X }
X return retval;
X}
END_OF_emalloc.c
if test 351 -ne `wc -c <emalloc.c`; then
        echo shar: \"emalloc.c\" unpacked with wrong size!
fi
# end of overwriting check
fi
if test -f gram.y -a "${1}" != "-c" ; then
    echo shar: Will not over-write existing file \"gram.y\"
else
echo shar: Extracting \"gram.y\" \(12878 characters\)
sed "s/^X//" >gram.y <<'END_OF_gram.y'
X%{
X# include "types.h"
Xtypedef char* yystype_def;
X# define YYSTYPE yystype_def
X%}
X
X%token BAD_TOKEN
X%token INTEGER_CONSTANT CHARACTER_CONSTANT FLOATING_CONSTANT
X ENUMERATION_CONSTANT IDENTIFIER STRING
X
X%token SIZEOF
X%token PTR_OP INC_OP DEC_OP LEFT_OP RIGHT_OP LE_OP GE_OP EQ_OP NE_OP
X%token AND_OP OR_OP MUL_ASSIGN DIV_ASSIGN MOD_ASSIGN ADD_ASSIGN
X%token SUB_ASSIGN LEFT_ASSIGN RIGHT_ASSIGN AND_ASSIGN
X%token XOR_ASSIGN OR_ASSIGN TYPEDEF_NAME
X
X%token TYPEDEF EXTERN STATIC AUTO REGISTER
X%token CHAR SHORT INT LONG SIGNED UNSIGNED FLOAT DOUBLE CONST VOLATILE VOID
X%token STRUCT UNION ENUM ELIPSIS
X
X%token CASE DEFAULT IF SWITCH WHILE DO FOR GOTO CONTINUE BREAK RETURN
X
X%left THEN
X%left ELSE
X
X%start translation_unit
X%%
X
X/****************************************************************
X ********* Name-Space and scanner-feedback productions **********
X ****************************************************************/
X
X/* The occurance of a type_specifier in the input turns off
X * scanner-recognition of typedef-names as such, so that they can
X * be re-defined within a declarator-list. The switch is called
X * "name_space_types".
X *
X * The call to lex_sync() assures that the switch gets toggled after
X * the next token is pre-fetched as a lookahead.
X */
X
XNS_ntd : { lex_sync(); ntd(); }
X ;
X
X/* Once the declarators (if any) are parsed, the scanner is returned
X * to the state where typedef-names are recognized.
X */
XNS_td : { lex_sync(); td(); }
X ;
X
X/* NS_scope_push creates a new scope in the id/typedef/enum-const
X * name-space. New levels are created by function-declarators
X * and are created and destroyed by compound-statements.
X * Thus, every occurance of a function-declarator must be
X * followed, at the end of the scope of that declarator,
X * by an NS_scope_pop.
X */
XNS_scope_push : { scope_push(); td(); }
X ;
XNS_scope_pop : { scope_pop(); }
X ;
X
X/* NS_struct_push creates a new name-space for a struct or union
X * NS_struct_pop finishes one.
X */
XNS_struct_push : { struct_push(); td(); }
X;
X
XNS_struct_pop: { struct_pop(); }
X;
X
XNS_id: { new_declaration(name_space_decl); }
X;
X
X/* Begin a new declaration of a parameter */
XNS_new_parm: { new_declaration(name_space_decl); }
X;
X
X/* Remember that declarators while define typedef-names. */
XNS_is_typedef: { set_typedef(); }
X;
X
X/* Finish a direct-declarator */
XNS_direct_decl: { direct_declarator(); }
X;
X
X/* Finish a pointer-declarator */
XNS_ptr_decl: { pointer_declarator(); }
X;
X
X/* The scanner must be aware of the name-space which
X * differentiates typedef-names from identifiers. But the
X * distinction is only useful within limited scopes. In other
X * scopes the distinction may be invalid, or in cases where
X * typedef-names are not legal, the semantic-analysis phase
X * may be able to generate a better error message if the parser
X * does not flag a syntax error. We therefore use the following
X * production...
X */
X
Xidentifier
X : NS_ntd TYPEDEF_NAME NS_td
X | IDENTIFIER
X | ENUMERATION_CONSTANT
X ;
X
X/************************************************************
X ***************** The C grammar per se. *******************
X ************************************************************/
X
X/*
X * What follows is based on the gammar in _The C Programming Language_,
X * Kernighan & Ritchie, Prentice Hall 1988. See the README file.
X */
X
Xtranslation_unit
X : external_declaration
X | translation_unit external_declaration
X ;
X
Xexternal_declaration
X : NS_id function_definition
X | NS_id declaration
X | NS_id untyped_declaration
X ;
X
Xfunction_definition
X : function_declarator
X compound_statement
X NS_scope_pop
X
X | function_declarator
X declaration_list
X compound_statement
X NS_scope_pop
X
X | declaration_specifiers
X function_declarator NS_td
X compound_statement
X NS_scope_pop
X
X | declaration_specifiers
X function_declarator NS_td
X declaration_list
X compound_statement
X NS_scope_pop
X ;
X
Xdeclaration
X : declaration_specifiers NS_td ';'
X | declaration_specifiers init_declarator_list NS_td ';'
X ;
X
Xuntyped_declaration
X : init_declarator_list ';'
X ;
X
Xdeclaration_list
X : declaration
X | declaration_list declaration
X ;
X
Xdeclaration_specifiers
X : 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
X : NS_is_typedef TYPEDEF
X | EXTERN
X | STATIC
X | AUTO
X | REGISTER
X ;
X
X/* Once an actual type-specifier is seen, it acts as a "trigger" to
X * turn typedef-recognition off while scanning declarators, etc.
X */
Xtype_specifier
X : NS_ntd actual_type_specifier
X | type_adjective
X ;
X
Xactual_type_specifier
X : VOID
X | CHAR
X | INT
X | FLOAT
X | DOUBLE
X | TYPEDEF_NAME
X | struct_or_union_specifier
X | enum_specifier
X ;
X
Xtype_adjective
X : SHORT
X | LONG
X | SIGNED
X | UNSIGNED
X ;
X
Xtype_qualifier
X : CONST
X | VOLATILE
X ;
X
Xstruct_or_union_specifier
X : struct_or_union NS_struct_push
X '{' struct_declaration_list NS_struct_pop '}'
X | struct_or_union identifier NS_struct_push
X '{' struct_declaration_list NS_struct_pop '}'
X | struct_or_union identifier
X ;
X
Xstruct_or_union
X : STRUCT
X | UNION
X ;
X
Xstruct_declaration_list
X : struct_declaration
X | struct_declaration_list struct_declaration
X ;
X
Xinit_declarator_list
X : init_declarator
X | init_declarator_list ',' init_declarator
X ;
X
Xinit_declarator
X : declarator
X | declarator NS_td '=' initializer NS_ntd
X ;
X
Xstruct_declaration
X : { new_declaration(struct_decl); }
X specifier_qualifier_list struct_declarator_list NS_td ';'
X ;
X
Xspecifier_qualifier_list
X : type_specifier
X | type_specifier specifier_qualifier_list
X | type_qualifier
X | type_qualifier specifier_qualifier_list
X ;
X
Xstruct_declarator_list
X : struct_declarator
X | struct_declarator_list ',' struct_declarator
X ;
X
Xstruct_declarator
X : declarator
X | ':' constant_expression
X | declarator ':' constant_expression
X ;
X
Xenum_specifier
X : ENUM '{' enumerator_list '}'
X | ENUM identifier '{' enumerator_list '}'
X | ENUM identifier
X ;
X
Xenumerator_list
X : enumerator
X | enumerator_list ',' enumerator
X ;
X
Xenumerator
X : IDENTIFIER
X | IDENTIFIER '=' constant_expression
X ;
X
Xdeclarator
X : direct_declarator NS_direct_decl
X | pointer direct_declarator NS_ptr_decl
X ;
X
Xdirect_declarator
X : IDENTIFIER { declarator_id($$); }
X | '(' declarator ')'
X | direct_declarator '[' ']'
X | direct_declarator '[' constant_expression ']'
X | direct_declarator NS_scope_push '(' parameter_type_list ')'
X NS_scope_pop
X | direct_declarator NS_scope_push '(' ')' NS_scope_pop
X | direct_declarator NS_scope_push '(' identifier_list ')' NS_scope_pop
X ;
X
Xfunction_declarator
X : direct_function_declarator NS_direct_decl
X | pointer direct_function_declarator NS_ptr_decl
X ;
X
Xdirect_function_declarator
X : direct_declarator NS_scope_push '(' parameter_type_list ')'
X | direct_declarator NS_scope_push '(' ')'
X | direct_declarator NS_scope_push '(' identifier_list ')'
X ;
X
Xpointer
X : '*'
X | '*' type_qualifier_list
X | '*' pointer
X | '*' type_qualifier_list pointer
X ;
X
Xtype_qualifier_list
X : type_qualifier
X | type_qualifier_list type_qualifier
X ;
X
Xparameter_type_list
X : parameter_list
X | parameter_list ',' ELIPSIS
X ;
X
Xparameter_list
X : parameter_declaration
X | parameter_list ',' parameter_declaration
X ;
X
Xparameter_declaration
X : NS_new_parm declaration_specifiers declarator NS_td
X | NS_new_parm declaration_specifiers NS_td
X | NS_new_parm declaration_specifiers abstract_declarator NS_td
X ;
X
Xidentifier_list
X : IDENTIFIER
X | identifier_list ',' IDENTIFIER
X ;
X
Xinitializer
X : assignment_expression
X | '{' initializer_list '}'
X | '{' initializer_list ',' '}'
X ;
X
Xinitializer_list
X : initializer
X | initializer_list ',' initializer
X ;
X
Xtype_name
X : specifier_qualifier_list NS_td
X | specifier_qualifier_list NS_td abstract_declarator
X ;
X
Xabstract_declarator
X : pointer
X | direct_abstract_declarator
X | pointer direct_abstract_declarator
X ;
X
Xdirect_abstract_declarator
X : '(' abstract_declarator ')'
X | '[' ']'
X | '[' constant_expression ']'
X | direct_abstract_declarator '[' ']'
X | direct_abstract_declarator '[' constant_expression ']'
X | '(' ')'
X | '(' parameter_type_list ')'
X | direct_abstract_declarator '(' ')'
X | direct_abstract_declarator '(' parameter_type_list ')'
X ;
X
Xstatement
X : labeled_statement
X | compound_statement
X | expression_statement
X | selection_statement
X | iteration_statement
X | jump_statement
X ;
X
Xlabeled_statement
X : identifier ':' statement
X | CASE constant_expression ':' statement
X | DEFAULT ':' statement
X ;
X
Xexpression_statement
X : ';'
X | expression ';'
X ;
X
Xcompound_statement
X : NS_scope_push '{' NS_scope_pop '}'
X | NS_scope_push '{' statement_list NS_scope_pop '}'
X | NS_scope_push '{' declaration_list NS_scope_pop '}'
X | NS_scope_push '{' declaration_list statement_list NS_scope_pop '}'
X ;
X
Xstatement_list
X : statement
X | statement_list statement
X ;
X
Xselection_statement
X : IF '(' expression ')' statement %prec THEN
X | IF '(' expression ')' statement ELSE statement
X | SWITCH '(' expression ')' statement
X ;
X
Xiteration_statement
X : WHILE '(' expression ')' statement
X | DO statement WHILE '(' expression ')' ';'
X | FOR '(' ';' ';' ')' statement
X | FOR '(' ';' ';' expression ')' statement
X | FOR '(' ';' expression ';' ')' statement
X | FOR '(' ';' expression ';' expression ')' statement
X | FOR '(' expression ';' ';' ')' statement
X | FOR '(' expression ';' ';' expression ')' statement
X | FOR '(' expression ';' expression ';' ')' statement
X | FOR '(' expression ';' expression ';' expression ')' statement
X ;
X
Xjump_statement
X : GOTO identifier ';'
X | CONTINUE ';'
X | BREAK ';'
X | RETURN ';'
X | RETURN expression ';'
X ;
X
Xexpression
X : assignment_expression
X | expression ',' assignment_expression
X ;
X
X
Xassignment_expression
X : conditional_expression
X | unary_expression assignment_operator assignment_expression
X ;
X
Xassignment_operator
X : '=' | MUL_ASSIGN | DIV_ASSIGN | MOD_ASSIGN | ADD_ASSIGN | SUB_ASSIGN
X | LEFT_ASSIGN | RIGHT_ASSIGN | AND_ASSIGN | XOR_ASSIGN | OR_ASSIGN
X ;
X
X
Xconditional_expression
X : logical_or_expression
X | logical_or_expression '?' expression ':' conditional_expression
X ;
X
X
Xconstant_expression
X : conditional_expression
X ;
X
X
Xlogical_or_expression
X : logical_and_expression
X | logical_or_expression OR_OP logical_and_expression
X ;
X
Xlogical_and_expression
X : inclusive_or_expression
X | logical_and_expression AND_OP inclusive_or_expression
X ;
X
Xinclusive_or_expression
X : exclusive_or_expression
X | inclusive_or_expression '|' exclusive_or_expression
X ;
X
Xexclusive_or_expression
X : and_expression
X | exclusive_or_expression '^' and_expression
X ;
X
Xand_expression
X : equality_expression
X | and_expression '&' equality_expression
X ;
X
Xequality_expression
X : relational_expression
X | equality_expression EQ_OP relational_expression
X | equality_expression NE_OP relational_expression
X ;
X
Xrelational_expression
X : shift_expression
X | relational_expression '<' shift_expression
X | relational_expression '>' shift_expression
X | relational_expression LE_OP shift_expression
X | relational_expression GE_OP shift_expression
X ;
X
Xshift_expression
X : additive_expression
X | shift_expression LEFT_OP additive_expression
X | shift_expression RIGHT_OP additive_expression
X ;
X
Xadditive_expression
X : multiplicative_expression
X | additive_expression '+' multiplicative_expression
X | additive_expression '-' multiplicative_expression
X ;
X
Xmultiplicative_expression
X : cast_expression
X | multiplicative_expression '*' cast_expression
X | multiplicative_expression '/' cast_expression
X | multiplicative_expression '%' cast_expression
X ;
X
Xcast_expression
X : unary_expression
X | '(' type_name ')' cast_expression
X ;
X
X
Xunary_expression
X : postfix_expression
X | INC_OP unary_expression
X | DEC_OP unary_expression
X | unary_operator cast_expression
X | SIZEOF unary_expression
X | SIZEOF '(' type_name ')'
X ;
X
X
Xunary_operator
X : '&' | '*' | '+' | '-' | '~' | '!'
X ;
X
X
Xpostfix_expression
X : primary_expression
X | postfix_expression '[' expression ']'
X | postfix_expression '(' ')'
X | postfix_expression '(' argument_expression_list ')'
X | postfix_expression '.' identifier
X | postfix_expression PTR_OP identifier
X | postfix_expression INC_OP
X | postfix_expression DEC_OP
X ;
X
Xprimary_expression
X : IDENTIFIER
X | constant
X | STRING
X | '(' expression ')'
X ;
X
Xargument_expression_list
X : assignment_expression
X | argument_expression_list ',' assignment_expression
X ;
X
Xconstant
X : INTEGER_CONSTANT
X | CHARACTER_CONSTANT
X | FLOATING_CONSTANT
X | ENUMERATION_CONSTANT
X ;
X
X
X%%
END_OF_gram.y
if test 12878 -ne `wc -c <gram.y`; then
        echo shar: \"gram.y\" unpacked with wrong size!
fi
# end of overwriting check
fi
if test -f hash.c -a "${1}" != "-c" ; then
    echo shar: Will not over-write existing file \"hash.c\"
else
echo shar: Extracting \"hash.c\" \(4337 characters\)
sed "s/^X//" >hash.c <<'END_OF_hash.c'
X/*
X * These are hash-routines from a standard library, stripped down
X * and specialized. The search loops look like they might spin
X * forever, but they proveably terminate due to an algebraic property
X * of the REHASH function. I don't want to go into it now. Trust me.
X */
X
X#include "types.h"
X#include "hash.h"
X
Xextern char* emalloc();
X
Xstatic str_hash();
Xstatic declaration **new_table();
Xstatic int round_up_to_pwr2();
X
Xhash_init_sized(obj, initial_table_size)
X hash* obj;
X{
X if(initial_table_size < 4) initial_table_size = 4;
X obj->size = round_up_to_pwr2(initial_table_size);
X obj->num_entries = 0;
X obj->max_entries = obj->size/2 - 1;
X obj->mask = obj->size - 1;
X obj->hash_table = new_table(obj->size);
X}
X
Xhash_clean(obj)
X hash* obj;
X{
X int i;
X declaration **ht = obj->hash_table;
X
X for(i = 0; i < obj->size; i++) {
X declaration *dc = ht[i];
X if(dc) {
X free((char*)dc->name);
X free((char*)dc);
X }
X }
X
X free((char*)obj->hash_table);
X}
X
X
Xstatic void hash_overflow();
X
X#define HASH(cont) ((str_hash(cont)) & obj->mask )
X#define REHASH(num) (((((num)+1)*3) & obj->mask) )
X
X/* Put a new entry into the table. If there was previously an
X * equivalent entry in the table, return it.
X * If there was not, return NULL.
X */
X
Xdeclaration*
Xhash_put(obj, entry )
X hash* obj;
X declaration *entry;
X{
X
X int bucket_number;
X declaration **bucket;
X
X bucket_number = HASH(entry->name);
X
X while(1) {
X
X bucket = obj->hash_table + bucket_number;
X
X if ( *bucket == (declaration*)0 ) {
X *bucket = entry;
X obj->num_entries++;
X if ( obj->num_entries > obj->max_entries )
X hash_overflow(obj);
X return (declaration*)0; /* <======== added new entry */
X }
X
X if ( strcmp( entry->name, (*bucket)->name ) != 0) {
X bucket_number = REHASH(bucket_number);
X continue; /* <====== search some more (collision) */
X }
X
X /* Found old declaration. Replace. */
X {
X declaration *old = *bucket;
X *bucket = entry;
X return old; /* <============== replaced entry */
X }
X
X }
X
X}
X
X
X/* Find an equivalent entry. If there is none, return NULL.
X * Do not change the table.
X */
X
Xdeclaration*
Xhash_get(obj, name)
X hash* obj;
X char* name;
X{
X
X int bucket_number;
X declaration** bucket;
X
X bucket_number = HASH(name);
X
X while(1) {
X bucket = obj->hash_table + bucket_number;
X
X if ( *bucket == (declaration*)0 ) {
X return (declaration*)0; /* <====== entry not found */
X }
X
X if ( strcmp( name, (*bucket)->name) != 0) {
X bucket_number = REHASH(bucket_number);
X continue; /* <====== search some more (collision) */
X }
X
X return *bucket; /* <====== found old declaration */
X }
X
X}
X
X
X/* private routine doubles the size of the table.
X */
X
Xstatic void
Xhash_overflow(obj)
X hash* obj;
X{
X declaration** old_hash = obj->hash_table;
X int old_size = obj->size;
X int recno;
X
X obj->max_entries = obj->size - 1;
X obj->size= obj->size * 2;
X obj->mask= obj->size - 1;
X obj->hash_table = new_table(obj->size);
X
X /* Take everything that was in the old table, and put it
X ** into the new one.
X */
X
X for (recno = 0; recno < old_size; recno++) {
X declaration **mem = old_hash + recno;
X if ( *mem != 0 ) {
X int bucket_number = HASH((*mem)->name);
X while(1) {
X declaration** bucket = obj->hash_table + bucket_number;
X if ( *bucket == 0 ) {
X *bucket = *mem;
X break; /* <==== copied it */
X }
X
X /* search some more */
X bucket_number = REHASH(bucket_number);
X
X }
X }
X }
X
X free((char*)old_hash);
X
X}
X
X
X
X/* private routine creates new hash-table.
X */
X
Xstatic
Xdeclaration**
Xnew_table(size)
X{
X
X declaration** table =
X (declaration**)emalloc(sizeof(declaration)*size);
X declaration** cursor = table;
X declaration** end = table+size;
X while(cursor < end) *cursor ++ = 0;
X
X return table;
X}
X
X
X
Xstatic int
Xround_up_to_pwr2(initial_table_size)
X int initial_table_size;
X{
X int size = 4; /* algorithm does not work with 1 or 2 */
X
X while(size < initial_table_size ) {
X size*= 2;
X }
X return size;
X}
X
X
X
Xstatic
Xstr_hash(str)
X char *str;
X{
X int retval = 0;
X while(*str) retval += retval + (unsigned char)(*str++);
X return retval;
X}
X
END_OF_hash.c
if test 4337 -ne `wc -c <hash.c`; then
        echo shar: \"hash.c\" unpacked with wrong size!
fi
# end of overwriting check
fi
if test -f hash.h -a "${1}" != "-c" ; then
    echo shar: Will not over-write existing file \"hash.h\"
else
echo shar: Extracting \"hash.h\" \(143 characters\)
sed "s/^X//" >hash.h <<'END_OF_hash.h'
X
Xtypedef struct
X{
X declaration **hash_table;
X int size;
X int max_entries;
X int mask;
X int num_entries;
X}hash;
X
Xdeclaration*
Xhash_get();
END_OF_hash.h
if test 143 -ne `wc -c <hash.h`; then
        echo shar: \"hash.h\" unpacked with wrong size!
fi
# end of overwriting check
fi
if test -f main.c -a "${1}" != "-c" ; then
    echo shar: Will not over-write existing file \"main.c\"
else
echo shar: Extracting \"main.c\" \(496 characters\)
sed "s/^X//" >main.c <<'END_OF_main.c'
X#include <stdio.h>
X
Xint errors = 0;
X
Xmain(argc, argv)
X char** argv;
X{
X argc--; argv++; /* skip the progam-name */
X
X if(argc == 0) {
X name_space_init();
X yyparse(); /* parse stdin */
X }
X else /* parse all files named in the command-line */
X for(; argc; argc--, argv++) {
X
X FILE* fp = freopen(*argv, "r", stdin);
X
X if(fp == 0) {
X perror(*argv);
X errors++;
X }
X else {
X name_space_init();
X yyparse();
X }
X
X }
X
X return -(errors);
X}
END_OF_main.c
if test 496 -ne `wc -c <main.c`; then
        echo shar: \"main.c\" unpacked with wrong size!
fi
# end of overwriting check
fi
if test -f makefile -a "${1}" != "-c" ; then
    echo shar: Will not over-write existing file \"makefile\"
else
echo shar: Extracting \"makefile\" \(319 characters\)
sed "s/^X//" >makefile <<'END_OF_makefile'
XCFLAGS = -O
XLEX = flex -f
X# LEX = lex
XYACC = yacc -vd
X
XOBJS = lex.yy.o \
X y.tab.o \
X main.o \
X hash.o \
X emalloc.o \
X name-space.o
X
Xparse-backend: $(OBJS)
X $(CC) -g $(OBJS) -o parse-backend
X
Xy.tab.o: y.tab.c y.tab.h
X
Xy.tab.c y.tab.h: gram.y
X $(YACC) gram.y
X
Xlex.yy.o: lex.yy.c y.tab.h
X
Xlex.yy.c: scan.l
X $(LEX) scan.l
END_OF_makefile
if test 319 -ne `wc -c <makefile`; then
        echo shar: \"makefile\" unpacked with wrong size!
fi
# end of overwriting check
fi
if test -f name-space.c -a "${1}" != "-c" ; then
    echo shar: Will not over-write existing file \"name-space.c\"
else
echo shar: Extracting \"name-space.c\" \(4417 characters\)
sed "s/^X//" >name-space.c <<'END_OF_name-space.c'
X/*
X * This code deals with the C name-space that distinguishes identifiers,
X * enumeration-constants, and typedef-names.
X *
X * It implements just enough of the name-space to distinguish
X * identifiers from typedef-names. With a few more keystrokes, it could
X * also identify enumeration constants, which it does not do just now.
X * There is no code to determine whether a name is doubly defined within
X * a scope, or whether a declaration in an old-style function definition
X * names something in the parameter-list, et cetera.. In other words,
X * it is a "starter kit".
X */
X
X#include "types.h"
X#include "hash.h"
X#include <stdio.h>
X#include "y.tab.h"
X
X
X#define MAX_NUM_LEVELS 16
X#define MAX_LEVEL (MAX_NUM_LEVELS-1)
X
Xint scope_level = 0; /* Counts the number of scopes within the name-space */
Xint decl_level = 0; /* For nested struct-declarations */
X
Xint idents_only[MAX_NUM_LEVELS]; /* If one, this name-space is not
X * applicable. Always return IDENTIFIER
X * in that case.
X */
X
Xdeclaration decls[MAX_NUM_LEVELS]; /* Declarations in progress. */
Xhash tables[MAX_NUM_LEVELS]; /* Hash tables, one for each scope */
X
Xextern declaration *hash_put();
Xextern char* emalloc();
X
Xname_space_init()
X{
X while(scope_level > 0) {
X scope_pop();
X }
X
X decl_level = 0;
X
X /* Create the name-space for level zero, with an arbitrary
X * initial table size. It's kind of big, because #include-files
X * usually generate a lot of names.
X */
X hash_init_sized(&tables[scope_level], 512);
X}
X
X/*
X * Create a new scope in the identifier/typedef/enum-const
X * name-space.
X */
Xscope_push()
X{
X scope_level++;
X
X if(scope_level > MAX_LEVEL) {
X fprintf(stderr, "C-parser: Nesting is too deep.\n");
X exit(-1);
X }
X
X /* Initial size is again arbitrary. */
X hash_init_sized(&tables[scope_level], 32 );
X
X}
X
X/*
X * Destroy an old scope in the identifier/typedef/enum-const
X * name-space.
X */
Xscope_pop()
X{
X
X hash_clean(&tables[scope_level]);
X scope_level--;
X}
X
X/*
X * Create a new name-space for a structure declaration.
X */
Xstruct_push()
X{
X decl_level++;
X}
X
X/*
X * Finish a structure declaration
X */
Xstruct_pop()
X{
X decl_level--;
X}
X
X/*
X * Look for the name in the name-space, beginning with
X * the outermost scope.
X */
Xdeclaration*
Xfind_decl(name)
X char *name;
X{
X int look;
X
X for(look = scope_level; look >= 0; look--) {
X
X declaration *find;
X
X if((find = hash_get(&tables[look], name)) != 0)
X return find;
X
X }
X
X return 0;
X}
X
X/*
X * Within this name-space, each defined name has a type,
X * either IDENTIFIER, ENUMERATION_CONSTANT, or TYPEDEF_NAME.
X */
Xtype_of_name(name)
X char* name;
X{
X
X declaration *find = find_decl(name);
X
X if(!find)
X return IDENTIFIER;
X else
X switch(find->type) {
X case enum_const:
X return ENUMERATION_CONSTANT;
X case typename:
X return TYPEDEF_NAME;
X default:
X return IDENTIFIER;
X }
X}
X
X/*
X * Remember the name of the declarator being defined.
X */
Xdeclarator_id(name)
X char* name;
X{
X declaration *decl = &decls[decl_level];
X decl->name = name;
X}
X
X/*
X * Begin a new declaration with default values.
X */
Xnew_declaration(type)
X enum decl_type type;
X{
X declaration *decl = &decls[decl_level];
X decl->decl_type = type;
X decl->type = identifier;
X decl->scope_level = scope_level;
X decl->name = 0;
X}
X
X/*
X * Remember that this declaration defines a typename,
X * not an identifier.
X */
Xset_typedef()
X{
X decls[decl_level].type = typename;
X}
X
X/*
X * Put a name into the current scope.
X */
Xstatic
Xput_name()
X{
X declaration *decl = &decls[decl_level];
X declaration *copy = (declaration*)emalloc(sizeof(declaration));
X
X *copy = *decl;
X
X if(decl->decl_type == struct_decl) {
X /* Should export the decl to the structure's name-space.
X * ... for now, just boot it.
X */
X free((char*)copy);
X return;
X }
X
X {
X declaration* prev = hash_put(&tables[scope_level], copy);
X /*
X * If the declaration was already there, we should do
X * the right thing... for now, to heck with it.
X */
X
X }
X}
X
X/* finish the declarator */
Xdirect_declarator()
X{
X put_name();
X}
X
X/* finish the declarator */
Xpointer_declarator()
X{
X put_name();
X}
X
X
X/*
X * Turn on typedef_name (and enum-constant) recognition)
X */
Xtd()
X{
X idents_only[decl_level] = 0;
X}
X
X/*
X * Turn it off.
X */
Xntd()
X{
X idents_only[decl_level] = 1;
X}
END_OF_name-space.c
if test 4417 -ne `wc -c <name-space.c`; then
        echo shar: \"name-space.c\" unpacked with wrong size!
fi
# end of overwriting check
fi
if test -f parse -a "${1}" != "-c" ; then
    echo shar: Will not over-write existing file \"parse\"
else
echo shar: Extracting \"parse\" \(51 characters\)
sed "s/^X//" >parse <<'END_OF_parse'
X
X/usr/lib/cpp $* | /u/djones/src/C-3/parse-backend
END_OF_parse
if test 51 -ne `wc -c <parse`; then
        echo shar: \"parse\" unpacked with wrong size!
fi
chmod +x parse
# end of overwriting check
fi
if test -f scan.l -a "${1}" != "-c" ; then
    echo shar: Will not over-write existing file \"scan.l\"
else
echo shar: Extracting \"scan.l\" \(6118 characters\)
sed "s/^X//" >scan.l <<'END_OF_scan.l'
XO [0-7]
XD [0-9]
XL [a-zA-Z_]
XH [a-fA-F0-9]
XE [Ee][+-]?{D}+
XFS (f|F|l|L)
XIS (u|U|l|L)
XW [ \t\f]*
XLIT \"(\\.|[^\\"])*\"
X
X%{
X#include <stdio.h>
X#include "y.tab.h"
Xextern char* yylval;
Xint line_num = 1;
Xextern int idents_only[];
X%}
X
X%%
X
X"/*" { comment(); }
X
X^{W}#{W}"line"?{W}{D}+{W}{LIT}.*\n { line_directive(); }
X^{W}#{W}"line"?{W}{D}+[^"]*\n { line_directive(); }
X^{W}#{W}"pragma".*\n { /* ignore pragma */ }
X
X\n { line_num++; }
X[ \t\f]+ { }
X
X"auto" { return(AUTO); }
X"break" { return(BREAK); }
X"case" { return(CASE); }
X"char" { return(CHAR); }
X"const" { return(CONST); }
X"continue" { return(CONTINUE); }
X"default" { return(DEFAULT); }
X"do" { return(DO); }
X"double" { return(DOUBLE); }
X"else" { return(ELSE); }
X"enum" { return(ENUM); }
X"extern" { return(EXTERN); }
X"float" { return(FLOAT); }
X"for" { return(FOR); }
X"goto" { return(GOTO); }
X"if" { return(IF); }
X"int" { return(INT); }
X"long" { return(LONG); }
X"register" { return(REGISTER); }
X"return" { return(RETURN); }
X"short" { return(SHORT); }
X"signed" { return(SIGNED); }
X"sizeof" { return(SIZEOF); }
X"static" { return(STATIC); }
X"struct" { return(STRUCT); }
X"switch" { return(SWITCH); }
X"typedef" { return(TYPEDEF); }
X"union" { return(UNION); }
X"unsigned" { return(UNSIGNED); }
X"void" { return(VOID); }
X"volatile" { return(VOLATILE); }
X"while" { return(WHILE); }
X
X{L}({L}|{D})* { return(identifier_or_typedef_name()); }
X
X0[xX]{H}+{IS}? { return(INTEGER_CONSTANT); }
X0[xX]{H}+{IS}? { return(INTEGER_CONSTANT); }
X0{O}+{IS}? { return(INTEGER_CONSTANT); }
X0{O}+{IS}? { return(INTEGER_CONSTANT); }
X{D}+{IS}? { return(INTEGER_CONSTANT); }
X{D}+{IS}? { return(INTEGER_CONSTANT); }
X
X'(\\.|[^\\'])+' { return(CHARACTER_CONSTANT); }
X
X{D}+{E}{FS}? { return(FLOATING_CONSTANT); }
X{D}*"."{D}+({E})?{FS}? { return(FLOATING_CONSTANT); }
X{D}+"."{D}*({E})?{FS}? { return(FLOATING_CONSTANT); }
X
X{LIT} { return(STRING); }
X
X">>=" { return(RIGHT_ASSIGN); }
X"<<=" { return(LEFT_ASSIGN); }
X"+=" { return(ADD_ASSIGN); }
X"-=" { return(SUB_ASSIGN); }
X"*=" { return(MUL_ASSIGN); }
X"/=" { return(DIV_ASSIGN); }
X"%=" { return(MOD_ASSIGN); }
X"&=" { return(AND_ASSIGN); }
X"^=" { return(XOR_ASSIGN); }
X"|=" { return(OR_ASSIGN); }
X">>" { return(RIGHT_OP); }
X"<<" { return(LEFT_OP); }
X"++" { return(INC_OP); }
X"--" { return(DEC_OP); }
X"->" { return(PTR_OP); }
X"&&" { return(AND_OP); }
X"||" { return(OR_OP); }
X"<=" { return(LE_OP); }
X">=" { return(GE_OP); }
X"==" { return(EQ_OP); }
X"!=" { return(NE_OP); }
X";" { return(';'); }
X"{" { return('{'); }
X"}" { return('}'); }
X"," { return(','); }
X":" { return(':'); }
X"=" { return('='); }
X"(" { return('('); }
X")" { return(')'); }
X"[" { return('['); }
X"]" { return(']'); }
X"." { return('.'); }
X"&" { return('&'); }
X"!" { return('!'); }
X"~" { return('~'); }
X"-" { return('-'); }
X"+" { return('+'); }
X"*" { return('*'); }
X"/" { return('/'); }
X"%" { return('%'); }
X"<" { return('<'); }
X">" { return('>'); }
X"^" { return('^'); }
X"|" { return('|'); }
X"?" { return('?'); }
X
X. { return BAD_TOKEN; }
X
X%%
X
Xchar *filename = 0;
Xextern int yychar;
Xextern int decl_level;
Xextern int errors;
X
Xyyerror(s)
Xchar *s;
X{
X errors++;
X
X fprintf(stderr, "%s: ", s);
X
X if(filename)
X fprintf(stderr, "file \"%s\", ", filename );
X
X fprintf(stderr, "line %d, token = \"%s\"\n",
X line_num, yytext);
X}
X
X#ifndef yywrap
Xyywrap()
X{
X return(1);
X}
X#endif
X
Xcomment()
X{
X
X int splat_seen = 0;
X
X for(;;) {
X int ch = input();
X switch (ch) {
X default:
X splat_seen = 0;
X break;
X case '*':
X splat_seen = 1;
X break;
X case '/':
X if(splat_seen)
X return;
X else
X splat_seen = 0;
X break;
X case 0: {
X /* This should never happen, because cpp should
X * catch the error first.
X */
X yychar = BAD_TOKEN;
X yyerror("Unterminated comment");
X exit(-(++errors));
X }
X }
X
X }
X
X}
X
Xextern char* strpbrk();
Xextern char* index();
Xextern char* rindex();
Xextern char* emalloc();
X
Xint line_directive()
X{
X /* Handle directive left by the preprocessor, i.e.
X *
X * # line 123 "foo.h"
X * # line 125
X * # 126 "foo.h" 2
X *
X * et cetera.
X */
X
X char *line_ptr = strpbrk(yytext, "0123456789");
X char *file_ptr = index(line_ptr, '"') + 1; /* Start of file-name */
X
X line_num = atoi(line_ptr);
X
X if(file_ptr != 0) {
X
X char *file_end = rindex(file_ptr, '"'); /* end */
X int len = file_end - file_ptr;
X
X if(filename != 0)
X free(filename);
X
X filename = emalloc(len + 1);
X
X strncpy(filename, file_ptr, len);
X filename[len] = 0;
X
X }
X}
X
Xint identifier_or_typedef_name()
X{
X /* Make a copy and set yylval.
X */
X int len = strlen(yytext);
X char *name = emalloc(len+1);
X strncpy(name, yytext, len);
X name[len] = 0;
X
X yylval = name;
X
X /* Return the type of the token,
X * IDENTIFIER, TYPEDEF_NAME, or ENUM_CONSTANT
X */
X if(idents_only[decl_level])
X return IDENTIFIER;
X else {
X return type_of_name(name);
X }
X
X}
X
X
Xlex_sync()
X{
X /* Probably because of its use for interactive line-interpreters
X * like "dc", original yacc uses a "lazy" lookahead, that is to say, it
X * does not fetch a lookahead when the only action is the default
X * reduction. But our scanner-feedback must keep the lookahead in
X * sync. This routine sees to it that the lookahead has been
X * fetched.
X *
X * yychar is the yacc lookahead token. It is -1 when
X * yacc is being "lazy". yylex() is allowed to return -1 (or any
X * negative int) to indicate EOF, but yacc uses 0 to indicate EOF.
X */
X
X if(yychar == -1)
X if((yychar = yylex()) < 0)
X yychar = 0;
X}
X
END_OF_scan.l
if test 6118 -ne `wc -c <scan.l`; then
        echo shar: \"scan.l\" unpacked with wrong size!
fi
# end of overwriting check
fi
if test -f types.h -a "${1}" != "-c" ; then
    echo shar: Will not over-write existing file \"types.h\"
else
echo shar: Extracting \"types.h\" \(241 characters\)
sed "s/^X//" >types.h <<'END_OF_types.h'
X
Xenum name_type { undefined, typename, identifier, enum_const };
Xenum decl_type { name_space_decl, struct_decl };
X
Xtypedef struct {
X char *name;
X enum name_type type;
X enum decl_type decl_type;
X int scope_level;
X
X}declaration;
X
X
END_OF_types.h
if test 241 -ne `wc -c <types.h`; then
        echo shar: \"types.h\" unpacked with wrong size!
fi
# end of overwriting check
fi
echo shar: End of shell archive.
exit 0


--

Return to the comp.compilers page.
Search the comp.compilers archives again.