Topics in Midterm 1

Close Book Exam

• Know the concepts and relationships

Introduction To Programming Languages

• Language evaluation criteria
• Language categories
  • Paradigms
    • Imperative (same as Von Neumann architecture, most fundamental)
    • Functional
    • Logic
    • Object-Oriented
  • Implementation
    • Compilation: C, C++
    • Interpretation: Python, Ruby
    • Hybrid: Java

Formal Language Theory

• Definition of a language
  • Alphabet
  • String
  • Language
  • Grammar
• Chomsky hierarchy
  • Regular, Type 3, Finite automata (FA)
  • Context-free, Type 2, Pushdown automata (PDA)
  • Context-sensitive, Type 1, Linear bounded automata (LBA)
  • Recursively enumerable, Type 0, Turing machine (TM)

Describing Syntax

• Syntax
  • Format of a program
  • Language at lexeme/token level (lexical analysis)
    • Regular language (type 3)
    • Lexer/Scanner design
  • Language at program level (syntax analysis)
    • Context-free language (type 2)
    • Parser design
  • Notations system
    • Regular expression (for lexeme/token)
    • BNF (Backus-Naur Form) for CFG (Context-Free Grammar)
    • EBNF (Extended BNF) for CFG (Context-Free Grammar)
• Semantics
  • Meaning of a program
  • Context-sensitive grammar

Lexical and Syntax Analysis

• Motivation: Essential part of compiler and interpreter design

• Lexical analysis

  • Input: Source code
  • Output: Stream of tokens
    • Token: Lexeme + Token type
    • Lexeme: String of characters
    • Token type: Category of lexeme
  • Tools: Regular expression, Finite automata (More powerful tools for context-free grammar like EBNF will also work)

• Syntax analysis

  • Input: Stream of tokens
  • Output: Parse tree
  • Tools: BNF, EBNF, Pushdown automata

• Lexer/Scanner/Tokenizer design

  • State diagram to code
  • Example lexer in C

• Parser design

  • LL(1) parser
    • Example LL(1) parser in C
    • a kind of recursive descent parser (RDP is one kind of top-down parser)
    • left-to-right
    • leftmost derivation
    • 1 token lookahead
    • Express the grammar in EBNF
    • Each non-terminal has a function
  • LR parser
    • Example LR parser in C
    • a kind of shift-reduce parser (SRP is one kind of bottom-up parser)
    • left-to-right
    • rightmost derivation
    • Create two tables: Action and Goto
    • Implement a push down automata
      • Stack: Keep track of the state
      • State: Current state of the parser
      • Action: Shift, Reduce, Accept, Error
      • Goto: Next state

Midterm 1 Take Home Part

• Language example representation interconversion
  • Sample code, existing programming language
  • BNF
  • EBNF