University of California, Irvine

ICS 141

Chapter 2 Check your understanding

1)What is the difference between syntax and semantics?

2. What are the three basic operations that can be used to build complex regular expressions from simpler regular expressions? (CAK)
3. What additional operation (beyond the three of regular expressions) is provided in context-free grammars?
4. What is Backus-Naur form? When and why was it devised?
5. Name a language in which indentation affects program syntax.
6. When discussing context-free languages, what is a derivation? What is a sentential form?

7. What is the difference between a right-most derivation and a left-most derivation?
8. What does it mean for a context-free grammar to be ambiguous?
9. What are associativity and precedence? Why are they significant in parse trees?

10. List the tasks performed by the typical scanner.
11. What are the advantages of an automatically generated scanner, in comparison to a handwritten one? Why do many commercial compilers use a hand- written scanner anyway?
12. Explain the difference between deterministic and nondeterministic finite automata. Why do we prefer the deterministic variety for scanning?

13. Outline the constructions used to turn a set of regular expressions into a minimal DFA.
14. What is the “longest possible token” rule?

15. +Why must a scanner sometimes “peek” at upcoming characters?

16. What is the difference between a keyword and an identifier?
17. Why must a scanner save the text of tokens?
18. How does a scanner identify lexical errors? How does it respond?
19. What is a pragma?
20. What is the inherent “big-O” complexity of parsing? What is the complexity of parsers used in real compilers?
21. Summarize the difference between LL and LR parsing. Which one of them is also called “bottom-up”? “Top-down”? Which one is also called “predictive”? “Shift-reduce”? What do “LL” and “LR” stand for?
22. What kind of parser (top-down or bottom-up) is most common in production compilers?
23. Why are right-most derivations sometimes called canonical?
24. What is the significance of the “1” in LR(1)?
25. Why might we want (or need) different grammars for different parsing algorithms?
26. What is an epsilon production?
27. What are recursive descent parsers? Why are they used mostly for small languages?
28. How might a parser construct an explicit parse tree or syntax tree?

29. Describe two common idioms in context-free grammars that cannot be parsed top-down.

30. What is the “dangling else” problem? How is it avoided in modern languages?

31. Discuss the similarities and differences between recursive descent and table- driven top-down parsing.

32. What are FIRST and FOLLOW sets? What are they used for?
33. Under what circumstances does a top-down parser predict the production A →α?

34. What sorts of “obvious” facts form the basis of FIRST set and FOLLOW set construction?
35. Outline the algorithm used to complete the construction of FIRST and FOLLOW sets. How do we know when we are done?

36. How do we know when a grammar is not LL(1)?
37. What is the handle of a right sentential form?
38. Explain the significance of the characteristic finite-state machine in LR parsing
39. What is the significance of the dot (.) in al LR item?
40. What is a shift-reduce conflict? How is it resolved in the various kinds of LR- family parsers?