CS606 Midterm Quiz 1 Combined

Q1. LL(1) parsing is called ___________________ parsing.

 Predictive

•  Non-predictive
•  Post-predictive
•  Post determine

Q2. One kind of predictive parser is the ______________________.

 Recursive descent parses

•  Bottom-up parser
•  Natural parser
•  Multilingual parser

Q3. Front-end of a two pass compiler consists of ____________________.

•  Code optimizer

 Scanner

•  Parser
•  Assembler

Q4. The algorithm for _____________________ conversion is called Thompson’s Construction.

•  DFA to RE

 RE to DFA

•  RE to NFA
•  CFG to NFA

Q5. ________ convert the relocatable machine into absolute machine code by linking library and relocatable object files.

•  Assembler

 Loader/link editor

•  Compiler
•  Preprocessor

Q6. The __________________ parser uses a stack to hold the frontier.

•  Top-down

 Bottom-up

•  Predicative
•  LL(1) parsers

Q7. ______________ is the process of discovering a derivation for some sentence of a language.

•  Compiling
•  Scanning

 Parsing

•  Interpretation

Q8. A ______________ accepts a string if we can follow transitions labeled with characters in the string from start state to some accepting state.

•  Regular expression
•  Regular language
•  Acceptor

Q9. The general idea behind NFA-to-DFA construction is that each _______ state corresponds to a set of _______ states.

 DFA, NFA

•  NFA, DFA
•  NFA, FA
•  CFG, NFA

Q10. Optimal registers allocation is ____________ problem.

•  NP-hard
•  Polynomial complete
•  Multinomial complete

Q11. Majority of the algorithms employed in the back-end are

•  Polynomial time
•  Np
•  None of the given

Q12. In predictive parsing table, the rows are _______________________.

 Non-terminals

•  Terminals
•  Both non-terminals and terminals
•  Neither non-terminals nor terminals