CS 430: Lecture 2 - Language Matters

Dear students:

You've read and taken a quiz on matters related to specifying a language and recognizing a program in a language. You learned about state machines, lexing, parsing, derivations, and parse trees. You learned about interpreters and compilers, which are the tools that understand your source code. Today we'll work through some language problems and solve some Ruby exercises.

Lexing

The first stage of understanding a program is to chop it up into tokens, which is the job of the lexer. The lexer is an assemblage of state machines that look for patterns of characters. Let's design two of these machines:

• Draw a state machine for recognizing big endian dates.
• Draw a state machine for recognizing real number literals.

State machines themselves aren't powerful enough to recognize an entire program. For example, you can't build a state machine that recognizes tokens like <>, <<>>, <<<>>>, and so on. State machines don't have the “memory” needed to recognize recursive structures found in math and programs.

Parsing

The second stage of understanding a program is to group the tokens into a represent that captures the hierarchical structure of a program. This is the job of the parser. Before writing a parser, we often lay out the rules of our language in a grammar. Let's solve these grammar problems:

• Write a grammar for the note list of RTTTL. Wikipedia provides this example:
  content_copy

  2a4, 2e, 2d#, 2b4, 2a4, 2c, 2d, 2a#4, 2e., e, 1f4, 1a4, 1d#, 2e., d, 2c., b4, 1a4, 1p, 2a4, 2e, 2d#, 2b4, 2a4, 2c, 2d, 2a#4, 2e., e, 1f4, 1a4, 1d#, 2e., d, 2c., b4, 1a4

  2a4, 2e, 2d#, 2b4, 2a4, 2c, 2d, 2a#4, 2e., e, 1f4, 1a4, 1d#, 2e., d, 2c., b4, 1a4, 1p, 2a4, 2e, 2d#, 2b4, 2a4, 2c, 2d, 2a#4, 2e., e, 1f4, 1a4, 1d#, 2e., d, 2c., b4, 1a4

• Write a grammar for expressions that add and multiply integers.

Once we have a grammar, we show how a string of symbols is parsed using derivations or parse trees. Let's parse these strings using our grammars:

• The tune 1f#5, 2a5.
• The expression 2 * 9.
• The expression 3 + 40 * 5.

Kattis Problems

Last time we started poking at some problems in Ruby. Hopefully you saw that learning a new language doesn't happen in 30 minutes. You must practice. Let's revisit those problems and solve them together.

• Stuck in a Time Loop
• Sort Two Numbers
• Pot
• N-sum
• Planina
• Nasty Hacks
• Finding an A
• Cold-puter Science

TODO

Here's your list of things to do before we meet next:

See you next time.