Description
Part 1: Reading and Exercises Compilers – Principles, Techniques, & Tools, 2nd Edition, Sections 4.1, 4.2, 4.3 Homework Exercises – laboratory and answer the questions at the end of the assignment.
Introduction In this assignment, you implement the language of the string (a|b)*(a|b)b(a|b) using nondeterministic (NFA) and deterministic (DFA) finite automata. You are given a main program (main.c), scanner (scan.l) and two parsers (gramNFA.y gramDFA.y) that already accept (a|b)*. You modify the two yacc files to correctly implement the grammar for the language. You test your compilers using three test programs (test1.c test2.c test3.c) with a script file (hw05_test.sh). You also implement the error production and keep track of the number of syntax errors.
Part 2: Laboratory From a console window, make a directory on your computer and call it hw05. mkdir EECS337/caseid/hw05/ ; where caseid is YOUR Case ID, enter all in lower case
Download a copy of: hw05_caseid.tar file to the hw05 directory from https://blackboard.case.edu/ in the EECS337 homework assignment area. To untar the file, type the command. tar xvf hw05_caseid.tar
The following files will be created in the current working directory. Makefile gramDFA.y gramNFA.y hw05_test.sh main.c scan.l test1.c test2.c test3.c yystype.h
Look at the test files (test1.c test2.c test3.c) and examine the input strings. The file test1.c contains one string that is accepted by the language of the string. aba
The file test2.c contains strings that are accepted by the language of the string and the last few examples have number characters embedded in the strings, which create syntax errors. aba abb bba bbb aaba … b1b2a b1b2b
The file test3.c contains four strings that are not accepted by the language of the string: aaa aab baa bab
Look at the Makefile. Notice the line with all, creates two executable versions (hw05estNFA, hw05testDFA) for testing. These two versions share the same yystype.h, main.c and scan.l files and use two different yacc files (gramNFA.y and gramDFA.y). So be sure to edit the gramNFA.y and gramDFA.y files for testing each implementation. The Makefile also copies the y.output file to either yNFA.output or yDFA.output. To build one version at a time then use one of the commands below. make hw05testNFA make hw05testDFA
Look at the hw05_test.sh Unix script file. It does a make clean and builds of both versions and then runs the same tests using the two executable versions. # # hw05_test.sh # make clean make # # test the NFA grammar # ./hw05testNFA +yydebug test1.c ./hw05testNFA test2.c ./hw05testNFA test3.c # # test the DFA grammar # ./hw05testDFA +yydebug test1.c ./hw05testDFA test2.c ./hw05testDFA test3.c
Test the hw05testNFA and hw05testDFA programs by using each of the following commands: ./hw05testNFA test1.c ./hw05testNFA test2.c ./hw05testNFA test3.c ./hw05testDFA test1.c ./hw05testDFA test2.c ./hw05testDFA test3.c
Out of the box, the output from the test files should be successful for test1.c and test3.c and a syntax error on test2.c. When you correctly implement the assignment you should have test1.c and test2.c run successfully and test3.c should give four syntax errors. Out of the box, your output should be:
./hw05testNFA test1.c for caseid start time: Thu Sep 19 07:18:20 2013 NFA A0: accept ./hw05testNFA test2.c for caseid start time: Thu Sep 19 07:18:20 2013 NFA A0: accept NFA A0: accept NFA A0: accept NFA A0: accept
NFA A0: accept NFA A0: accept NFA A0: accept NFA A0: accept NFA A0: accept NFA A0: accept NFA A0: accept NFA A0: accept NFA A0: accept
^ syntax error Error: yyparse 1 ./hw05testNFA test3.c for caseid start time: Thu Sep 19 07:18:20 2013 NFA A0: accept NFA A0: accept NFA A0: accept NFA A0: accept
You are now ready to solve the laboratory assignment.
Part 3: Laboratory Assignment Edit the main.c file and change all strings with caseid to your Case ID. Save the file.
Edit the scan.l file and add two regular expressions to pass the characters “a” and “b”. Change the dot (.) expression to return nothing. Save, build and test the files again. The syntax error from test2.c should now be eliminated because it returns only a and b to the parser and skip everything else.
Design the NFA state transition table for the string (a|b)*(a|b)b(a|b). Change the state table into an NFA grammar. Now edit the gramNFA.y file. Change the productions to implement the grammar for using non-deterministic (NFA) finite automata. The accepting state is always empty.
Build the program using the following commands: make clean make hw05testNFA
Test the hw05testNFA program by using each of the following commands: ./hw05testNFA test1.c // success ./hw05testNFA test2.c // success ./hw05testNFA test3.c // syntax error
Design the DFA state transition table for the string (a|b)*(a|b)b(a|b). Change the state table into a DFA grammar. Now edit the gramDFA.y file. Change the productions to implement the grammar using deterministic (DFA) finite automata. Remember there is only one path for each symbol out of each state in DFA and include the EOL or EOF as an input symbol.
Build the program using the following commands: make clean make hw05testDFA
Test the hw05testDFA program by using each of the following commands: ./hw05testDFA test1.c // success ./hw05testDFA test2.c // success ./hw05testDFA test3.c // syntax error
Part 4: Syntax Error Handling Edit the yystype.h file and add the variable below to the DATA structure and the extern statement to the scan.l external declarations . Save the file. int errors;
extern void yysync( void); Edit the main.c file and inside the main_exit routine replace the return 0; with the code below. Save the file. /* * check if compiler errors */ if( data.errors) fprintf( stderr, “Error: compiler errors: %d\n”, data.errors); return( data.errors);
Edit the scan.l file and add the code below at the end of the file after the %%. Save the file. /* * resync the parser with a syntax error */ void yysync( void) { int c; data.errors++; while (( c = getc( yyin )) != EOF) { if( c == ‘\n’) { unput( c); break; } } }
Edit the gramNFA.y and gramDFA.y files and add to the “line” production the error production shown below. The word “error” is a non-terminal symbol for a parser error. The function yysync is in the scan.l file to read characters to EOF or to a new line character. If it sees a new line it “unput” that character and returns. The macro “yyerrok” tells the parser to continue parsing the file. This allows the parser to resynchronize on a per line bases. Save the files. | error ‘\n’ { yysync(); yyerrok; }
Build the program using the following commands: make clean make
When the error handling code is complete and working then execute the command below. This should now continue parsing the test3.c file and generate four errors that are reported from the main_exit routine, shown below.
./hw05testNFA test3.c for caseid start time: Thu Sep 19 07:48:34 2013
^ syntax error
^ syntax error
^ syntax error
^ syntax error Error: compiler errors: 4 Error: exit: 4 Part 4 A: Laboratory Extra Credit (5 points) Notice the syntax error messages do not include any previous string information. Edit the files (yystype.h, gram[ND]FA.y, scan.l) to report a meaningful syntax error message. For example your output should look like:
./hw05testNFA test3.c for caseid start time: Mon Sep 23 07:47:44 2013
aaa ^ syntax error
aab ^ syntax error
baa ^ syntax error
bab ^ syntax error Error: compiler errors: 4 Error: exit: 4
When done, upload ONLY your scan.l file to blackboard in the assignment area. Submit it with the comments hw05 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 syntax error 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 Unix script file “./hw05_test.sh”. To redirect the standard error (stderr) and standard output (stdout) to a file use the following command: ./hw05_test.sh & hw05_test.txt
Print out the hw05_test.txt output file. Put your name, assignment number and date on it. Answer the questions at the end of the assignment.
Your final directory should look like:
EECS337/caseid/hw05/Makefile EECS337/caseid/hw05/gramDFA.y EECS337/caseid/hw05/gramNFA.y EECS337/caseid/hw05/hw05_caseid.tar EECS337/caseid/hw05/hw05_test.sh EECS337/caseid/hw05/hw05_test.txt EECS337/caseid/hw05/hw05testDFA EECS337/caseid/hw05/hw05testNFA EECS337/caseid/hw05/main.c EECS337/caseid/hw05/scan.l EECS337/caseid/hw05/test1.c EECS337/caseid/hw05/test2.c EECS337/caseid/hw05/test3.c EECS337/caseid/hw05/yDFA.output EECS337/caseid/hw05/yNFA.output EECS337/caseid/hw05/yystype.h
Part 6: Laboratory Questions
1) What happens if you remove the [\n] lex expression and action {…} from scan.l?
2) Why does test2.c generate a syntax error when you build it out of the box?
3) Why does test3.c NOT generate a syntax error when you build it out of the box?
4) After implementation, explain why one of your files (yNFA.output yDFA.output) is larger?
5) How many bytes are in your executable programs (hw05testNFA hw05testDFA)?
6) What is a reason to write your grammar in DFA over NFA inside a yacc parser?
7) In yacc, how do you define the starting state?
8) In yacc, what does an accepting state have that is not found in a transition state?
9) Write your yacc NFA productions for solving language [(a|b)*(a|b)b(a|b)].
10) Write your yacc DFA productions for solving language [(a|b)*(a|b)b(a|b)].