Laboratory Manual
                     for
                 Compiler Design
                  Robb T. Koether
        ii
                    Contents
                    I   Preliminaries                                                                       11
                    1 Getting Started                                                                        13
                             1.1     Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . .    14
                             1.2     The Cygwin Window . . . . . . . . . . . . . . . . . . . . . . .         14
                             1.3     The HOME Environment Variable . . . . . . . . . . . . . . .             15
                             1.4     The Java Development Kit . . . . . . . . . . . . . . . . . . . .        16
                             1.5     Running Java Programs . . . . . . . . . . . . . . . . . . . . .         16
                             1.6     The Java API . . . . . . . . . . . . . . . . . . . . . . . . . . .      17
                             1.7     The JLex Java-based Lexical Analyzer Generator . . . . . . .            17
                             1.8     The CUP Java-based Parser Generator . . . . . . . . . . . . .           19
                             1.9     Zipping Files    . . . . . . . . . . . . . . . . . . . . . . . . . . .  21
                             1.10    Assignment . . . . . . . . . . . . . . . . . . . . . . . . . . . .      21
                    II    Lexical Analysis                                                                  23
                    2 Writing a Lexical Analyzer                                                             25
                             2.1     Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . .    25
                             2.2     Makefiles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .    26
                             2.3     Running the Lexer . . . . . . . . . . . . . . . . . . . . . . . .       27
                             2.4     Understanding the Lexer . . . . . . . . . . . . . . . . . . . . .       28
                             2.5     Assignment . . . . . . . . . . . . . . . . . . . . . . . . . . . .      28
                    3 ALexical Analyzer using JLex                                                           31
                             3.1     Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . .    31
                             3.2     JLex . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .    32
                                                                 1
                    2                                                                            CONTENTS
                             3.3     The Err and Warning Classes . . . . . . . . . . . . . . . . . .         33
                             3.4     The Token Class . . . . . . . . . . . . . . . . . . . . . . . . .       34
                             3.5     Invoking the Lexer . . . . . . . . . . . . . . . . . . . . . . . .      34
                             3.6     Building the Lexical Analyzer . . . . . . . . . . . . . . . . . .       34
                             3.7     The Makefile . . . . . . . . . . . . . . . . . . . . . . . . . . .       35
                             3.8     Assignment . . . . . . . . . . . . . . . . . . . . . . . . . . . .      36
                    III    Syntactic Analysis                                                               39
                    4 ARecursive-Descent Parser                                                              41
                             4.1     Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . .    41
                             4.2     Modify the Lexical Analyzer . . . . . . . . . . . . . . . . . . .       42
                             4.3     The Recursive-Descent Parser . . . . . . . . . . . . . . . . . .        42
                             4.4     Derivations and Parse Trees . . . . . . . . . . . . . . . . . . .       44
                             4.5     Improving the Parser . . . . . . . . . . . . . . . . . . . . . . .      45
                             4.6     Assignment . . . . . . . . . . . . . . . . . . . . . . . . . . . .      45
                    5 Using JLex with a Predictive Parser                                                    47
                             5.1     Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . .    47
                             5.2     Lexer-Parser Interface    . . . . . . . . . . . . . . . . . . . . . .   48
                             5.3     The Productions . . . . . . . . . . . . . . . . . . . . . . . . .       49
                             5.4     The Parse Table . . . . . . . . . . . . . . . . . . . . . . . . . .     50
                             5.5     The Parsing Algorithm . . . . . . . . . . . . . . . . . . . . . .       51
                             5.6     Running the Program       . . . . . . . . . . . . . . . . . . . . . .   52
                             5.7     Expand the Grammar . . . . . . . . . . . . . . . . . . . . . .          53
                             5.8     Assignment . . . . . . . . . . . . . . . . . . . . . . . . . . . .      53
                    6 Using JLex and CUP                                                                     55
                             6.1     Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . .    56
                             6.2     Modifying the JLex File . . . . . . . . . . . . . . . . . . . . .       56
                             6.3     The Symbol Class . . . . . . . . . . . . . . . . . . . . . . . . .      57
                             6.4     The CUP File . . . . . . . . . . . . . . . . . . . . . . . . . . .      58
                             6.5     The Grammar . . . . . . . . . . . . . . . . . . . . . . . . . . .       58
                             6.6     Shift/Reduce Conflicts . . . . . . . . . . . . . . . . . . . . . .       60
                             6.7     Semantic Actions . . . . . . . . . . . . . . . . . . . . . . . . .      61