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 <T> -> <T> # <F><T> -> <T> ^ <F><T> -> <F><F> -> zWhich of the following represent the correct EBNF for the non-terminal T [1], non-terminal <F> [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] 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 <S> or simply S
S->(S)|eS->e|(S)<S>->(<S>)|e<S>->e|(<S>)
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 <term> for a modulo-division expressionS = { % }V = <term> <factor> Note Please DO NOT put a space for every non-terminal, terminal and meta symbol (e.g. | ->)non-terminals may be written as <term> or simply term
