2021/5/31 Project 1 https://canvas.vt.edu/courses/131840/assignments/1195002 1/6 Unlimited Attempts 2021/5/242021/6/3 Details CS 3304 Project #1 At some point in your schooling, you may have encountered the concept of diagramming sentences. A diagram of a sentence is a tree-like drawing representing the grammatical structure of the sentence, including parts such as the subject, verb, and object. Here is an extended BNF grammar for some simple English sentences that we will use for the purposes of diagramming.
--> --> --> | --> --> lifted | saw | found --> quickly | carefully | brilliantly --> [] [] --> cow | alice | book --> | --> green | lean | mean --> --> of | at | with This grammar can generate an infinite number of sentences. One sample is: mean cow saw carefully green alice with book (For simplicity, we ignore articles, punctuation, and capitalization, including Alice’s name or the first word of the sentence.) Implementation Language For this assignment, your program must be written in Pascal (https://canvas.vt.edu/courses/131840/pages/pascal) . Your solution may only use standard Pascal code, not extensions or special library routines provided with your compiler. If your Pascal compiler includes object-oriented features, you may not use them for this assignment. Your program must Project 1 2021/6/2 100 Possible Points IN PROGRESS Next Up: Submit AssignmentAttempt 1 View Feedback 2021/5/31 Project 1 https://canvas.vt.edu/courses/131840/assignments/1195002 2/6 adhere to proper use of the Pascal language as well as good programming style, including embedded routines, scoping, parameter passing, identifier naming, and routine length. This assignment will also give you more experience using BNF. Decide what the basic operations are that you need to implement, how those will be written as functions or procedures, and then how they can be used to build higher level functions/procedures. An easy way to organize your solution is to construct one (parameterless) procedure for each non- terminal in the grammar. See Chapter 4 in Sebesta (in 11th ed., Section 4.4, pp. 175-183 of Chapter 4) for details on recursive descent parsing. For example, the following procedure parses the non- terminal : procedure adj; { The global variable "next_token" holds the next token in the input stream. See Sebesta for details } begin write ('('); { more on this below } if ((next_token = 'green') or (next_token = 'lean' ) or (next_token = 'mean' )) then begin lexical; { A function you write to advance to the next token } write (')') end else error ('Input is not a sentence'); { A function you write to handle errors } end; Here's an alternative version for the parse adjective procedure parse_adjective; { The global variable "next_token" holds the next token from the input stream. See Sebesta for details } begin if ( (next_token = 'lean') or (next_token = 'green') or (next_token = 'mean') ) then begin good_output := good_output + '"' + token + '"'; {good_output is a global variable I use for the output of the parenthesized sentence} lexical; end else if ( next_token_type = none ) then {next_token_type is a function I wrote that returns the type of word that the next token is} {none is what is returned if the next_token isn't one of the known words} begin error_flag := true; error_message := 'Input has invalid tokens.'; {error_flag is a global I use to indicate if an error has occurred} {error_message is the error message that is output if there is an error} end else begin error_flag := true; error_message := 'Input is not a sentence.'; end end; Input Format 2021/5/31 Project 1 https://canvas.vt.edu/courses/131840/assignments/1195002 3/6 Your program should read “candidate sentences”, one per line, from its standard input. For each line of input, your program should attempt to interpret the line’s contents (a whitespace-separated list of words) as a sentence. You will need to read each entire line in as a string. This string will have to be split into tokens by a lexical analyzer, which will then feed them to your parsing routine. Each input line is guaranteed to fit into a String variable in FreePascal, and each input line is guaranteed to end in a newline. If you are developing your solution under Unix, be sure that your code works correctly whether the standard input stream uses Unix (a line feed) or Windows (a carriage return/line feed pair) line ending conventions. The best way to address this problem is simply to use the readln() operation to read input a line at a time. Alternatively, if you choose to read input one character at a time, you can use the eol function to detect line endings and then use readln() to advance over the line terminator, all in an OS-independent manner. Output Format The output of your program should be produced on standard output (in the Pascal sense of the term). Your program should produce a “diagrammed” version of the input string, which means a sentence in properly parenthesized form. “Properly parenthesized” means that each non-terminal appearing in the input string now has parentheses around it (omitting all redundant parentheses). For instance, the input string: "alice found mean green book" would be parenthesized as ((("alice")) ("found") ((("mean"("green"))"book"))) A more complicated example is "mean cow saw carefully green alice with book" which returns (((("mean")"cow")) ("saw""carefully") ((("green")"alice"("with"("book"))))) In addition, there are two distinct error conditions that your program must recognize. First, if a given string does not consist of valid tokens, then respond with this message: "Input has invalid tokens." Second, if the parameter is a string consisting of valid tokens but it is not a legitimate sentence according to the grammar, then respond with the message: "Input is not a sentence." Note that the “invalid tokens” message takes priority over the second message; the “not a sentence” message can only be issued if the input string consists entirely of valid tokens. 2021/5/31 Project 1 https://canvas.vt.edu/courses/131840/assignments/1195002 4/6 Here's a sample output. You can see the input sentence and then the corresponding output. To be clear, you do not include the input sentence nor the word "Sentence:" in the output. The only thing you put in the output is the parenthesized sentence or the error message. I've included many with errors for your testing: output_windows.txt (https://canvas.vt.edu/courses/131840/files/18867219?wrap=1) (https://canvas.vt.edu/courses/131840/files/18867219/download?download_frd=1) output.txt (https://canvas.vt.edu/courses/131840/files/18867220?wrap=1) (https://canvas.vt.edu/courses/131840/files/18867220/download?download_frd=1) Pascal Implementation Hints There's a Pascal Language Page (https://canvas.vt.edu/courses/131840/pages/pascal) I've made and there's a video you can watch with samples as well. Here are some random bits of Pascal information that you may find useful as you implement this assignment: Free Pascal supports a string type called String . By default, this type supports strings up to 255 characters in length. Strings are stored as character arrays, with a “hidden” byte at the beginning to record the current length of the string. Unlike C, C++, or Java, in Pascal, the first character in a string is at index position 1. See Section 2.13.2.4 of the FreePascal Reference Guide (http://www.freepascal.org/docs-html/ref/refsu64.html#x147-15300013.2) for details on the basic functions supported for strings. String comparisons are performed using “=”: s : String; ... if s = "while" then ... You can use readln(s); to read all characters on the current input line into a string variable s , and then advance over the newline to the start of the next line. Each OSIL input line will be no longer than 255 characters. You can use writeln(x); to print out any value of any scalar type. You can use ord(c) to convert any character c into its corresponding ASCII code as an integer. You can use chr(x) to convert an integer value x into a character with the corresponding ASCII code. You can use val(s, x, err) to parse a string s into its corresponding integer value, which will be placed in x . The integer err will be set to the result code of the operation (0 for success, or the position where parsing failed if there was an error). You can use copy(s, start, len) to extract a substring from a string, or use delete(s, start, len) to remove characters from a string. 2021/5/31 Project 1 https://canvas.vt.edu/courses/131840/assignments/1195002 5/6 You can use a forward declaration (https://www.freepascal.org/docs- html/ref/refse97.html#x189-21300014.6) to introduce a subroutine’s name and parameter profile (so it can be called by others) before you give its implementation. This is necessary for mutually recursive or mutually dependent operations. Submitting Your Program Your Pascal implementation is to be organized in a single file. All documentation and identifying information should be placed in comments within the single source file. The comments at the beginning of the file should identify the assignment and give your full name. Every Pascal procedure/function should be preceded by comments explaining its purpose, the meaning of each parameter, and the general strategy of its implementation if applicable. You'll submit here on Canvas. I will grade your submission on rlogin. I'll give your program 1 sentence at a time and compare it's output to the reference solution output. If I can manage it, I'll do this before the due date, give feedback and allow you to submit it again. If not, then I'll do this after the due date, give feedback and a small window of time to submit any fixes. 80% of the score comes from correct implementation and execution; 20% of the score comes from programming style, sound design, and good coding principles (comments, readability). The system will begin accepting submissions as soon as I can. You will have an unlimited number of submissions. We will grade the final submission only. Please stay abreast of the deadlines and plan you schedule accordingly. Upload File File permitted: PAS Drag and drop, or click to browse your computer More Options 2021/5/31 Project 1 https://canvas.vt.edu/courses/131840/assignments/1195002 6/6 学霸联盟 
