CS 3040 Sample Programs and Problems

Finite State Machines

Sample finite state machines. You should try them yourself before looking at solutions:

1. Strings of a's and b's with each b right after an a. The empty string is not included.
2. Non-empty strings of either a's or b's, but not both.
3. aⁱbc^j or aⁱcb^k for non-negative i, j, k.

It's a good idea to write down positive and negative examples before trying to draw the machines.

Python

• BLTL Interpreter:
  • btl_syntax.py: classes to represent BTL programs
  • btl_interpreter.py: evaluating BTL programs
  • test_btl_interpreter.py
• fact.py: Python implementation of factorial

Haskell

myDrop.hs: a recursive re-implementation of Haskell's drop function. patternDrop.hs computes the same result but using patterns in the argument lists. These are discussed in the week 3 notes.

A Haskell implementation of a finite state machine

card.hs: a short example illustrating defining a data type and writing a function processing that type.

Top-down, bottom-up parsers

nats.hs: Natural numbers

C++

simple-expr-recognizer.cpp: a recursive-descent parser implementing an expression recognizer. This serves as an introduction to recursive descent parsing.

simple-expr.cpp: expression parser with evaluation.

expr.cpp: recursive-descent parser for expressions over +, -, *, /, (, and )

• To compile:

          g++ -o expr expr.cpp
  

• To run: enter the expression on the command line, with a space around each token:

          ./expr 3 + 4 - 5
  

  The dot at the start (./) is necessary because there's a more full-fledged version of expr that comes standard on Unix systems.
• Note: (, ), and * are special characters, so you'd want to escape them at the command-line prompt:

          ./expr 18 \* \( 3 - 12 / 2 \)
  

• fact.cpp: C++ implementation of factorial for discussion on semantics

ANTLR

All ANTLR examples