CS 440/540 Examples in C++

The purpose of this page is to provide you with some working examples of the use of the tools we will use in this class. As we move through the topics, you will want to get these files and try to build them yourself. You may use them as the starting point for the class projects, if you like.

Lexical Analysis

To build the below examples:

flex yourfile.l
g++ -x c++ lex.yy.c -ll

• Remove white space (very simple example)
• Character, line, word counting Lex example from the slides.
• Lex example using states: removing comments from code
• Transforming input

---

Recursive Descent (LL) Parsing

• Expression grammar recursive descent parsing
• This is a nonsense grammar from a programming contest: the lowercase words are non-terminals, the uppercase characters are the terminals of this language.

    slurpy -> slimp slump
    slimp -> A rest_slimp 
    rest_slimp  -> H
  
    rest_slimp -> B slimp C
    rest_slimp -> slump C
    slump -> d_or_e F f_string end 
    d_or_e -> D
    d_or_e -> E
    f_string -> F f_string | lambda
    end -> slump
    end -> G 
  
   
  Some strings in the language: AHDFG, ADFGCDFFFFFG, ABAEFGCCDFEFFFFFFG
  Some strings NOT in the lanuage: AHDFGA, DFGAH, ABABCC

  • a Lex spec. for the language
  • a header file defining the tokens
  • a Makefile
  • C++ parser.
• A DFA based example (C, but should compile with g++)

---

LR parsing

For C++, I have had more success with bison than with yacc. There are some small differences between the tools that you need to be aware of. Instead of producing a y.tab.c file, the file is named after the specification. Using bison file slurp.y, we would get a slurp.tab.c (and slurp.tab.h).

As with the earlier flex stuff, you need to use the -ll library. For bison, you also need -ly. The correct use:

flex file.l
bison -vd file.y
g++ -x c++ file.tab.c lex.yy.c -ly -ll

• An LR (YACC) version for the nonsense language:
• a Lex spec. for the language (notice that it is different from the one above. I wanted to show you another way of passing single character tokens.
• a Makefile for the program
• the Yacc specification
• A simple calculator
  • a Lex spec. for the language
  • the YACC specification
  • a Makefile for the program

Syntax directed translation

• A simple calculator with evaluation
  • the Lex specification for the language
  • the YACC specification

• A calculator with evaluation and with a symbol table. This example allows single character (lower case) variables to be given a value and later used in other expressions.
  • the Lex specification for the language
  • the YACC specification
  • Simple symbol table (header and implemenation