Tom Niemann's "Tutorial on Lex and Yacc"
Scanners for production compilers or software systems must be verified (by proof, demonstration, review, or test, that shows that the requirements, design, and performance specifications are met) and validated (also by proof, demonstration, review, or test that shows that the scanner satisfies the needs of its users and its role in a larger containing system--either compiler or system application). The amount of effort expended in verifying and validating a scanner is dependent on the purpose and intended use of the scanner. For both verification and validation, the description of the input language must be shown to be correct. If the scanner is generated, then the quality of the scanner depends on the reliability and effectiveness of the generator.
In this exercise, you will be introduced to LEX and YACC, which stand for Lexer (short for lexical analyzer) and Yet Another Compiler-Compiler. They are generators, i.e. programs that generate other programs, in this case, a scanner and a parser. Our focus in this Unit 4 Assessment will be on LEX, actually, FLEX - which stands for Fast Lexer. Read this tutorial on LEX; it provides a concise description of LEX and YACC. Then, complete the exercises on this page.
Exercise #1: Draw a high level block diagram depicting LEX and a C compiler, together with the input and output files for each of them.
Exercise #2: Give the LEX input file for replacing 00 with the text 'error' in the language L of Exercise #1 from Assessment 1.
Exercise #3 (optional): For this exercise, we will be using several software tools: a generator for scanners (lexical analyzers), a C compiler, and text editor for creating input files. We will use a scanner generator, called FLEX for creating scanners. FLEX is based on the earlier, original LEX. There are several good compilers available, cyngwin and gcc. We will use gcc. There are, also, several editors for creating input files; we'll use Notepad++.
a) Install FLEX on your computer. Installation guidance is given below.
b) If you do not have a C compiler, install a C compiler on your computer. Instructions for installing the gcc compiler can be found here.
c) Check your answer to Exercise 2 by using FLEX and your C compiler to create a scanner; test the scanner by running it on a collection of sample input strings that are in the language of Exercise #1 from Assessment 1. Also, run it on some strings that are not in the language of Exercise #1.
You can check your answers against the Answer Key.
Installation Notes for FLEX, Bison, and the Gcc (Gnu Compiler Collection) Compiler
These notes give suggestions on the installation of FLEX, Bison (open source software for the original Lex and Yacc), and the gcc compiler.
To download and install FLEX (used for Exercise #2 and Exercise #3, and Bison used for Exercise #3):
1) Use your search engine to find a free software version of Flex and Bison to download; for example, type in 'free software foundation fast lexical analyzer' or 'free software foundation software for Yacc;' look over the results and select a copy of FLEX and Bison to investigate. Be careful to avoid risky sites.
Look for a specific version of FLEX, for example, search for 'FLEX for Windows.'
OR
2) Go here for Flex, here for a Windows version for Flex, and here for Bison.
3) After selecting a 'reliable' site, such as gnu.org, look for a version of FLEX for your operating system and follow the instructions for downloading and installing it, including documentation. This should also give you Bison. After downloading FLEX, if Bison is not included, repeat the steps 1), 2), 3) for Bison.
4) For a C compiler, you may already have one installed on your machine. If not use your search engine to search for "cyngwin C compiler" or "gcc C compiler" and look for a free software version that you can download. Be caution of risky web sites. For the gcc compiler, for example, search for "codeblocks.org gcc compiler". Some of the results may refer to mingcc (minimal gcc compiler), which will work. Installation of a compiler can be involved and the use of an installer is recommended. A good tutorial on the installation of the gcc compiler can be viewed here.
Make sure that the version of FLEX or LEX, and Yacc and Bison, you obtain are compatible.
You can check your answers against the Answer Key.