Problem Statement | |||||||||||||
You have been charged with writing the 'type checking' module for a new language called TC--. When coding in TC--, the coder is allowed to omit the types of local variables and parameters, and the return types of functions, only when the compiler is able to deduce those types from their usage. Each valid program has one and only one possible "type set". Sometimes a variable is used before its type is "known" when reading the program from top to bottom, but that should not deter the type checking module you're writing. Once the type of a variable is known, it is retroactively effective to the start of the function, and proactively effective to the end of the function. This applies to local variables, formal parameters, and function return types. Informally the grammar can be defined as:
Function calls, assignments and expressions are all instances of "program statements" and can occur in any order within the function. A return statement will always be the last statement in a function. Note that there are only two data types in TC--: int and string. You cannot mix ints and strings in an assignment or an expression. Only the + and - operators are valid on strings, whereas all four operators are valid on ints. Both arguments to a binary operator must be variables or parameters of the same type (no constants in expressions). For example (line numbers and whitespace added for clarity): 1 function f(a,b,c) 2 e:int 3 g=h(a) 4 e=b+c 5 return c 6 7 function h(p:string):string 8 return p The TC-- compiler will deduce the following types:
Write a method, deduceTypes, which is given a valid TC-- program which follows the grammar defined above, and determines each function's complete signature and the types of all local variables in each function. The program provided will be syntactically valid, and will be guaranteed to have only one unique type assignment. Your method should return a String[] which contains two types of entries:
Therefore, for the above example, your output should be: function f(a:string,b:int,c:int):int e:int g:string function h(p:string):string | |||||||||||||
Definition | |||||||||||||
| |||||||||||||
Notes | |||||||||||||
- | Function names may be reused as parameter or variable names. | ||||||||||||
- | Variables can be used before they are assigned a value. | ||||||||||||
- | A formal grammar for the input can be found at the end of the problem. | ||||||||||||
Constraints | |||||||||||||
- | There will be at least one function defined in program | ||||||||||||
- | There will be at most one definition for each function (no overloading). | ||||||||||||
- | program will contain between 2 and 50 elements, inclusive. | ||||||||||||
- | Each element in program contain between 3 and 50 characters, inclusive. | ||||||||||||
- | All variable, parameter and function names will be single letters in lower case. | ||||||||||||
- | Integer constants range from zero (inclusive) to positive infinity, subject to line length constraints | ||||||||||||
- | String constants will always start and end with double quotes | ||||||||||||
- | String constants may contain any upper or lower case letter, digit, space, or any of the following characters: !@#$%^*()_+`~-={}|;:,.? | ||||||||||||
- | Spaces (outside quotes) will only be present in two locations: 1. After the function keyword (exactly one single space will always be present) 2. After the return keyword (exactly one single space will always be present) | ||||||||||||
- | The program provided will be syntactically valid, and will be guaranteed to have only one unique type assignment. | ||||||||||||
- | The number of arguments in each function call will always match the number of formal parameters defined for that function. | ||||||||||||
- | Variable names will not 'shadow' parameter names, or vice versa. | ||||||||||||
Examples | |||||||||||||
0) | |||||||||||||
| |||||||||||||
1) | |||||||||||||
| |||||||||||||
2) | |||||||||||||
| |||||||||||||
3) | |||||||||||||
| |||||||||||||
4) | |||||||||||||
|