The Design And Implementation Of The C Compiler Grammar Analysis

High-level programming language promoted the development and application of computer in which the compiler plays an important role. The compiler is the system software and every developer must be familiar with and use it. The design and implementation is a big software project, and the compiler theory and technology that it relies on are very complex so that it is the perfect combination of theory and practice in computer science.This paper designed and implemented the C language compiler lexer and parser. The parser is divided into two kinds of the parser, LR(1) and LL(1) parser.In the design and implementation of the C compiler lexical analyzer, the entire terminal symbols in the C language grammar are divided into three categories: string class, numbers and other symbols. Each class is designed and implemented as an independent module. The realization of string storage in the lexical analyzer uses the combination of hash table and storage area. Manage all storage areas in a single linked list, and the address of the string stored in the storage area is put into the hash table, then the hash value is used as the index. We design error processing and cache management of lexical analysis. Lexical analyzer will provide symbols for the parser.First of all, the products, FIRST and FOLLOW sets are encoded. They will be used in the syntax analyzer. The structure and reduction algorithm of LR(1) syntax analysis are designed on the basis of shift-reduction theory. In the algorithm the reduction production match selection from candidate productions, and use the C grammar symbol’s FIRST and FOLLOW sets as shift and reduction condition. Three data structures are designed based on these algorithms. They are production table, mapping table of symbols to production sets and terminal or non-terminal symbol table. The LR(1) parser is implemented by these designs.This paper uses the recursive descent method to realize the C compiler top-down parser. It’s start from the root node of tree, using the FIRST set to select the corresponding production and FOLLOW set to determine the return or syntax error. In the LL(1) syntax analysis, the left recursion production, the left common factor and the FIRST set conflict problems are respectively use iterative right expansion, the extracted left common factor is analyzed first and “pre-scan and rollback” method to solve.Based on all of the above design and implementation, we integrate the C language compiler lexical analyzer and grammar analyzer. The system has realized the syntax analysis of all the grammar of C89, and can generate syntax tree of source program, as well as can recognize and report errors in grammar. Test results show that all the functions of the system have reached the expected requirements.