Advanced Programming I Lecture Notes

6 February 2007 • Assignment 1 Code Review

Outline

• The problem.

• A solutions.

• Testing

• Results

• Observations

The Problem

• Read in a regular expression, write out the language generated by the regular expression.

• The solution.

  main()
    regular_expression regexp
  
    while (input_regexp(std::cin, regexp))
      const language l = generate(regexp)
      ouput_language(std::cout, l)
  

Make A Wish

• We don't have read(), gen-language(), or write().

  • What's a regular-expression? What's a language?

  • Later for that.

    • Delay decisions to gather more information.

• Reading and writing seem relatively simple, undemanding and unimportant.

  • Deal with generating languages.

Regular Expressions

• Study the problem.

  • What are its properties?

  • How can you make it simpler?

• What's a regular expression?

  • It's a single regular expression followed some other regular expressions.

    

Regular Languages

• What language does R_f R_r generate?

• R_f generates L_f and R_r generates L_r.

  • L_f followed by L_r.

• Each string in L_f is prepended to every string in L_r.

  • Call this the cross-product of the two languages.

Generating A Language

• The genii is primed.

  gen-language(regexp)
  
    if is-simple-regexp(regexp)
      return gen-simple-language(regexp)
    else
      regexp-f, regexp-r = 
        split-regexp(regexp)
  
      return cross-product(
               gen-language(regexp-f), 
  	     gen-language(regexp-r))
    

Inventory

• If we have

  • is-simple-regexp()

  • gen-simple-language()

  • split-regexp()

  • cross-product()

  then we're done.

• Given those, does gen-language() work? Is it correct?

More Work

• cross-product() is straightforward.

• is-simple-regexp() and split-regexp() are related.

  • split-regexp() splits after the first simple regular expression.

• gen-simple-language() assumes simple regular expressions.

Make A Wish

• Suppose simple-regexp-end() returns a pointer to the end of the first simple regular expression.

  is-simple-regexp(R)
    return size(R) == simple-regexp-end(R)
  
  split-regexp(R)
    e = simple-regexp-end(R)
    return R[0, e - 1], R[e, size(R)]
  

What's Left?

• The only open problems are

  • simple-regexp-end()

  • gen-simple-language()

• What do we know about language and regular expression data structures?

  • The operations discovered so far are providing details.

Simple Regular Expressions

• Simple regular expressions come straight from the problem.

  • ? R

  • * R

  • | R₁ R₂

  • ( R₁ R₂ ... )

  • Everything else.

simple-regexp-end()

simple-regexp-end(regexp)
  case regexp[0] of
    '?' e = simple-regexp-end(regexp + 1)

    '*' e = simple-regexp-end(regexp + 1)

    '|' e = simple-regexp-end(regexp + 1)
        e = simple-regexp-end(regexp + e)

    '(' e = 1
        while regexp[e] != ')'
	  e = simple-regexp-end(regexp + e)

    else  e = 1

  return e

Generating Simple Languages

• The pattern follows simple-regexp-end().

• ( R₁ R₂ ... )

  return 
    gen-language(regexp[1, size(regexp)-1])

• | R₁ R₂

  e1 = simple-regexp-end(regexp + 1)
  e2 = simple-regexp-end(regexp + e1)
  return 
    union(gen-simple-language(regexp + e1)
          gen-simple-language(regexp + e2))
  

Regular Expression Data

• What operations do regular expressions need to support?

  • Splitting, referencing component parts, comparing parts.

• An array of tokens should do the trick.

  • But any data structure supporting the operations will do.

• Listen to the solution; it will tell you.

Regular Language Data

• What operations do regular languages need to support?

  • Cross-products, unions, and a few others.

• An array of strings should do the trick.

  • This is similar to regular expressions.

  • Resist the temptation to combine the two; they are different in important ways.

Errors

• What about errors and error handling?

  • Doing this well is hard.

• There are two general choices:

  1. Hide errors as regular data.

  2. React immediately and vigorously to errors.

• Stick with 2, particularly if you know about exceptions.

Testing

• Always test your code.

  • I'm going to.

• Tests don't have to be complicated.

  • Lots of simple tests run all the time.

• Let the tests help you shape the design's refinement.

  • Use refinement steps that have a simple test.

Tests

• Get the empty-input test to work.

• What were the tests for the next steps?

  • The simplest possible regular expression: a.

  • Only implement what's needed to correctly handle a.

  • Once a works, get a a working.

Generic Tests

• Every assignment should pass these two tests:

  1. The empty-input test.

     $ ./pgm < /dev/null
     

     Programs should handle empty input.

  2. The garbage-input test.

     $ ./pgm < pgm
     

     Programs should handle garbage input.

• "Handle" means "not coredump."

Assignment Tests

• You've already seen the assignment tests.

  
  ""
  {  }
  ( )
  {  }
  a a
  { a a }
  a b
  { a b }
  ? a
  { "", a }
  | a b
  { a, b }
  * a
  { "", a, a a }
  | a ( )
  { "", a }
  ? a ? a
  { "", a, a a }
  
  

Coding

• Program Defensively.

• No coredumping.

• Coding style.

  • Write small functions.

  • Document your functions.

Program Defensively

• Every program will be tested against garbage input.

  $ ./pgm < pgm
  

• Make sure your code can handle it.

  • "Handle" means "not coredumping."

• The answer to the question

  "Can input be like this...?"

  is "Yes."

No Coredumping

• A coredump is an unexpected, abnormal termination.

• Coredumping looks like this:

  
  ../../test-code: line 165: 10192 Segmentation fault ...
  
  ../../test-code: line 133: 10060 Killed ...
  

• It is easy to coredump programs in C++.

  • Particularly when pointers are involved.

• It's your responsibility to make sure coredumps don't happen.

Commented-Out Code

• Please don't submit commented-out code.

  // int qmarks = 0;
  // int stars = 0;
  // int bars = 0;
  
  /*
  int qmarks = 0;
  int stars = 0;
  int bars = 0;
  */
  

• Use version control (CVS, RCS) or make trial copies.

Write Small Functions

• Each functions or procedure should be small: 20 to 30 lines.

  • Small functions are focused.

  • The less it does, the less likely it is to go wrong.

  • A small function is easier to understand than a large one.

Comment Functions

• Each function should have a comment describing what it does and how to use it.

  • Nothing about how it works, or why.

• How to use it:

  • The inputs and outputs, including globals.

  • The relation between inputs and outputs.

  • The error conditions.

Example Function Comments

• Ok

  // Output an error if the open paren
  // exceeds the close paren. 
  
  bool parenerror (int op, int cl)
  

• Better

  // Return op ≤ cl.
  // Print an error if op > cl.
  
  bool parenerror (int op, int cl)
  

• Is this a good function?