CS 440/540 Examples in C

    The purpose of this page is to provide you with some working examples of the use of the C 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.

    I have pages that have similar examples for the following other languages:

    • C++
    • Java

    Lexical Analysis

    • 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

    To build the above examples, use flex and gcc.

    Recursive Descent (LL) Parsing

    • Expression grammar recursive descent parsing
    • This is a 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 for the C version of program
      • Here is a C parser for the slurpy language that parses each input separately but assumes that each line contains a single slurpy element. The entire file is either accepted or rejected 

        slurpy_file: slurpy_file slurpy EOLN
   | slurpy EOLN
;
      • Sample testfiles: test1 test2

    • A DFA based example

      LR parsing

      These examples (and their makefiles) assume C. However, they can be compiled as C++ with minimal effort (see the C++ version of this page).
      • An LR (YACC) version for the Slurp 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

      • A larger example based on a toy programming language
        • a Lex spec. for the language
        • the parser
        • a Makefile for the program

      Syntax directed translation

      • Calculator with evaluation
        • a Lex spec. for the language
        • a YACC spec. for the language
        • Makefile
      • 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.
        • a Lex spec. for the language
        • the YACC specification
        • a Makefile for the program

      • Ex. 2.7 from the text

        • Grammar 
        seq -> seq instr
seq -> BEGIN
instr -> EAST
instr -> WEST
instr -> NORTH 
instr -> SOUTH
        This simple example demonstrates the use of structs in unions.
        • A Lex specification
        • A YACC specification

      • A typechecking example (similar to the one on the slides)
        • A Lex specification
        • A YACC specification
        • types.c
        • types.h
        • A makefile
        • A test file -- correct
        • A test file -- correct
        • A test file -- correct
        • A test file -- type errors
        • A test file -- type errors
        • A test file -- type errors
        • A test file -- type errors
        • A test file -- type errors
        • A test file -- type errors
        • A test file -- type errors
      • Very simple example of attaching info to tokens
      • Very simple code generation example