The following deals with questions/answers you may encounter when asked about:
- Lexical and Syntax Analysis
- Names, Bindings and Scopes
- Data Types
1. What are the 3 approaches to implementing programming languages?
- Compilation, Pure Interpretation and Hybrid Implementation
2. What is the job of the syntax analyzer?
- Check the syntax of the program and create a parse tree.
3. What are the syntax analyzers based on?
- Formal description of the syntax of programs, usually BNF.
4. What are some of the advantages of using BNF?
- Descriptions are clear and concise.
- Descriptions are clear and concise.
- Syntax analyzers can be generated directly from BNF.
- Implementations based on BNF are easy to maintain.
5. What are the 2 distinct parts of syntax analysis and what
do they do?
- Lexical analysis: deals with small-scale language
constructs such as names
- Syntax analyzer: deals with large-scale constructs such as
expressions
6. What are the 3 reasons for why lexical analysis is separated from syntax analysis?
- Simplicity, Efficiency and Portability
7. What does the lexical analyzer do?
- Collects input characters into groups (lexemes) and assigns an internal code (token) to each group.
8. How are lexemes recognized?
- By matching the input against patterns.
9. What are some other tasks that are performed by the lexical analyzer?
- Skipping comments and white spaces between lexemes
- Inserting lexemes for user-defined names into the symbol table.
- Detecting syntactic errors in tokens.
10. Name the three approaches that can be used to build a lexical analyzer.
- Write a formal description of the token patterns of the language and use a software tool to automatically generate a lexical analyzer.
- Design a state transition diagram that describes the token patterns of the language and write a program that implements the diagram.
- Design a state transition diagram that describes the token patterns of the language and hand-construct a table-driven implementation of the state diagram.
11. A state transition diagram, or _________ diagram, is a directed graph.
- state
12. A state transition diagram, or state diagram, is a _______ graph.
- directed
13. Describe a state diagram.
- Nodes are labeled with state names
- The arcs are labeled with input characters
- An arc may also include actions to be done when transition is taken.
14. Syntax analysis is often referred to as _________.
- parsing
15. What are the responsibilities of a syntax analyzer?
- Determine if input program is syntactically correct.
- Produce a parse tree.
16. What must a parser do when an error is found?
- Produce a diagnostic message and recover.
17. Why is recovery used?
- So that the compiler finds as many errors as possible as quickly as possible.
18. How are parsers categorized?
- According to the direction in which they build parse trees.
19. What are the two different parser categories?
- Top-down
- Bottom-up
20. Describe a top-down parser.
- Builds a tree from thee root down to the leaves
21. Describe a bottom-up parser.
- Builds a tree from the leaves up to the root.
22. A top-down parser traces or builds the parse tree in _________.
- preorder
23. What does it mean when a top-down parser traces the parse tree in preorder?
- Each node is visited before its branches are followed.
24. The actions taken by at top-down parser correspond to a _________ derivation.
- Leftmost
25. A ________ _________ parser is coded directly from the BNF description of the syntax language.
- recursive descent
26. What is an alternative to using a recursive-descent parser?
- Using a parsing table
27. Both parsing tables and recursive-descent parsers are _______ __________.
- LL algorithms.
28. What does LL stand for in LL algorithm?
- First L: specifies a left-to-right scan of the input
- Second L: specifies that a leftmost derivation is generated
29. A given right sentential form may include more than one RHS from the grammar. The correct RHS to reduce is called the _________.
- handle
30. The most common bottom-up parsing algorithms are in the ___ family.
- LR
31. What does LR stand for in the LR algorithm?
- L: left-to-right scan
- R: rightmost derivation is generated
32.
What is the Big O for parsing algorithms that work for any grammar?
- O(n3)
- O(n3)
33. What is the Big O for parsing algorithms that are used in commercial applications?
- O(n)
34. How does a recursive-descent parser produce a parse tree?
- In top-down order
35. A recursive-descent parser has one subprogram for each ___________ in the grammar.
- nonterminal
36. _____ is ideally suited for describing recursive-descent parsers.
- EBNF
37. ______ __________ causes a catastrophic problem for LL parsers.
- Left recursion
38. The left recursion in the rule A → A + B is called _______ _________ _________.
- direct left recursion
39. True or False? Direct Left Recursion occurs in one rule.
- True
40. What does the ε symbol represent?
- empty string
41. A rule that has ε as its RHS is called an ______ ______.
- erasure rule
42. Why is the erasure rule called that?
- Because using it in a derivation effectively erases its LHS from the sentential form.
43. The _____ _______ ________ is used to test a non-left-recursive grammar to determine whether it can be parsed in a top-down fashion.
- pairwise disjointness test
45. What does the pairwise disjointness test compute?
- FIRST sets
46. Is left-recursion acceptable for bottom-up parsers?
- Yes
47. A bottom-up parser produces the _____ of a rightmost derivation by starting with the last sentential form (input sentence) and working back to the start symbol.
- reverse
48. In each step of the bottom-up parser, the parser’s task is to find the ____ in the current sentential form that must be rewritten to get the previous sentential form.
- RHS
49. True or False? A right sentential form may include more than one RHS.
- True. i.e. The right sentential form E + T * id includes three RHSs, E + T, T, and id.
50. What is the task of a bottom-up parser for a given right sentential form?
- to find the unique handle
51. What is a phrase?
- A string consisting of all the leaves of the partial parse tree that is rooted at one particular internal node of the whole parse tree.
52. What is a simple phrase?
- A phrase that is derived from a nonterminal in a single step.
53. The handle of a right sentential form is the ________ ________ phrase.
- leftmost simple
54. Bottom up parsers are often called ____ ______ algorithms.
- shift reduce
55. Why are bottom up parsers often called shift-reduce algorithms?
- Because shift and reduce are their two fundamental actions
56. What does the shift action do in a shift-reduce algorithm?
- Moves the next input token onto the parser’s stack.
57. What does the reduce action do in a shift-reduce algorithm?
- Replaces the RHS (the handle) on top of the parser’s stack by its corresponding LHS.
58. Most bottom-up parsers belong to the ___ family.
- LR
59. What do LR parsers use?
- A small amount of code and a parsing table
60. What was the name of the original LR algorithm that was produced by Donald Knuth?
- canonical LR algorithm
61. Why was the canonical LR algorithm not widely used?
- It required large amounts of computer time and memory to produce a parsing table
62. What are some of the advantages of LR parsers?
- Can be built for all programming languages
- Can detect syntax errors as soon as possible
- LR class of grammars is a proper superset of the class parsable by LL parsers.
63. True or False? It’s easy to produce an LR parsing table by hand.
- False
64. How are LR parsing tables normally produced?
- Using software that takes a grammar as input and produces the parsing table
65. True or False? The LR parser can avoid examining the entire stack if it keeps a summary of the stack contents in a “state” symbol on top of the stack.
- True
66. What does the dollar sign represent in the LR parser configuration?
- End-of-input marker
67. The LR parsing process is based on the parsing table, which has two parts, _____ and _____.
- ACTION and GOTO
68. What does the parse table specify?
- What the parser should do
69. How does the parse table specify what the parser should do?
- Based on the state symbol on top of the parse stack and the next input symbol
70. Besides shift and reduce, what are the two other actions possible in a parse table and what do they do?
- Accept (parsing is complete) and error (a syntax error has been detected)
71. What do the values in the GOTO part indicate?
- Which state symbol should be pushed onto the parse stack after a reduction has been completed.
72. Describe the shift parser action.
- The next input symbol is pushed onto the stack along with the state symbol specified in the ACTION table.
73. Describe the reduce parser action.
- First, the handle is removed from the stack.
- Next, the number of symbols removed is twice the number of symbols in the handle.
- Next, the LHS of the rule is pushed onto the stack.
- Finally, the GOTO table is used to determine which state must be pushed onto the stack.
74. Describe the accept parser action.
- The parse is complete and no errors were found
75. Describe the error parser action.
- The parser calls an error-handling routine.
76. In imperative programming languages, what is a variable?
- A variable is an abstraction of the von Neumann architecture’s memory cells.
77. How can a variable be characterized?
- By a collection of attributes: Name, Address, Value, Type, Scope and Lifetime
78. True or False? In functional programming languages, once a name is created it can be changed.
- False
79. Names are also called _______.
- Identifiers
80. Why are names also called identifiers?
- Because they are used to identify a variable, a function, class or other program constructs.
81. Fortran I names had a maximum name length of _____.
- Six
82. COBOL names had a maximum length of ______.
- 30
83. Name two languages that don’t have a name length limit.
- Java and C#
84. How are scalar, arrays and hash names defined in Perl?
- $, @ and %
85. What do the @ and @@ symbols represent in Ruby?
- Class Instance and Class Object
86. What is a keyword?
- A word that’s special only in certain context
87. What is a reserved word?
- A special word that cannot be used a user-defined name.
88. True or False? Keywords can be overwritten by user-defined names.
- True
89. What is a variable?
- An abstraction of memory
90. What does the address variable characteristic represent?
- The memory address with which the variable is associated with
91. What does the following variable characteristic represent: value?
- The contents of the location with which the variable is associated.
92. True or false? A variable may have different addresses at different times during execution.
- True
93. If two variable names can be used to access the same memory location, they are called _______.
- aliases
94. How are aliases created?
- Pointers and reference variables
95. What does the variable’s type determine?
- The range of values of the variable
- The set of operations for that type
- The precision
96. What is an abstract memory cell?
- Way of thinking about the physical cell or collection of cells associated with a variable
97. A ________ is an association, such as between an attribute and an entity, or between an operation and a symbol.
- binding
98. The ______ ______ is the time at which a binding takes place.
- binding time
99. Describe what takes place during the language design time.
- Program structure (syntax)
- Primitive types and meanings (semantics)
- i.e. binding of * to the multiplication operator
100. Describe what takes place during the language implementation time.
- Coupling of I/O to OS
- Maximum sizes of stack of heap
- Precision of fundamental types
- i.e. binding of floating type to an internal representation in C
101. Describe what takes place during the compile time.
- Map high-level language constructs to machine code.
- i.e. binding of a variable to a particular type in C or Java
102. Describe what takes place during the link time
- Multiple object codes (machine code files) and libraries are combined into one executable
- i.e. binding a library subprogram to subprogram’s code
103. Describe what takes place during load time.
- OS loads the executable in memory
- Assign machine addresses to static data
- i.e. binding of a C static variable to a memory cell
104. Describe what takes place during run time.
- The time during which a program runs
- i.e. bindings of non-static variables in a subprogram to a memory cell.
105. A binding is ______ if it first occurs before run time and remains unchanged throughout program execution.
- static
106. A binding is ______ if it first occurs during execution or can change during execution of the program.
- dynamic
107. Before a variable can be referenced in a program, it must be bound to a ____ _____.
- data type
108. Give an example of an explicitly declared static type binding.
- int i;
109. Give an example of an implicitly declared static type binding.
- Fortran: I, J, K, L, M, N implicitly declare to be integer type.
110. True or False? Type inference is a way to implicitly declare a binding.
- true (i.e. var sum = 0; or var total = 0.0;)
111. True or False? Dynamic Type Binding uses declarations.
- False
112. Give an example of dynamic type binding.
- apple = “Apple”;
apple = 17.3;
113. What is allocation?
- The binding of a variable to a memory cell that is taken from a pool of available memory.
114. What is deallocation?
- the process of unbinding a variable and placing the memory cell back in the pool of available memory.
115. What is the lifetime of a variable?
- The time during which the variable is bound to a specific memory location.
116. What are the four categories of variables by lifetime?
- Static, stack-dynamic, explicit heap-dynamic and implicit heap-dynamic
117. What are the 3 main areas in memory that are allocated for variables?
- Static area, stack and heap
118. True or False? Static variables are bound to memory cells before program execution begins and remain bound to those same memory cells until termination.
- True
119. What is the lifetime of a static variable?
- Entire program execution
120. Static variables can be used as global variables and ____ _____ variables.
- history sensitive
121. True or False? In early Fortran, all variables were static.
- True
122. True or False? In C and C++, global variables are always static.
- True
123. Describe what is meant by a history sensitive variable.
- local variables that are declared static
124. True or False? A program that has only static variables can support recursive subprograms.
- False
125. In stack-dynamic variables, the type is ______ bound.
- statically
126. In stack-dynamic variables, the storage is bound when their declarations are _______.
- elaborated
128. What is meant by elaboration in declarations?
- the storage allocation and binding process that takes place when the code containing the declaration is executed.
129. Stack dynamic variables are allocated from the _____ _____ _____.
- run time stack
130. True or False? Programming languages that allow stack-dynamic variables allow recursion.
- True
131. For stack-dynamic variables the size of local variables is determined at _____ time.
- run
132. True or False? Stack-dynamic variables are history sensitive.
- False
133. What is the heap?
- Unstructured pool of memory cells
134. What is the lifetime of explicit heap-dynamic variables?
- from explicit allocation to explicit deallocation
135. The explicit heap-dynamic variables can only be accessed through ________ or ______ variables.
- pointer or reference
136. Explicit heap-dynamic variables are created either by an _______ or a call to a ______ _______.
- operator (new in C++) or library function (malloc in C)
137. Objects in Java are ______ heap-dynamic and are accessed through _______ variables.
- explicit
- reference
138. Java relies on ______ _______ to destroy a heap-dynamic variable.
- garbage collection
139. In C#, explicit heap-dynamic and stack-dynamic objects are _______ deallocated.
- implicitly
140. When are implicit heap-dynamic variables bound to heap storage?
- when they are assigned values
141. What is the lifetime of implicit heap-dynamic variables?
- from implicit allocation to implicit deallocation
142. What is the scope of a variable?
- the range of the statements in which the variable is visible
143. A variable is _____ if it can be referenced.
- visible
144. What is a local variable?
- a variable declared in a program unit (subprogram) or block.
145. What is a nonlocal variable?
- a variable visible in a program unit or block, but not declared there.
146. What is a global variable?
- a special category of nonlocal variables
147. What is static scoping?
- the scope of a variable can be determined prior to execution at compile time
148. What is dynamic scoping?
- the score of a variable is determined at run time.
149. Static scope is sometimes referred to as _____ ______.
- lexical scope
150. True or False? In languages that use static scoping, variable declarations can be hidden.
- True
151. Variables within a block are typically _____ _______.
- stack dynamic
152. In python a global variable can be referenced in a function, but it can be modified there only if the function has declared it to be _____.
- global
153. True or False? Dynamic scope is based on the order in which subprograms are called, not their nesting.
- True
154. True or False? Scope and Lifetime are different concepts?
- True
155. What is the referencing environment of a statement?
- the collection of all names that are visible in the statement.
156. What is an active subprogram?
- Execution of the subprogram has begun and in not yet terminated.
157. What is a named constant?
- A variable that is bound to the same value throughout its lifetime
158. True or False? The binding of values to named constants can only be static.
- False. It can be static or dynamic
159. The binding of a variable to a value at the time it is bound to storage is called _______.
- initialization
160. What does a data type define?
- A collection of values and a set of operations on those values.
161. True or False? In the early languages, all data structures had to be simulated with arrays.
-True
162. ______ _______ ______ were one of the most important advances and paved the way for abstract data types, classes and object-orientation.
- User-defined types
163. Data types are either _____ or ______ (scalar).
- structured or unstructured
164. What is a variable descriptor?
- The collection of attributes of a variable
165. What are descriptors used for?
- Type checking and allocation and deallocation operations.
166. Data types that are not defined in terms of other types are called _____ ____ _____.
- primitive data types
167. ______ is the most common primitive numeric type
- Integer
168. What are the four signed integer types provided by Java?
- byte, short, int and long
169. True or False? C++ and C# have unsigned integer types.
- True
170. What are the three ways to store negative integers?
- Sing magnitude notation, two’s complement notation and one’s complement notation
171. What are the two floating-point types included in most Programming Languages?
- float and double
172. Most larger computers that are designed to support business applications have hardware support for _____ data types.
- decimal
173. True or False? C89 has a Boolean type
- False
174. How is the Boolean type represented in C89
- nonzero numbers are true and zero is false
175. True or False? C99 and C++ have a Boolean type
- True
176. True or False? The Boolean type is stored in one bit.
- False, one byte since the byte is the lowest retrievable storage unit.
177. _____ was the first widely used language to use the Unicode character set.
- Java
178. True or False? Python has a character type.
- False, instead characters are treated as strings of length 1
179. Name a few of the most common string operations.
- Assignment, Catenation, Substring Reference, comparison and pattern matching
180. How are character strings stored in C and C++?
- char arrays
181. How do you mark the end of a string in C?
- With the null character
182. In Java, strings are supported by two classes: _____ and ______.
- String and StringBuffer
183. True or False? Java’s String class is mutable.
- False. StringBuffer is mutable.
184. True or False? In Python, string is a primitive type and strings are immutable.
- True
185. Pattern matching in Perl, JavaScript, Ruby and PHP is based on _______ ________.
- regular expressions
186. What is a static-length string?
- the length of a string is fixed (i.e. Java’s String object)
187. What is a limited dynamic-length string?
- the length of a string can vary up to a declared and fixed maximum set by the variable’s definition.
188. What is a dynamic-length string?
- the length of a string can vary with no maximum
189. What is an enumeration type?
- specifies all possible values of the type by providing a list of enumeration constants.
190. ____ and ______ were the first widely used languages to include an enumeration data type.
- C and Pascal
191. Is the following example a legal operation on this C++ enumeration type? myColor=4;
- No, but casting would make it legal (i.e. myColor=(colors) 4;
192. True or False? In Java, enumeration constants are instances of the class.
- True
193. A Java enumeration is implicitly a ______ of the Enum class.
- subclass
194. True or False? A Java enumeration inherits methods from the Enum class.
- True
195. What does the ordinal method do?
- Returns the numeric value of an enumeration object.
196. True or False? PHP and JavaScript inherit from the Enum class.
- False, PHP and JavaScript do not have enumeration types at all.
197. What are the two properties of an array data structure?
- All elements have the same type
- Elements are accessed by position relative to first element
198. References to an array element are specified using __________ ___________.
- subscript expressions
199. How are array elements accessed?
- by giving the name of the array and a selector that specifies the position of the element
200. The position of an element is specified by ________ or ___________.
- subscripts or indices
201. What are the two distinct types involved in an array type?
- element type and type of the subscripts
202. The type of the subscript is often _______.
- integer
203. In Perl, array names should begin with _____ but the _____ is used when accessing an element in an array.
- @
- $
204. True or False? Negative subscripts are allowed in Perl.
- True
205. A reference to a nonexistent array element in Perl yields _____.
- undef
206. The binding of the subscript type to an array variable is usually ______.
- static
207. True or False? The lower bound of the subscript range is often implicit.
- true
208. What are the five categories that arrays can be divided into?
- Static, Fixed stack-dynamic, stack-dynamic, fixed-heap dynamic and heap-dynamic
209. What is a static array?
- when subscript ranges are statically bound and storage allocation is static
210. Arrays declared in C & C++ functions that include the _____ modifier are static.
- static
211. What is a fixed stack-dynamic array?
- Subscript ranges are statically bound but the allocation is done at declaration time. Use a static modifier and a fixed size.
212. What is a stack-dynamic array?
- Subscript ranges are dynamically bound, and the storage is dynamically allocated.
213. What is a fixed heap-dynamic array?
- Subscript ranges are dynamically bound, and the storage allocation is dynamic, but they are both fixed after storage is allocated. Storage is allocated on the heap. i.e. malloc and free in C or new in C++
214. True or False? In Java all arrays are fixed heap dynamic arrays.
- True, once created they keep the same subscript ranges and storage
215. What is a heap-dynamic array?
- subscript ranges are dynamically bound, and the storage allocation is dynamic, and can change any number of times during the array’s lifetime. i.e. C#’s ArrayList class or JavaScript arrays
216. A reference to a nonexistent element in a JavaScript array yields _______.
- undefined
217. Arrays of string can be initialized by a list of _____ ______.
- string literals
218. True or False? When an initializer is present, the length of the array can be omitted.
- True
219. True or False? An array operation is performed on a single array element.
- False, it’s performed on an entire array.
220. A true multidimensional array is called a _________ __________.
- rectangular array
221. What is a jagged array?
- Lengths of rows are not the same
222. True or False? Java supports rectangular arrays
- False, only jagged arrays
223. True or False? Multidimensional arrays must be mapped onto the linear structure of the computer memory.
- True
224. What are the two common ways to map multidimensional arrays onto the linear structure of the computer memory?
- Row-major order and column-major order
225. What is the access function of a one-dimensional array?
- address(list[k]) = address(list[0]) + k * element_size
Comments
Post a Comment