Tom Niemann's "Tutorial on LEX and YAC"
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 Assessment will be on YACC. Read the part of the tutorial on YACC. This tutorial explains YACC and how YACC and LEX interface. LEX and YACC are the original programs, and just as Flex is an open software version for LEX, Bison is an open software version for YACC.
Exercise #1: Add a block diagram depicting YACC, C compiler, and the connections with their input and out files, and the connections to LEX.
Exercise #2: In Assessment 3, we developed a scanner for recognizing the language L of Exercise #1 of Assessment 1. Here, instead of using LEX, we will use YACC. YACC builds a context free syntax analyzer, i.e. a parser for the language we want to analyze; LEX builds a regular expression analyzer. Because the former is more powerful than the latter, whatever LEX can do, YACC should be able to also do. For this exercise, describe L by a grammar that can be input to YACC to create a parser for recognizing the strings of L.
Exercise #3 (Optional): For this exercise, we will be build the parser for the language L, used in #3 above, to check our solution to #3. We will use several software tools: a generator for scanners (lexical analyzers), a C compiler, and text editor for creating input files, and a parser generator. We will use a scanner generator, called FLEX, based on the original LEX. The particular version of Flex we will use is Win_Flex, a FLEX scanner generator that runs on Windows. There are several good compilers available, cyngwin and gcc. We will use gcc. There are also several editors for creating input files; we will use Notepad++. For the parser generator, we will use Bison, an open source parser generator based on the original YACC. The version of Bison that we will use is Win_Bison, a version that runs on Windows. You may download the executables for Win_Flex and Win_Bison.
You can check your answers against the Answer Key. This assessment should take approximately 3 hours to complete (not including installation of Bison and the Gcc compiler).
Installation Guidance for installing Flex, Bison, and the gcc compiler were given at the end of the problem statement for Assessment 3 Exercise #4. Additional guidance is included in the following problem statement.
a) Install Bison on your computer. (FLEX should already be installed from Exercise #3). Installation of Bison may have been done when you installed FLEX. If not, see the Installation guidance in the instructions for Assessment 3. The installation of Bison includes documentation. Good manuals can be found here for FLEX for Windows and here for Bison for Windows.
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 Bison and your C compiler to generate a simple parser for language L - strings of 0's and 1's, not including 00, and ending in 1. Test the parser by running it on a collection of sample input strings that are in the language L. Also, run it on some strings that are not in L