これがベトナム大学院の実態だ!

Trường Đại Học Bách Khoa Thành Phố Hồ Chí Minhの大学院修士課程に社会人入学

Nguyên lý ngôn ngữ lập trình / Assignment 3

悪名高いとか物議を醸すとか不名誉な枕詞のつく同科目において、悪夢のAssignment 3が勃発した。
さすがに以前の約束通り、Assignment 2ができていなくても取り組めるようにはなっていた。

Assignment 3
version 1.1
After completing this assignment, you will be able to
• explain the principles how a compiler can check some semantic constraints such as
type compatibility, scope constraints,... and
• write a medium ( 300-500LOC) Scala program to implement that.
1 Specification
In this assignment, you are required to write a static checker for a program written in MC.
To complete this assignment, you need to:
• Read carefully the specification of MC language
• Download and unzip file assignment3.zip
• If you completed Assignment 2, you can skip this step. Otherwise (if you did not
complete Assignment 2), don’t worry, just follow these steps:
– download initial.zip, and unzip it, and change the folder initial into assign-
ment3; change current directory into assignment3
– remove folder src/main/mc/codegen, src/main/mc/checker and files AstUtils.scala,
TestChecker.scala, CheckerSuite.scala, TestCodeGen.scala and CodeGenSuite.scala
in folder src/test/scala/
– modify src/main/mc/Main.scala by commenting out 2 lines "import jasmin.Main"
and "import mc.codegen._"
– download upload.zip from Assignment 2, unzip it, and copy files into the corre-
sponding folders as described in Assignment 2.
• Make folder src/main/mc/checker and copy StaticCheck.scala and StaticError.scala
(from assignment3.zip) into this folder
• Copy TestChecker.scala and CheckerSuite.scala (from assignment3.zip) into src/test/scala
• Modify StaticCheck.scala to implement the static checker. Please fill in your id in
the headers of this file.
2
2 Static Checker
A static checker plays an important role in modern compilers. It checks in the compiling
time if a program conforms to the semantic constraints according to the language specifica-
tion. In this assignment, you are required to implement a static checker for MC language.
The input of the checker is in the AST of a MC program, i.e. the output of the assignment
2. The output of the checker is nothing if the checked input is correct, otherwise, an error
message is released and the static checker will stop immediately
For each semantics error, students should throw corresponding exception given in Stat-
icError.scala to make sure that it will be printed out the same as expected. Every test-case
has at most one kind of error. The semantics constraints required to check in this assign-
ment are as follows.
2.1 Redeclared Variable/Function/Parameter:
An identifier must be declared before used. However, the declaration must be unique in
its scope. Otherwise, the error messages “Redeclared : ”+ is released,
where is the kind of the identifier in the second declaration. The scope of an
identifier (variable, function, parameter) is informally described as in Section 10 of MC
specification.
2.2 Undeclared Identifier/Function:
The error message “Undeclared Identifier: ”+ is released when there is an iden-
tifier is used but its declaration cannot be found. The identifier can be a variable or
parameter. “Undeclared Function: ”+ is released in similar situation for
a function invocation.
2.3 Type Mismatch In Statement:
A statement must conform the corresponding type rules for statements, otherwise the error
message “Type Mismatch In Statement: ”+ is released.
The type rules for statements are as follows:

  • The type of a conditional expression in an if statement must be boolean.
  • The type of expression 1 and expression 3 in a for statement must be integer while

the type of expression 2 is boolean.

  • The type of condition expression in do while statement must be boolean.
  • For a return statement, if the return type of the enclosed function is void, the

expression in the return statement must be empty. Otherwise, the type of the return
3
expression must be equal to or be coerced to the return type of the function. An
exception is an array pointer or array can be returned to an array pointer, i.e., the
type of return expression can be in array pointer or array type while the return type
of the enclosed function is in array pointer type with the same element type.
2.4 Type Mismatch In Expression:
An expression must conform the type rules for expressions, otherwise the error message
“Type Mismatch In Expression: ”+ is released.
The type rules for expression are as follows:

  • For an array subcripting E1[E2], E1 must be in array type or array pointer type and

E2 must be integer.

  • For a binary and unary expression, the type rules are described in the MC specifica-

tion.

  • For an assignment expression, the left-hand side can be in any type except void, array

pointer type and array type. The right- hand side (RHS) is either in the same type
as that of the LHS or in the type that can coerce to the LHS type. In MC, just the
integer can coerce to the float.

  • For a function call (), the number of the actual parameters

must be the same as that of the formal parameters of the corresponding function.
The rule for an assignment is applied to parameter passing where a formal parameter
is considered as the LHS and the corresponding actual parameter is the RHS. An
exception is an array pointer or array can be passed to an array pointer, i.e., the
actual parameter can be in array pointer or array type while the corresponding formal
parameter is in array pointer type with the same element type.
The three following errors are required just for the students in gifted class (KSTN):
2.5 Function not return:
A function that does not return void must return something in every its execution paths.
If there exists one path where there is nothing returned, the error message "Function Not
Return: " will be released.
2.6 Break/Continue not in loop:
A break/continue statement must be inside directly or indirectly a loop otherwise the error
message "Break/Continue Not In Loop" will be released.
4
2.7 Unreachable statement:
An unreachable statement is a statement in a function which the control flow cannot reach.
For example, the statement after a return statement is an unreachable statement. The value
of an expression is ignored when determining an unreachable statement. For instance, the
stmt in if (false) stmt is reachable as the value of the condition expression is ignored.
The error message "Unreachable statement: "+ will be released when the
is an unreachable statement.
2.8 No Entry Point:
There must be a function void main () somewhere in a MC program. Otherwise, the error
message "No entry point" is released.
2.9 Unreachable function:
A function, except main function, must be invoked by another function, otherwise, the
error message "Unreachable function: " is released.
3 Submissions
This assignment requires you submit 2 files: StaticCheck.scala containing class Static-
Checker with the entry method check, and CheckerSuite.scala containing 100 testcases.
The deadline is announced in course website and in www.cse.hcmut.edu.vn/onlinejudge.
If the deadlines in these places are different, the deadline in www.cse.hcmut.edu.vn/onlinejudege
is applied.
4 Plagiarism
• You must complete the assignment by yourself and do not let your work seen by
someone else.
If you violate any requirement, you will be punished by the university rule for plagiarism.