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 - 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 - 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 [Midterm covered up to here.] - Bottom-up parsing - LR(1) parsers (know what the 'L', 'R', and '1' each stand for) - Right sentential forms - Phrases, simple phrases, and handles - Shift-reduce parsing - 4 actions: shift, reduce, accept, and fail - LR parser tables - Shift/reduce conflicts - Yacc - General syntax of a yacc file - Syntax-directed translation - Instead of producing parse trees, grammar drives direct computation - Can be thought of as compilation of language to executed code. - E.g.: our prefix-notation calculator - Scheme - Functional vs. imperative programming - Foundations in mathematics - Side effects-free programming - Read-Eval-Print Loop (REPL) - S-expressions - Lists (proper lists) - Null - #t, #f - Quoting - using "quote" - using "'" - Functions - As first-class objects (know what this means) - Predicates - Special forms - What are they? - How Scheme evaluates an S-expression - define - Syntax for defining variables - Syntax for defining named functions - eval, apply - map - Recursion - car, cdr, cons - Dotted pairs - Lambda expressions - Defining functions and lambda forms that take any number of args, 1- or more args, 2 or more args, etc. parameters - Function composition - Tail recursion - Motivation--regular recursion and stack space - Identifying true tail calls - Tail call optimization - Converting taill call into goto - Do other languages like Python and Java do tail call optimization? - Lexical vs. dynamic scoping - Explanation of lexical scope and dynamic scope - Free vs. bound variables - Scheme's "let" form - "let" as lambda expression - let* - Dynamic scoping in CommonLisp - Advantages and disadvantages of lexical vs. dynamic scoping - Environments - Be able to describe and diagram - Closures - Know how we used it in class to generate counters - Garbage collection - Box and pointer notation - You should be able to draw a diagram of how lists are internally represented, and pointed to by symbol table entries. - Functions, special forms and predefined symbols you should remember: define, print, #t, #f, null, append, list, quote, ', cons, car, cdr, null?, list?, if (if-then-else) - Functions, special forms and predefined symbols you should know if we remind you: member, cond, reverse, pair?, equal?, length, map, list-ref, list-tail - Perl - What's it good for? - Basic syntax - Data types - Numbers and strings - Scalars, arrays, and hashs - $, @, % - How to access members of arrays and hashes - General syntax - You should be able to write simple Perl programs for the exam - You should also be able to figure out what simple Perl programs do. (We will not give you any examples that use shortcuts, defaults, or other Perl shorthands that cause confusion.) - Filehandles, I/O, STDIN & STDOUT - Regular expressions (REs) - General syntax: - Character ranges and classes - *, + (0-or-more and 1-or-more) - ? (optional) - The binding operator "=~" - The three regular expression functions: - matching: "m/some pattern/" - substitution: "s/old/new/" - translation: "t/ABC/abc/" - Problems with greedy matches, earliest matches - Contexts - Scalar vs. list context - How contexts affect interpretation of variable references and expressions - Scope - Declaring variables: - "my": lexically scoped - "local": dynamically scoped - Some issues with Perl from a language design perspective - You should be able to list a few problems with Perl in terms of specific features that violate properties of orthogonality, simplicity, etc. and how they affect readability, writability, reliability, cost, etc. - Prolog - Programming as Logical deduction - Declarative, not procedural - What vs. how - First-order logic - Simple Prolog syntax - Facts and rules - Prolog variables - How Prolog satisfies a goal - Be prepared to give simple Prolog example of some simple facts and rules, and a query with variables that does something interesting (You can just recall the lecture examples, if you want).