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.


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:

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.


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:

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:

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.


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

See you next time.