EXERCISES

1. Why do we use separate Scanner and parser in a compiler? Can the parser not do both the jobs?
2. Why in the Scanner shown in Section 3.2 the symbols like ‘=’ do not appear in the Symbol Table?
3. Implement a lex based Scanner for the simple language discussed in Chapter 2. Compare it against the hand-coded C language implementation given there, in terms of the size of the programs and ease of developing the Scanner.
4. Implement lex based Scanners for all the examples for regular expressions given in this chapter.
5. If you are familiar with Perl or Python language, try to implement the Scanner for the simple language given in Chapter 2 in that language. Compare with the hand-coded C Scanner.
6. Can you implement a compiler for a programming language using only lex as the tool? What problems, if any, would you face? Hint: Look up the theory of Pumping Lemma for FSM and CFG in Appendix A.
7. Implement for C the error handling as suggested in Section 3.4.
8. Write regular expressions for the following languages over the alphabet Σ = {0,1}:
   1. All strings that do not end with 00.
   2. All strings that contain an even number of 1s.
   3. All strings which do not contain the substring 10.
9. Draw DFAs for each of the languages from the above exercise.
10. Consider the following deterministic finite automaton (DFA) over the alphabet Σ = {0,1}.

     

    

     

    Give a one-sentence description of the language recognized by the DFA. Write a regular expression for this language.
11. For each of the following specifications written in lex/Flex, give a regular expression describing the language of possible outputs. Assume that all inputs are strings consisting of characters a, b, A and B.
    1. Specification 1:

       [aA]                { printf(″x″); }
       [aA] [aA]           { printf(″y″); }
       [bB]                { printf(″z″); }
       

    2. Specification 2:

       ([aA]+)([bB}+)      { printf(″a″); }
       [aA]                { printf(″b″); }
       [bB]                { printf(″c″); }