Lex & Yaccfor Compiler Writing
Some of the most time consuming and tedious parts of writinga compiler involve the lexical scanning and syntax analysis. Luckily there isfreely available software to assist in these functions. While they will not doeverything for you, they will enable faster implementation of the basicfunctions. Lex and Yacc arethe most commonly used packages with Lex managing thetoken recognition and Yacc handling the syntax. Theywork well together, but conceivably can be used individually as well.
Both operate in a similar manner in which instructions fortoken recognition or grammar are written in a special file format. The textfiles are then read by lex and/or yaccto produce c code. This resulting source code is compiled to make the finalapplication. In practice the lexical instruction file has a“.l” suffix and the grammar file has a “.y” suffix. This process is shown inFigure 1.
If you use the -d flag with the yacc command, the yacc program generates that file from the yacc grammar file information. The y.tab.h file contains definitions for the tokens that the parser program uses. In addition, the calc.lex file contains the rules to generate these tokens from the input stream. The following are the contents of the calc. The function of Lex is as follows: Firstly lexical analyzer creates a program lex.1 in the Lex language. Then Lex compiler runs the lex.1 program and produces a C program lex.yy.c. Finally C compiler runs the lex.yy.c program and produces an object program a.out. A.out is lexical analyzer that transforms an input stream into a sequence of tokens.
Figure 1.
The file format for a lex fileconsists of (4) basic sections
- The first is an area for c code that will be place verbatim at the beginning of the generated source code. Typically is will be used for things like #include, #defines, and variable declarations.
- The next section is for definitions of token types to be recognized. These are not mandatory, but in general makes the next section easier to read and shorter.
- The third section set the pattern for each token that is to be recognized, and can also include c code to be called when that token is identified
- The last section is for more c code (generally subroutines) that will be appended to the end of the generated c code. This would typically include a main function if lex is to be used by itself.
- The format is applied as follows (the use and placement of the % symbols are necessary):
%{
//header c code
%}
//definitions
%%
//rules
%%
//subroutines
The format for a yacc file issimilar, but includes a few extras.
- The first area (preceded by a %token) is a list of terminal symbols. You do not need to list single character ASCII symbols, but anything else including multiple ASCII symbols need to be in this list (i.e. “”).
- The next is an area for c code that will be place verbatim at the beginning of the generated source code. Typically is will be used for things like #include, #defines, and variable declarations.
- The next section is for definitions- none of the following examples utilize this area
- The fourth section set the pattern for each token that is to be recognized, and can also include c code to be called when that token is identified
- The last section is for more c code (generally subroutines) that will be appended to the end of the generated c code. This would typically include a main function if lex is to be used by itself.
- The format is applied as follows (the use and placement of the % symbols are necessary):
%tokens RESERVED, WORDS, GO,HERE
%{
//header c code
%}
//definitions
%%
//rules
%%
//subroutines
These formats and general usage will be covered in greaterdetail in the following (4) sections. In general it is best not to modify theresulting c code as it is overwritten each time lexor yacc is run. Most desired functionality can be handledwithin the lexical and grammar files, but there are some things that aredifficult to achieve that may require editing of the c file.
As a side note, the functionality of these programs has beenduplicated by the GNU open source projects Flex and Bison. These can be usedinterchangeably with Lex and Yaccfor everything this document will cover and most other uses as well.
Here are some good references for further study:
The Lex & Yaccpage – has great links to references for lex,
Nice tutorial for use of lex &yacc together
http://epaperpress.com/lexandyacc
- Lex is a program that generates lexical analyzer. It is used with YACC parser generator.
- The lexical analyzer is a program that transforms an input stream into a sequence of tokens.
- It reads the input stream and produces the source code as output through implementing the lexical analyzer in the C program.
Kms Tools
The function of Lex is as follows:
- Firstly lexical analyzer creates a program lex.1 in the Lex language. Then Lex compiler runs the lex.1 program and produces a C program lex.yy.c.
- Finally C compiler runs the lex.yy.c program and produces an object program a.out.
- a.out is lexical analyzer that transforms an input stream into a sequence of tokens.
Lex file format
A Lex program is separated into three sections by %% delimiters. The formal of Lex source is as follows:
Definitions include declarations of constant, variable and regular definitions.
Rules define the statement of form p1 {action1} p2 {action2}....pn {action}.
Where pi describes the regular expression and action1 describes the actions what action the lexical analyzer should take when pattern pi matches a lexeme.
User subroutines are auxiliary procedures needed by the actions. The subroutine can be loaded with the lexical analyzer and compiled separately.