Copyright © 2004, 2021
Robert W. Hasker

CS 4980 CC - Note 1

Introduction

• intro self
• Office hours: see web page: https://faculty-web.msoe.edu/hasker/
  • Also: whenever I'm in or by appointment.
• syllabus review
• time requirements: significant
• textbook: intended for careful reading

Compilation

• Chapter 1
• what does a compiler do?
• phases of a compiler:
  • lexical analysis: sequence of tokens ("words")
  • parse: abstract syntax tree
  • semantic analysis
  • code emission
• alternate view: see p. 4 of textbook
  • can split compiler into a very large number of phases!
  • allows reusing any number of phases to support changing input language, instruction set, optimizations, etc.
  • phases often combined
• tools
  • context-free grammars: specifying the language to be parsed
  • regular expressions: specifying the language of tokens

Basic structure of the course

1. lexical analysis
2. parsing
3. code generation
4. issues for modern languages
5. optimization (if time)

Why study compiler construction?

• probably not to build a compiler
• understand languages, optimization
• process application-specific languages
• build language manipulation applications
• useful tools: lex, yacc

Starting Point: Specifying a language

• How to define a programming language?
• Solution 1: English/French/Mandarin description - problems?
• Solution 2: follow model of natural languages:
  • A sentence is a subject followed by a verb followed by an optional direct object
  • Issue: verbose, hard to maintain
  • Elements to keep: have classes of items, can substitute sequences for other items
• Solution: context free grammar
  • Classes of things, stuff you can substitute for: words starting with caps
  • Terminals: things that cannot be substituted for; all lower case letters or quoted strings
    • Examples: numbers, character constants, 'true', 'false', '{', '}'
  • Rules: how to substitute one thing for another
  • Example:

            Statement -> Assignment
            Statement -> 'if' Variable 'then' Statement 'else' Statement
            Assignment -> Variable '=' number
            Variable -> identifier
    

    where identifier is a sequence of letters, number is a sequence of digits
• Write some sample programs, including nested ifs
• Extend the language to allow print to display a value
• Extend the language to allow multiple statements inside if's
• The power of this notation: expression grammar: introduce

      Expression -> Term 
      Expression -> Term '+' Expression
      Term -> Factor
      Term -> Factor '*' Term
      Factor -> '(' Expression ')'
      Factor -> constant
  

  where constant is a sequence of digits

Parsing 101: Recursive Descent

• Grammar gives us a way to parse code!
  • Rewrite the expression grammar in English:
    • An expression is a term or a term, '+', and a (sub)expression
    • A term is a factor or a factor, '*', and a (sub)term
    • A factor is a constant or a left parenthesis followed by an expression followed by a right parenthesis
    • A constant is one or more digits
  • In code:

    void parse_expression() {               void parse_factor() {
      parse_term();                           if ( next_token() == '(' ) {
      if ( next_token() == '+' ) {              parse_expression();
        parse_expression();                     if ( next_token() != ')' )
      }                                           fail();
    }                                         } else 
                                                parse_constant();
    void parse_term() {                     }
      parse_factor();
      if ( next_token() == '*' ) {         void parse_constant() {
        parse_term();                         if ( ! isdigit(next_character()) ) fail();
      }                                       while ( isdigit(next_character()) )
    }                                           advance();
                                            }
    

• Known as a recursive descent parser
  • Note expression is very recursive
  • Wins: can handle almost any language, no extra tools needed, easy to generate errors
  • Issue: doesn't scale!
• Full implementation: simple-expr-recognizer.cpp

Assignment 1

• Create a grammar for boolean expressions (and, or, not)
• assume variables, expressions of the form a <= b and a == b
• Implement in Java