2015-01-20
Class 3
Overview (Ch. 2)

syntax (form) vs. semantics (meaning)
  - BNF is the standard for describing syntax
  - no predominate standard for describing semantics
    - operational  (state-based)
    - denotational (function-based)
    - axiomatic    (proof-based)

their translator: code -> intermediate code
  - from Fig. 2.1 to Fig. 2.2
  - Fig 2.4 good example
  - we will do this for Decaf
    - (and hopefully a bit further)

context-free grammar: {V,Σ,R,S}
  - V: set of non-terminals
  - Σ: set of terminals             "tokens"
  - R: relation: V -> (V ∪ Σ)*      "productions"
  - S: s ∈ V                        "start symbol"

sentence: string of terminals

productions are noted using Backus-Naur Form
  - "::=" vs. "->"
  - "<expr>" vs "E"

derivations
  - start symbol -> sentence using production-based transformations
  - generates a "syntax tree" or "parse tree"

"ambiguous" grammars
  - two trees/derivations generating the same sentence
  - example in Fig 2.6:
        S -> S + S
        S -> S - S
        S -> 0 | 1 | 2 | ... | 9
  - sources and fixes
    - ambiguous associativity: make a rule more restrictive
    - ambiguous precedence: add a new "level" in the grammar

syntax-directed translation
  - attach actions or attributes to grammar productions
  - attributes (properties of syntax tree nodes)
    - synthesized vs. inherited attributes
    - semantic rules
  - actions (program fragments)

traversals
  - depth-first: inorder, preorder, postorder
  - breadth-first

parsing
  - O(n^3) in general; O(n) for grammars we will discuss
  - top-down (recursive descent, LL(1))
    - recursive subprograms, "match()"
    - FIRST(α): possible first terminals of all sentences generated by α
    - ε-productions
    - PROBLEM: left recursion
  - bottom-up (SLR, LALR, LR(1), GLR)
    - parsing tables, "shift/reduce"

Fig. 2.19: example of top-down parser

building syntax tree while parsing
  - node for each non-terminal
  - properties and/or subnodes for some terminals
  - discard some terminals

recommended exercises
  - 2.2.1-2.2.4
  - 2.3.1, 2.3.2, maybe 2.3.5
  - 2.4.1

calc project
  - more complex than the postfix translator from 2.5.5
    - more operators (note different associativity)
    - more types of output (should build syntax tree)
  - less complex than the code generator of Appendix A
    - no keywords
    - no blocks or variables
       - no need for symbol table
    - no need for checking
  - test cases on the server

next time
  - more complex lexing
  - symbol tables
  - type checking
  - 3-address code and labels
  - help with calc project