CMSC 331, Fall 2017--Study Guide

- Intro:
  - Motivation for studying PLs
  - Evaulation Criteria
    - Readability, Writability, Reliability, Cost
  - Von Neumann architecture
  - Categories of languages
    - Imperative (procedural)
    - Object-oriented
    - Functional
    - Rule-based/Logic-based
  - Implementation methods
    - Interpreted, compiled, hybrid
      - Pros and cons of each, in terms of complexity, speed, portability,
	debugging, etc.

- History of PLs
  - Beginnings
    - Von Neumann
    - Zuse & Plankalkul
  - Important (Historical) Languages
    Know one or two key historical features of each: why was it important
    in the evolution of programming languages?
    - Machine code
    - Fortran
    - Cobol
    - Algol
    - Lisp
    - APL
    - Pascal
    - C
    - Ada
    - C++
    - Java

- Syntax/Semantics
  - Syntax vs. Semantics
    - What is the difference?
  - Grammars
    - Four general types
  - Context-free grammars (CFG)
    - Noam Chomsky
    - Backus Naur Form (BNF), Extended BNF (EBNF)
      - Terminals & non-terminals
      - Recursion
      - Derivations
	- Leftmost and rightmost derivations
	- Sentential form
    - Finite vs. infinite languages
    - Parse trees
    - Ambiguous vs. unambiguous grammars
    - Operators
      - Notation: infix, prefix, etc.
      - Precedence, associativity
	- Implementing precedence and associativity in a CFG
      - Conditionals
    - Syntactic sugar
      - E.g.: EBNF vs. BNF
    - Language generators vs. recognizers
    - Parsing CFGs
      - Order of complexity for general CFG
      - Linear-time parsing and restrictions on grammar
      - LL(n) and LR(n) parsers
      - LL(1) and Recursive descent parsers
      - LR(1) and Bottom-up parsers

  - Semantics
    - Motivation:
      - Understanding programs at deep level
      - Program verification
    - Static vs. Dynamic semantics
      - Static semantics
	- Attribute grammars
      - Dynamic semantics
	- Operational semantics
	- Axiomatic semantics
	  - Weakest precondition
	  - Axiomatic semantics for statements
	  - Axiomatic semantics for sequence of statements
	  - Axiomatic semantics for conditionals
	    - weakest precond. vs. logical implication
	- Denotational semantics
	  - A simple single-sentence description will suffice
	  - Don't study details
  - Lexical analysis
    - Regular expressions (RE)
      - What they are
      - Equiv. to regular grammars: where they fit in Chomsky's classifcation
    - Role of lexical analysis in PL compilation or interpretation
    - Tokens, patterns, lexemes
    - Basic parts and operators of a regular expression
      - characters, char. classes, *, +, (...), |, etc.
    - Finite automata/finite state machines (FA/FSMs)
      - Must be able to draw one
      - Start state, accepting states, labelled transition arcs
      - Deterministic vs. non-deterministic FA (DFA vs. NFA)
    - Relationship between RE and DFA
    - Constructing lexical analyzers
      - Code-based
	- Table-driven
      - Lex
	- General syntax of a lex file
  - Parsing--Part I
    - Top-down vs. bottom-up parsers
    - Top-down parsers:
      - LL(1) parsers (know what the two 'L's and '1' each stand for)
      - Recursive descent
	- Recursive descent vs. left-recursion
	  - Eliminating left-recursion
      - Predictive Parsers
      - Left factoring
      - Parsing tables
      - First sets, Follow sets