Description
1. Introduction
You will be given a lexer that reads tokens from standard input. Your goal is to write, in C or C++, a program that reads all tokens from standard input by calling the lexer function getToken() and storing certain tokens in a linked list. After all tokens are read, your program will print out the content of the linked list in a specific order. The next section describes the lexer API. You also need to read the provided code in lexer.c and understand how the lexer works. You will only use the getToken() function in this project. 2. Lexer API There are two functions that the lexer defines. These two functions compose the application programming interface (API) of our lexer. These functions are declared in lexer.h (and implemented in lexer.c ). You will find the files lexer.h and lexer.c on the submission site for project 2. getToken() reads the next token from standard input and returns its type as a token_type enum. If the token is of type ID , NUM , IF , WHILE , DO , THEN , or PRINT , then the actual token value is stored in the global variable current_token as a null-terminated character array and the length of the string is stored in the global variable token_length . There are two special token_type values: END_OF_FILE , which is returned when the lexer encounters the end of standard input and ERROR , which is returned when the lexer encounters an unrecognized character in the input. ungetToken() causes the next call to getToken() to return the last token read by the previous call to getToken() . Note that this means the next call to getToken() will not read from standard input. It’s a logical error to call ungetToken() before calling getToken() . This function is useful for writing recursive descent parsers that you will see later on in this course. There are four global variables declared in lexer.h that are set when getToken() is called: t_type : the token type is stored here. Note that this will be the same value that was returned by getToken() . current_token : the token value is stored in the array current_token . If the token is of type ID , NUM , IF , WHILE , DO , THEN , or PRINT , then current_token contains the token string. For all other token types, current_token contains the empty string. token_length : the length of the string stored in current_token . line : the current line number of the input when the token was read.
3. Requirements Your program should use the provided lexer and read all tokens from the input by repeatedly calling the getToken() function. Certain token strings and additional data should be stored in a linked list. Specifically, if either of the following conditions are true: The token is of type NUM OR The token is of type ID AND the actual token is equal to one of the following values: “cse340” , “programming” , or “language” Then the token string and other information needs to be stored in a node of a linked list. The information that needs to be stored about each of these tokens in the linked list is the following: Token type (from t_type ) Token value (from current_token ) Line number of the input where token was read (from line ) After reading all tokens from the input and storing information about tokens that match the criteria, your program should go over the linked list and print the information in reverse order from when that token was encountered. Each of the tokens in the linked list must be printed to standard output on a separate line with the
You should write all your code in a separate C or C++ file and include lexer.h to be able to access the lexer functions. Here is how to do it in C:
And this is how to do it in C++:
To compile your code, you should use the GCC compiler from CentOS 6.7 that you have installed from last project. This is how to compile your code if you are writing it in C:
To compile your C++ program, use the following two commands instead:
Example Here is an example input with four lines:
Here is the expected output:
Notice that the tokens are listed from last to first (reverse order). 4. Testing This section is relevant to this project as well as all later projects in this course. 4.1. Input / Output Your program should read the input from standard input. That is normally the keyboard input and it can be accessed by using many standard C functions like getchar() , scanf() etc. In C++, you would use cin to read from standard input. In this project, you won’t read the input directly, the call to getToken() would read the input by using getchar() . Read the source code in lexer.c to see how this is done. Your program should write its output to standard output. That is normally done by using such functions as printf() or puts() in C or using cout in C++. 4.2. Testing Your Code Our grading system is automated hence another program (running on the submission site server) tests your code for correctness. We provide exact input/output format for every project in addition to multiple test cases . A test case is composed of two parts: A specific input in a file with .txt extension The expected output in a file with .txt.expected extension Your program passes a test case if given the input in the .txt file, it produces exactly the same output as the contents of the respective .txt.expected file. Otherwise your program fails that test case. 4.2.1. Testing with a single test case To feed the input file to your program without typing its content on the keyboard, we use input redirection and you should too! Here is how you would redirect the standard input of a program to a file: Let’s assume that we have a compiled program named a.out (an executable file). Normally, you would run this program like this (in a terminal):
Which would wait for you to provide the input by typing it on the keyboard (that is if the program expects any input). To redirect the standard input to a file named test01.txt , you should run the program like this instead:
the program through its standard input. Similarly, we can redirect the standard output to a file. This way instead of printing the output of the program on the terminal, the output will be stored in a file. To redirect the standard output, we use the “greater than” character with a file name like this:
NOTE: if a file with the same name exists, it will be overwritten! Of course you can mix input and output redirection as well:
Our automated grading system compares the output generated by your program with the expected output by using the diff command. diff is a system utility that is used to compare the contents of two files. If the files are different, it produces a report highlighting the differences otherwise it outputs nothing. We use diff with -Bw option which causes it to ignore differences in whitespaces. Here is an example of how to compare the output generated by the program with the expected file:
4.2.2. Running multiple test cases You can also use the shell script that we have provided called test1.sh , which automates this process for multiple test cases. The test script assumes that your compiled program is called a.out and test cases are stored in a subdirectory named tests . You can run it like this: command to fix the problem:
the output with the expected file using diff and reports any differences for failed cases. At the end it will print the number of tests passed and removes any temporary files created. It is strongly recommended that you test your program before submission with the provided test cases the way I described here. 5. Evaluation Your submission will be graded on the number of test cases passing when you submit your code. If your program does not compile on the server, you will not receive any credit, so if you a see a compiler error message on the submission site, fix the problem and submit again. 6. Submission Submit your code on the course submission site. You should only upload your source code
