Programming Language Concepts

Table of Contents

Lecture 1


  • Uses hand-in for assignments
  • Canvas is used for announcements
  • four languages/techniques
    • antlr
    • javascript
    • haskell
    • prolog
  • Class uses iclicker channel AC

Lecture 2


  • not about popular languages
  • why not just java
    • no low-level stuff
  • Electronic submission of assignments
    • PDFS with highligting and annotations
    • using webgrader
  • Academic honesty
    • fairly normal
    • discuss above the level of psuedocode
    • permitted diagrams can be found in 15.1, 15.2, 16.1 of the textbook
  • clicker questions
    • discuss problems and different views of problems
  • Ex, Matlab
    • used in engineering
    • interpreted, proprietary, GNU Octave
    • input and source program go in at the same time
    • use the strengths of languages, in matlab, matrices are your friend

The start

  • lexical/syntax analysis
    • translate sourcecode into machine code or other source code
      • rules about what to do expect
    • char stream to scanner to token stream to parser to parse tree to semantic analysis to ast or ir to optimization to ir to final output
    • syntax rules provide formatting, allows both humans and computers to process and create information
  • scanners recognize regular languages, break input into tokens, like regular expressions
  • parsers recognize context-free grammars

Lecture 3

More scanners

  • regexes for regular languages
  • NFA can go to different states at varying times
    • no input with an \(\epsilon\)
    • states can be shrunk by fiding removable \(\epsilon\) transitions, and thus converted to a dfa
  • DFA can be simplified, but must be done carefully
  • a simplified DFA can be converted to a lookup table

Context Free Grammars

  • allow you to recognize paired parens, keep track of information and state
  • grammars are terminals and nonterminals
  • lhs has only non-terminals
  • terminals and non-terminals on rhs
  • BNF most common notation for CFGs
    • no kleene star
  • EBNF allows for kleene start or plus
  • start with a start symbol (production)
  • continue using valid productions based on tokens
  • end when all non-terminals are resolved
  • LL left to left, left most derivation (noting you needed to make a specific turn), top down, requires look-ahead, break ties on the left
  • LR left to right, right-most derivation (noting what turns you need to make next), bottom up, break ties on right
  • will form parse trees

Lecture 4

More Scanning and Parsing

  • LL Grammars, Deriving from the left
    • top down
    • predicts production to use
    • number of lookaheads required defines what classification of grammar
  • LR grammars, Right Most derivation
    • bottom-up
    • recognize which production to use


  • fixdng ambiguity can be done by adding new rules, or modifying other ones
  • antlr syntax isn’t that bad

Lecture 5

Semantic Analysis

  • syntax does not equal semantics
  • syntax is form of a valid program
  • semantics are the meaning of a valid program
  • syntax is recognized by a CFG
  • semantics are recognized by an attribute grammar
  • semantics make sure input is meaningful
  • static semantics are enforced at compile time
  • dynamic semantics are checked at run time
  • parse tree can be decorated (annotated) with attributes
  • some dynamic checks can be slow, some free
    • div by zero can be done in hardware
    • pointers can be more complicated
  • use of assertions, pre/post conditions and invariants
  • static analysis
    • compile time prediction of behavior
    • precise analysis can determine if a program will always follow rules
      • hakell’s hindley-milner type checker
    • generates code for what is unknown at compile time
    • determine what is safe to do (thread safety for instance)
  • attribute grammars
    • add meaning to a parse tree
    • can only use local information
    • annotation is the process of evaluating attributes
    • flow is bottom up
    • all s attribute grammars ar l attribute grammars

Date: 2017-08-08 Tue 14:31

Author: Samuel W. Flint

Created: 2017-08-30 Wed 14:12