Description
Part 1: Reading Compilers – Principles, Techniques, & Tools, 2nd Edition, Sections 4.5, 4.6, 4.9 Homework Exercises – problem 4.5.3 (b) and laboratory assignment.
Introduction An example of a math calculator program (interpreter) using lex (first.l) and yacc (second.y) is found on page 295-296 of your book. You implement and test the program using the commands: lex first.l yacc second.y cc y.tab.c -ly –ll ./a.out ./a.out < math0.txt The first command creates a lex.yy.c file. The second command creates a y.tab.c file. The third line compiles the y.tab.c file into an executable file (a.out). You run the executable program with the forth command and enter a string from the console. If you enter a string (1e1+1e2) and hit return, you will get an output result (110) printed to the screen. To exit the program you must use CTRL-C to terminal the program. The fifth line shows redirecting a file to the executable to test the program and terminates when it see the end of file (EOF) character.
The way the source code from the book is formatted, lex.yy.c file from the first line is included in the bottom of the yacc (second.y) file. This is why it is not included in the third line as a separate file to compile and link. If you change the first.l file you must execute the first three commands in sequence again. It is easier to use a make file (Makefile) to compile and link each file independently. We also would like to include a main program (calc.c) so we can initialize the compiler/interpreter before calling the yacc parser (yyparse).
In this assignment you change the implementation of the math operators (+ - * /) from using a double (8 bytes) type to using a long double (16 bytes) type. Then you add the bitwise operators (& | ^ % ~), which require integer types (long long). You update the YYSTYPE structure to handle integer and floating-point numbers. You will need to handle constant type conversion for the bitwise operators. For extra credit you remember the constant format (floating point, decimal, octal, hexadecimal) for correctly displaying the output result (0xff & 0x0f - 0x0f).
For encoding integer and floating-point numbers you replace the (first.l) lex regular expression for number to use the expressions from the ansi_c compiler (shown below). number [0-9]+\e.?|[0-9]*\e.[0-9]+ %% {number} { sscanf( yytext, "%lf", &yylval); return NUMBER; } 0[xX]{H}+{IS}? // hex 0{D}+{IS}? // octal {D}+{IS}? // decimal {D}+{E}{FS}? // float {D}*"."{D}+({E})?{FS}? // float {D}+"."{D}*({E})?{FS}? // float
Laboratory Assignment
In this assignment you encode the numbers using lex regular expressions and the C sscanf() function into a static YYSTYPE data structure. You update the current lex scanner to add lex regular expressions to encode integers (decimal, octal, hexadecimal) and floating-point numbers. You then expand the math operators (+ - * /) to include the bitwise instructions (| ^ & % ~) operators. You add action code to manually handle the operand types in the parser to maintain the correct operand type.
In the calculator program the parser uses the yacc precedence operators (%left %right %prec). The precedence statements are normally located in the top of the yacc file (second.y) just below the %token statements. The precedence is defined from lower to higher precedence going down the page. The binary operators are referenced to the left (a op b) and the unary operators are referenced to the right (op b). For example: (-2+3) where minus (unary) is applied first and then plus (binary) is used next ((-2)+3).
The book version of the calculator program supports double as the yylval data type and only returns floating point numbers (1e1). The parser is designed to handle a syntax error and to resynchronize at the end of line (‘\n’). Look at the second.y file and see “lines” is defined as an expression, error or empty line. The action yyerrok clears the error and allows the parser to continue processing the input stream. The version shown below is slightly different than the version shown on page 296 and removes the extra productions. We would like one place to handle the output result. lines : lines expr '\n' { printf("%g\n", $2); } | lines error '\n' { yyerror(" reenter previous line: "); yyerrok; } | /* empty */ ; In this assignment you redefined YYSTPE to using a structure definition to hold type information, INTEGER and FLOAT values. This changes the size of the yacc stack from a single scalar value to a larger structure definition. So while the size of the yacc stack is bigger in this implementation it does provide direct memory references for increased speed compared to dynamic address pointer implementations (indirect addresses). The math operators (op) already included are: '+' addition '-' subtraction '*' multiple '/' divide '-' unary minus The new logical bit-wise operators are: '|' IOR '^' XOR '&' AND '%' MOD '~' NOT (unary)
You code the parser actions to support the correct data types. For the math instructions, if all the input operands are INTEGER then the result is an INTEGER. If any of the operands are a FLOAT then the result is a FLOAT. The data conversion methods are shown below for the math operators. INTEGER = INTEGER op INTEGER FLOAT = FLOAT op INTEGER FLOAT = INTEGER op FLOAT FLOAT = FLOAT op FLOAT INTEGER = op INTEGER FLOAT = op FLOAT
For the logical bit-wise operators all the FLOAT input operands need to be converted into INTEGER and the results is always an INTEGER. The data conversion methods are shown below for the bit-wise operators.
INTEGER = INTEGER op INTEGER INTEGER = FLOAT op INTEGER INTEGER = INTEGER op FLOAT INTEGER = FLOAT op FLOAT INTEGER = op INTEGER INTEGER = op FLOAT
To achieve maximum execution speed the YYSTYPE data structure is defined using a static structure definition and the math and logic operations are coded directly in-line. The actions could be coded into just a few functions to optimize on space. The trade-off for increased speed is more source code to maintain and gives a larger executable image. This model allows yacc programs to be used in soft real time applications such as interpreters and processing stages in routers and communication systems. In this assignment you shall implement the functions to encode constant values in the scanner. You should be able to support: integers (ddd), octal (0ooo), hexadecimal (0xhhh), and floatingpoint numbers (d.de-d). The current version defined in the code supports only floating-point numbers (math0.txt). Part 2: Laboratory From a console window, make a directory on your computer in your EECS337 directory under your Case ID and call it hw06. mkdir ~/EECS337/caseid/hw06/ ; where caseid is YOUR Case ID, enter all in lower case
Change directory to the hw06 directory. cd ~/EECS337/caseid/hw06/
Download a copy of: hw06_caseid.tar file to the hw06 directory from https://blackboard.case.edu/ from the EECS337 homework assignment area. To untar the tar file type the command: tar xvf hw06_caseid.tar
The following files will be created in the current working directory. book/book.sh book/first.l book/second.y calc.c first.l hw06_test.sh Makefile math0.txt math1.txt math2.txt math3.txt math4.txt math5.txt math6.txt math7.txt math8.txt math9.txt second.y yystype.h
The book subdirectory contains the original software from the book. In the current directory the software has been updated to use a make file, moves the YYSTYPE definition into the yystype.h file, adds a main function and adds the yyerrror and yywrap functions. Type the following commands to see the differences between the starting templates and original book version. diff first.l book/ diff second.y book/
[Optional] You can change directory into the book directory and run the book.sh file to compile, link and test the original version of the software (math0.txt). cd book/ ./book.sh cd ..
Look at the test files (math*.txt) and examine the input strings. The first file uses expressions with strings that should work with the original software. The others create syntax errors.
Look at the calc.c file. This is the main program and calls into yyparse. This version is not the same as used before in the previous assignments. Only the +yydebug flag works for debugging.
Look at the yystype.h file. Notice the book defines YYSTYPE as a double at the top of the yacc file. This version defines YYSTPE as a double inside the yystype.h file.
Look at the first.l file and notice the include files at the top of the file. The yywrap function is included at the bottom of the file.
Look at the second.y file and notice the include files at the top of the file. The yyerror function is included at the bottom of the file.
Build the calculator compiler (interpreter) calc by using the commands: make clean and make
To test this version of the calculator program from the command line type: ./calc and enter a math expression: 13e1+1e2 You should get the result (230) printed to the standard output. Notice on a syntax error the software does not exit: 2+3 To exit, type on the command line: $
To test with yydebug statements type: ./calc +yydebug and enter a math expression as before.
To test with the first example file type: ./calc < math0.txt Your output should be: for caseid start time: Mon Sep 30 09:54:13 2013 SIZEOF int: 4 INTEGER: 8 INTEGER INTEGER: 8 float: 4 FLOAT: 8, INTEGER FLOAT: 16 Enter calculator expression and $ to exit 230 6000 -170 0.15 170 -230 6000 -6000 6000.15 On $ or EOF the program exits. You are now ready to solve the laboratory assignment.
Part 3: Laboratory Assignment You will edit the current version that supports double numbers with math operations to include long long and long double values. You use type in the structure to know which value is encoded.
Edit calc.c and change all caseid to your Case ID and save the calc.c file.
Edit yystype.h and change the YYSTYPE to a structure definition to support long long and long double. /* * define yystype */ #define YYSTYPE struct yycalc YYSTYPE { int type; // holds INTEGER or FLOAT from %token long long lvalue; // holds INTEGER value long double dvalue; // holds FLOAT value }; Save the yystype.h file. Edit the lex.l file and remove the number definition. Then add to the top the lex macro definitions from the ansi_c compiler (hw03 scan.l). Insert this code before the first %{ as shown below. D [0-9] L [a-zA-Z_] H [a-fA-F0-9] E [Ee][+-]?{D}+ FS (f|F|l|L) IS (u|U|l|L)* Then between the %%s remove the lex expression {number} and action for NUMBER and insert the code below. This action encodes a hexadecimal string into the lvalue of the yylval structure. 0[xX]{H}+{IS}? { sscanf( yytext, "%Lx", &yylval.lvalue); yylval.type = INTEGER; return( INTEGER); } Then add action code to the regular expression shown below to support octal (%Lo), decimal (%Ld) and the three floating-point (%Lf) numbers. For the integer types use INTEGER for the type and return INTEGER. Encode the floating-point numbers into the dvalue field (&yylval.dvalue) and set the type to FLOAT and return the FLOAT value. 0{D}+{IS}? {D}+{IS}? {D}+{E}{FS}? {D}*"."{D}+({E})?{FS}? {D}+"."{D}*({E})?{FS}? Save the first.l file.
Edit the second.y file and remove the %token NUMBER and replace it with two new tokens. %token INTEGER %token FLOAT Change the precedence operators to include the logical bitwise operators. %left '|' %left '^' %left '&' %left '+' '-' %left '*' '/' '%' %right UMINUS '~' /* supplies precedence for unary minus */
Change the number production with NUMBER to now be INTEGER or FLOAT. number : INTEGER | FLOAT ; Then change all the production actions to handle the new operand data types. For example replace the old line to print the output result with the code shown below. Notice you need to switch on the operand type to determine the format string to use in the printf statement. lines : lines expr '\n' { switch( $2.type) { case INTEGER: printf("%Ld\n", $2.lvalue); break; case FLOAT: printf("%Lg\n", $2.dvalue); break; } } | lines error '\n' { yyerror(" reenter previous line: "); yyerrok; } | /* empty */ ; Remove and replace all the actions for the math operators and add the bitwise operators to handle the INTEGER and FLOAT operand types. One method is shown below. Notice the action is to switch on both of the operand types and type cast the values before the operations. Save the second.y file. | expr '-' expr { switch( $1.type) { case INTEGER: switch( $3.type) { case INTEGER: $$.type = INTEGER; $$.lvalue = $1.lvalue - $3.lvalue; break; case FLOAT: $$.type = FLOAT; $$.dvalue = (long double)$1.lvalue - $3.dvalue; break; } break; case FLOAT: switch( $3.type) { case INTEGER: $$.type = FLOAT; $$.dvalue = $1.dvalue - (long double)$3.lvalue; break; case FLOAT: $$.type = FLOAT; $$.dvalue = $1.dvalue - $3.dvalue; break; } break; } }
Test your calculator program using each of the test files by typing the commands:
make clean make ./calc < ../hw06/math0.txt ./calc < ../hw06/math1.txt ./calc < ../hw06/math2.txt ./calc < ../hw06/math3.txt ./calc < ../hw06/math4.txt ./calc < ../hw06/math5.txt ./calc < ../hw06/math6.txt ./calc < ../hw06/math7.txt ./calc < ../hw06/math8.txt ./calc < ../hw06/math9.txt Part 4: Extra Credit (5 points) Edit the files again and change the code to remember the format of the constants (decimal, octal, hexadecimal, floating-point). Decide on a method to determine the output results when the inputs are not using the same format (0x0ff & 1.3 - 0x01).
Generate your output the same as in Part 5 and upload ONLY your first.l file to blackboard in the assignment area. Submit it with the comments hw06 with your CaseID on the title line. The extra credit will be graded on-line and your score will be added to your assignment score. When you generate your laboratory output file in Part 5, show the improved type format handling. Mark your output file with EXTRA CREDIT and turn in with your assignment. Part 5: Laboratory Output Generation When all your lab assignments have been completed execute the homework script file “./hw06_test.sh”. To redirect the standard error (stderr) and standard output (stdout) to a file use the following command. ./hw06_test.sh & hw06_test.txt
Print out the hw06_test.txt and put your name, assignment number, date on it and turn it in with your homework exercises.
Your final directory structure for the calc compiler should be as below (using your Case ID): EECS337/caseid/hw06/Makefile EECS337/caseid/hw06/calc EECS337/caseid/hw06/calc.c EECS337/caseid/hw06/first.l EECS337/caseid/hw06/hw06_caseid.tar EECS337/caseid/hw06/hw06_test.sh EECS337/caseid/hw06/hw06_test.txt EECS337/caseid/hw06/math0.txt EECS337/caseid/hw06/math1.txt EECS337/caseid/hw06/math2.txt EECS337/caseid/hw06/math3.txt EECS337/caseid/hw06/math4.txt EECS337/caseid/hw06/math5.txt EECS337/caseid/hw06/math6.txt EECS337/caseid/hw06/math7.txt EECS337/caseid/hw06/math8.txt EECS337/caseid/hw06/math9.txt EECS337/caseid/hw06/second.y EECS337/caseid/hw06/yystype.h