# Structure of Programming Languages Chapter 1 Flashcards Table View

 AI Conference at Dartmouth, 1956: [1],Minsky, Newell,Simon. Newell,Shaw and Simon demonstrate Logic Theorist, a reasoning program written in IPL [2] IPL had support for [3] data structures, The author wanted a language for AI projects, but not IPL: too low-level and machine-specific. Then, an IBM group (consulting McCarthy developed FLPL [1] - McCarthy[2] - Information Processing Language[3] - Linked lists A grammar that generates a sentential form that has two or more distinct parse trees, ambiguous [1] writing was used in Babylon, founded by [2].Many Babylonian clay tablets survive:poems and storiescontacts and recordsastronomymath, base[3] number system [1] - Cuneiform[2] - Hammurabi[3] - 60 A Context-Free Grammar G is a quadruple(V , S, R, S)Where:V - [1]S - [2]R - [3]S - [4] V - alphabetS - set of terminalsR - set of rulesS - start symbol [1] is a repeated application of rules. Every string derived is a [2] starting with the start symbol and ending with a [3] where all string derived is composed of all terminal symbols [1] Derivation[2] Sentential Form[3] Sentence The following are the Early tool that aid the improvement of most programming languagesAssemblers,Programming tools namely[1] discovered by John Mauchly, 1949, A-0, A-1, A-2, discovered by [2] in 1951-1953 (like macro libraries)[3] by John Backus, 1954 (interpreted) [1] Short Code[2] Grace Hopper[3] Speedcoding Given the grammar  -> # -> ^ -> -> zWhich of the following represent the correct EBNF for the non-terminal T [1], non-terminal [2] of the grammarNote Please put a space for every non-terminal, terminal and meta symbol (e.g. | ->)non-terminals should be written as T or F [1] T -> F { ( #  | ^ ) F }[2] F -> z Given the CFG:CFG G = ( V , S, R, S ) V = { S, a, b }  = { a, b } R = { S -> baSb, S -> e } L(G) is described as ? L = { w e {a,b}* / every a is in between b's} [1] A hierarchical representation of a derivation [1] Parse Tree [1] is a device reads input strings of the language and decides whether the input strings belong to the languageExample: syntax analysis part of a compiler[2] A device where one can determine if the syntax of a particular sentence is correct by comparing its to the structure [1] Recognizer[2] Generator In a CFG, the set of Rules is a finite subset of form [?]Note: E here is represented as symbol S and Xrepresents cross multiply [?]= ( V - E ) X V* [1] and context-free grammars are equivalent meta-languages well-suited for describing the syntax of programming languages. [2] is an extension of [1] that enhance its readabilityAn [3] is a descriptive formalism that can describe both the syntax and the semantics of a languageThree primary methods of semantics descriptionare Operational, axiomatic, [4] [1] BNF[2] Extended BNF[3] attribute grammar[4] denotational [1] and context-free grammars are equivalent meta-languages well-suited for describing the syntax of programming languages. [2] is an extension of [1] that enhance its readabilityAn [3] is a descriptive formalism that can describe both the syntax and the semantics of a language [1] BNF[2] Extended BNF[3] attribute grammar A simple production described by a chain of boxes (for nonterminals) and ovals (for terminals): Syntax Diagram [1] English mathematician, he is an inventor of mechanical computers:Difference Engine, construction started but not completed (until a 1991 This Engine [2], features Processing unit (the Mill)Memory (the Store)Programmable ([3])Iteration, conditional branching, pipelining, many I/O devices [1] Charles Babbage[2] Analytical Engine[3] punched cards It is a set of rules that say how to build a parse tree: Grammar Given the GrammarS -> aT | bT -> bT | cV = {S, T,a,b,c,}S = {a,b,c}Which of the following string is part of the grammar abc Every meaningful combination of primitive concepts is legal—no special forbidden combinations to remember. This refers to: orthogonality This strategy allows structured grouping of the statement, an alternative for label-oriented controls that allows goto or jump statements: Phrase-Level Control The meaning of the expressions, statements, and program units Semantics The form or structure of the expressions, statements, and program units Syntax Show a rule for generating a well balanced parenthesis. (Assume the Start symbol is S and e for empty string)Note Please do not put a space for every non-terminal, terminal and meta symbol (e.g. | ->)non-terminals may be written or simply S S->(S)|eS->e|(S)->()|e->e|() Given the GrammarS -> aT | bT -> bT | cV = {S, T,a,b,c,}S = {a,b,c}Which of the following string are part of the grammar? abcabbcabbbbbc It is a string of characters over some alphabet sentencesentenceslanguagelanguages Show an unambiguous BNF rule for for a modulo-division expressionS = { % }V =  Note Please DO NOT put a space for every non-terminal, terminal and meta symbol (e.g. | ->)non-terminals may be written as or simply term ->%|->|%term->term%factor|factorterm->factor|term%factor