COM3360 Project ============================================================================ Name: Dino DiBiaso Account: dibiaso Project: Implement sem-check tool using propagation patterns. Includes all consistency checking of class dictionaries and generated files with the exception of LL-1 grammar checking. Directory: /proj/asl/lieber/f95/com3360/dibiaso/README-project Credits: Used class dictionary from: /course/com3360/doc/cds/cd-class-dictionary ============================================================================ to run program: alias sem-check-pp /proj/asl/lieber/f95/com3360/dibiaso/sem-check-pp sem-check-pp -i cd.cd ============================================================================ Class Dictionary: // // The class dictionaries which define the inputs to our tools are // available with the following copyright notice: // Copyright (C) 1985-1993 Northeastern University. // Permission is granted to any individual or institution to use, copy, modify, // and distribute this class dictionary, provided that this complete copyright // and permission notice is maintained, intact, in all copies and supporting // documentation. Cd_graph = < adjacencies > Nlist(Adjacency) ["*terminal_sets*" Comma_list(Vertex) "." *l]. Adjacency = < source > Vertex ["(" < parameters> Comma_list(Vertex) ")"] < ns > Neighbors "." *l. Neighbors : Neighbors_wc | Repetit_n *common*. Neighbors_wc : Construct_ns | Alternat_ns *common* + < construct_ns > List(Any_vertex) - . Construct_ns = "=". Alternat_ns = ":" + < alternat_ns > Bar_list(Term) - [ Common]. Common = "*common*". Repetit_n = "~" Sandwich(Kernel). Kernel = [ Term ] "{" Sandwich(Term) "}". Any_vertex : Opt_labeled_term | Optional_term | Syntax_vertex | Inherit_term. Vertex = < vertex_name > DemIdent . Syntax_vertex : Regular_syntax | Print_command *common*. Regular_syntax = < string > DemString . Print_command : Print_indent | Print_unindent | Print_skip | Print_space. Print_indent = "+" . Print_unindent = "-" . Print_skip = "*l" . Print_space = "*s" . Opt_labeled_term : Labeled | Regular *common* [StaticSpec] [AccessorSpec] Term. StaticSpec = "*static*" . AccessorSpec : ReadOnlyAcc | PrivateAcc *common* . ReadOnlyAcc = "*read-only*" . PrivateAcc = "*private*" . Regular = . Labeled = "<" < label_name > DemIdent ">" . Inherit_term = "*inherit*" Comma_list(Term). Term : Normal | CppTerm *common* Vertex TermRef ["(" Comma_list(Term) ")" ]. CppTerm = "$" . Normal = . TermRef : LocalRef | ModuleRef. ModuleRef : CompRef | LibRef *common* DemIdent. LocalRef = . CompRef = "@". LibRef = "@@". Optional_term = "[" Sandwich(Opt_labeled_term) "]". // Parameterized classes List(S) ~ {*l S}. Nlist(S) ~ S {S}. Bar_list(S) ~*l S {"|" *l S}. Comma_list(S) ~ S {"," S}. Sandwich(S) = List(Syntax_vertex) S List(Syntax_vertex) . // Added by D. DiBiaso to help checking inductiveness Ind_list ~ { Vertex }. ============================================================================ Bugs and parts of project that would have been developed further: I had trouble getting some of the "C" standard libraries to be linked in to the main program, and subsequently could not use the "mkdir" system call to create the directory "./notmod/cds" if it does not already exist. Therefore, the three expanded class dictionaries that are generated are stored in the current directory where the source class dictionary exists. The cosmetic format of the generated expanded class dictionaries (ie. the spacing, indentation, skipped lines, etc.) could be improved to look nicer like the format generated by the real sem-check. This would have to be done by adding more strategically placed print commands to the class dictionary or writing a propagation pattern to pretty print the CD instead of using g_print(). Checking inherit cycles may be only taking into acount alternation edges and not *inherit* edges. CppTerms ($) are reported as undefined. A few false alarms (warnings) are generated by the checking of the inductiveness axiom. I ran out of time to complete handling all of the idiosynchracies involved in recursively checking for cycles of Terms. Complete sem-check functionality by adding LL-1 grammar checking using propagation patterns. ============================================================================ Test inputs: In directory /proj/asl/lieber/f95/com3360/dibiaso, a number of test input class dictionaries can be found named di.* that fail each of the rules for consistency checking or contain several examples for testing the the expanded class dictionaries that are generated. This set of CDs tests whether each phase of sem-check succesfully detects the inconsistencies that it was designed to detect. Several class dictionaries were used to test whether the expected outputs were generated for "correct" class dictionaries. The CDs in directory /course/com3360/doc/cds were used for thorough testing. ============================================================================ Test input/output case: INPUT: Example = Op. Op : A | B | C. A : C | D. B ~ { Example}. C = Example. D = . OUTPUT: Checking that if a class is used without a label, then the name of this class must contain at least one capital letter ... Checking that the first production is an unparameterized construction production ... Checking that every class is defined exactly once ... Checking that two class names on the right hand side of every repetition production are identical ... Checking that every parameterized class is consistently defined and used ... Checking that formal parameter classes are not used as parameterized classes on the right hand side ... Checking that every alternative of a parameterized alternation class has to use all its formal parameters in the same order ... Checking inheritance cycles ... Expanding parameterization ... Checking that all alternatives are defined as either construction classes or alternation classes that will eventually be defined by construction classes ... sem-check: error: on line 2 C is duplicated as an alternative of Op . sem-check: error: on line 2 B , a repetition class, cannot be an alternative of Op . Checking whether the class names and label names are the keywords of C++ Demeter ... Expanding common parts ... Expanding inherit classes ... Checking that the part names of every vertex are unique ... Checking the Inductiveness Axiom ... Semantic check failed. ============================================================================ Input/output case where behavior could be improved (Inductiveness Axiom checking): Input: Conglomerate = Name Company. Name = DemIdent. Company = Name List(Employee) List(Company). Employee : Manager | Staff *common* Name Name Salary. Salary = DemNumber. Manager = . Staff = . List(S) ~ { S }. Output: Checking that if a class is used without a label, then the name of this class must contain at least one capital letter ... Checking that the first production is an unparameterized construction production ... Checking that every class is defined exactly once ... Checking that two class names on the right hand side of every repetition production are identical ... Checking that every parameterized class is consistently defined and used ... Checking that formal parameter classes are not used as parameterized classes on the right hand side ... Checking that every alternative of a parameterized alternation class has to use all its formal parameters in the same order ... Checking inheritance cycles ... Expanding parameterization ... Checking that all alternatives are defined as either construction classes or alternation classes that will eventually be defined by construction classes ... Checking whether the class names and label names are the keywords of C++ Demeter ... Expanding common parts ... Expanding inherit classes ... Checking that the part names of every vertex are unique ... sem-check: error: near line 4 find nonunique parts: of Manager = < name > Name < name > Name < salary > Salary . < name > Name from Manager < name > Name from Manager sem-check: error: near line 6 find nonunique parts: of Staff = < name > Name < name > Name < salary > Salary . < name > Name from Staff < name > Name from Staff Checking the Inductiveness Axiom ... There are no non-cyclic objects for the following classes: Conglomerate Name Company Warning: There are 1 violations of the Inductiveness Axiom Semantic check failed. ============================================================================ Other Info: None of the generated C++ code that were generated from the cd.cd and *.pp files were changed. The generated Makefile that gen-make produced was not changed. ============================================================================ Approach: The approach I used in developing my project was to break the program into the 15 different phases that the sem-check program goes through (12 class dictionary checking rules and 3 class dictionary generations). Each of these phases was implemented in a propagation pattern ".pp" file. Also, an additional propagation pattern file, utilities.pp was created that contained helper propagation patterns that were called in several places. The main function, main.C, calls each of the 15 high level propagation patterns in sequential order. Each high level propagation pattern returns an integer value of 1 if the rule or class dictionary generation succeeded and a 0 if it failed. The resulting message generated by sem-check as to whether the whole sem-check operation failed or not is determined by "anding" the results of the calls to the high level pps together. The pps that generate class dictionaries by expanding parameterized classes and common parts of inheritance classes also modify the structure of the class dictionary object so that the future propagation patterns that are executed on the cd can be take advantage of the simplified, expanded structure. I realize that a project of this scope could never be accomplished in the time it took me to do it without using the adaptive software techniques. The large number of traversals required to perform all of the class dictionary semantic checking functions would have been overwhelming in itself to write in straight C++. There were a couple of nice short cuts that really saved a lot of time like using g_print to output the expanded class dictionaries. Also, 3/4 of the way through my implementation I realized that I was not using the latest CD for Demeter C++ class dictionaries and had to change my CD! The changes minimally affected some of the propagation patterns, but did not change too much considering how much code was already developed. I found that it took several iterations to come up with propagation patterns that worked the way I had in mind when I wrote them. I took me a while to really understand how alternation classes are implemented. For my decent sized project, towards the end, the turnaround time became almost unbareable due to the large amount of code that needed to be generated and compiled from the propagation patterns. Also, it seemed that every propagation pattern had to be recompiled if the structure of any propagation pattern changed. I also went down the wrong path a couple of times and ended up rewriting entire sets of propagation patterns to perform functions the most efficient way.