nicksettler / ifj_proj_2022 Goto Github PK
View Code? Open in Web Editor NEWMinimal type-safe PHP compiler
Minimal type-safe PHP compiler
Lexical analyzer parses the following expression to the following table. Actually, such code must lead to lexical error. So it is needed to add more tests for different operator combinations with some failing tests. Example combinations: */
, +*
, -*-
, *+
and so on.
$a = 2 */ 3;
type | value |
---|---|
IDENTIFIER | $a |
ASSIGN | = |
INTEGER | 2 |
MULTIPLY | * |
INTEGER | 3 |
Binary tree needs to be tested. The following tests are needed to create:
Lexical analyzer implementation currently parses source string
5 - 3.4asd4;
as the following tokens
value | type |
---|---|
5 | INTEGER |
- | MINUS |
3.4 | FLOAT |
asd4 | IDENTIFIER |
; | SEMICOLON |
The same behaviour is present while working with integers, for example for the following code 5 - 3asd4;
Such behaviour is wrong. Trying to parse these lines of code should throw a lexical error, saying, that number can contain only digits.
Project contains LL grammar. It is needed to create a LL table based on grammar and ad it to documentation
To print more useful error messages, there is a need to add information about each token where it starts and ends. This information can be stored in each token of lexical analyzer and be passed to syntax analyzer. Syntax analyzer nodes can also contain this information in node attributes to print its error during analysis.
Source code must be filtered before lexical analzying:
// ...
must be removed/*
and ending with */
must be removedSuch filtering may be implemented using regular expressions
The following piece of code can be correctly parsed using compiler. This happens because one of the tokens it gets from lexical analyzer is ?>write
with type IDENTIFIER
. Anyway the source code is parsed correctly, because PHP standards allow programmers to skip closing php bracket (?>
). So this statement is parsed like a function call with no closing PHP bracket after it. EOF
after the last ;
token just finishes syntax analysis.
<?php
$a = 1;
write($a);
?>write(1);
This bug is related to wrong lexical analyzer behaviour. Lexical analyzer must return these tokens separately from the source code:
?>
(CLOSE_PHP_BRACKET
)write
(IDENTIFIER
)(
(LEFT_PARENTHESIS
)1
(INTEGER
))
(RIGHT_PARENTHESIS
);
(SEMICOLON
)The project will contain code generators functions. These functions will write commands to target program source code. The list of all the commands is listed in the task.pdf in the chapter 10.4. It is needed to create file with all code generator functions. Each function with instruction printing should append it to the string_t
data type from #1 PR.
Current implementation of semantic analysis does not support checking return types in function declaration. Returned value type from function must match return type from function declaration. This logic should be added
Lexical analyzer does not have tests for negative expressions. Add tests for the following expressions:
$a = -4 + $b
$a = -sum(1, $c) + $b
$a = -(4 + $b) + (-(-func1()+(-2 * sum($c, 2))))
Current implementation of syntax analyzer cannot parse null in expressions - such case will lead to syntax error. This bug should be fixed
declare is one of PHP control structures. It should be recognized in the following way as other keywords like if
, while
and so on, and it should not be looked for in the symbol table.
According to the section 12.4 of the task.pdf each source code file must be started with a comment which includes:
Úvod všech zdrojových textů musí obsahovat zakomentovaný název projektu, přihlašovací jména a jména studentů, kteří se na daném souboru skutečně autorsky podíleli.
For future files it might be useful to create a File Template in CLion. Settings → Editor → File and Code Templates → Includes tab. Set the content of C File Header the following. Change #set
directivies with your VUT login and your full name
#set( $Login = "xmoise01" )
#set( $Fullname = "Nikita Moiseev" )
/**
* Implementace překladače imperativního jazyka IFJ22.
* @authors
* ${Login}, ${Fullname}
*
* @file ${FILE_NAME}
* @brief
* @date ${DATE}
*/
PHP has a case-insensitive contant null. It must be recognized bu lexical analyzer
Code generator contains wrong predefined functions, that should be changed according to the task
Current implementation can parse the following code into SYN_NODE_IF
. Its right branch will not contain SYN_NODE_SEQUENCE
, but SYN_NODE_ASSIGN
, which prevents semantic analysis from checking if variables in assignment expression are defined. This behaviour should be changed, to make if statement contain SYN_NODE_SEQUENCE
in the right branch even without curly brackets
if ($a == 1) $b = 0;
Semantic analysis does not support calling function recursively. For example the following code will throw a SEMANTIC UNDEF VAR ERROR
saying that factorial function is used before declaration
function factorial(int $n) : int {
if ($n < 2) {
$result = 1;
} else {
$decremented_n = $n - 1;
$temp_result = factorial($decremented_n);
$result = $n * $temp_result;
}
return $result;
}
The same error is called if two function are used recursively like in the following code
function abc(int $a) {
return def($a - 1);
}
function def(int $a) {
if ($a != 0) abc($a);
}
Current compiler implementation does not support any code optimisations. It is needed to add mathematical expressions optimisations where it is possible. Optimiser must be able to simplify math expressions containing only constant values like in the example below. Float type can be removed in places where it is not needed - decimal part of a number is 0.
$a = 1 + 2;
# Simplify to $a = 3;
$b = 3.0 * 2;
# Simplify to $b = 6;
$c = 2.5 * 4;
# Simplify to $c = 10;
$d = 6.0 / 3.0;
# Simplify to $d = 2;
$e = 1.0 * 2 + 4.5 * 4 - (2 - 2.0)
# Simplify to $c = 20;
For creating syntax analyzer is needed to add grammar rules in some text file
Union two separate files of lexical analyzer into one: lexical_fsm
and lexical_token
Syntax analyzer must be capable to parse function declarations
Function declaration without arguments
function f() {
# statements
}
Function declaration with non-typed arguments and no return type
function sum($a, $b) {
return $a + $b;
}
Function declaration with non-typed arguments and return type
function sum($a, $b): int {
return $a + $b;
}
Function declaration with typed arguments and no return type
function sum(int $a, int $b) {
return $a + $b;
}
Function declaration with typed arguments and return type
function sum(int $a, int $b): int {
return $a + $b;
}
It is needed to add deletion of unused variables to code optimiser. Variable can be deleted in the following cases:
// First case example
$a = 1; # this line can be deleted
write("Hello world");
// Second case example
$i = 0;
$b = 0; # this line can be deleted
while ($i < 10) {
$b = $b + 1; # this line can be deleted
$i = $i + 1;
}
write($i);
Lexical analyzer should be tested better for handling error code. The following errors should be tested:
strict_types
error. Must be thrown when declare contains something which is not strict types or its value is not 0 or 1[a-zA-Z]
) or an underscore (_
)\d
). Must be implemented in #21Code optimiser must be able to remove unreachable code. Code is unreachable in the following cases:
function sum($a, $b) {
return $a + $b;
write($a, $b); # this code is unreachable and can be removed
}
$s = 1;
# The condition below is unreachable - the following 3 lines of code can be removed.
if ($s == 2) {
write("Hello");
}
$s = 2;
# Else body in the following if..else construction in unreachable and can be removed
if ($s == 2) {
write("Hello");
} else {
write("Bye");
}
$s = 10;
# The following while loop body is unreachable and can be removed
while ($s < 10)
write($s);
Code optimiser must be able to remove unused variables declaration. Variable declaration can be useless, when it is storing just constant values. Any usage of such variable can be replaced with its value like in the example below
$a = 1;
$a = $a + 2; # Can be changed to $a = 1 + 2; First line can be deleted
write($a); # Can be changed to write(3); Second line can be deleted
Source code contains a lot of redundant files and code, which must not be included in final archive with completed task. All things, that are needed to be done, before creating completed task archive are stated in repository wiki in the following page. Bash script should be used to simplify execution of these tasks.
Moreover it might be reasonable to add execution of this bash script to CI pipeline. This pipeline should be triggered when milestone is closed, or when tag is created (for creating unplanned versions). The pipeline must create a release including an archive with completed task as a release attachment.
Current syntax analyzer implementation does not support parsing return
command in function or in any other block of code. This feature should be added.
Current syntax analyzer implementation will process the following program
$a = 1;
$b = 2;
as the following tree
graph TD
R(SYN_NODE_SEQUENCE) --L--> RL(SYN_NODE_SEQUENCE)
R --R--> RR(SYN_NODE_ASSIGN)
RL --L--> RLL(NULL)
RL --R--> RLR(SYN_NODE_ASSIGN)
RLR --L--> RLRL(SYN_NODE_INDENTIFIER)
RLR --R--> RLRR(SYN_NODE_INTEGER)
RR --L--> RRL(SYN_NODE_INDENTIFIER)
RR --R--> RRR(SYN_NODE_INTEGER)
Current implementation parses program in a kind of binary tree.
This should be changed to make syntax tree able to store multiple nodes in a particular level. So the mentioned program must be parsed into the following tree to reduce nesting of the whole tree. This implementation is more suitable unlike the second one
graph TD
R(PROGRAM) --1--> R1(SYN_NODE_ASSIGN)
R --2--> R2(SYN_NODE_ASSIGN)
R --"..."--> RN(...)
R1 --1--> R1L(SYN_NODE_INDENTIFIER)
R1 --2--> R1R(SYN_NODE_INTEGER)
R2 --1--> R2L(SYN_NODE_INDENTIFIER)
R2 --2--> R2R(SYN_NODE_INTEGER)
Also this can be parsed into the following tree. But such implementation will be hard to debug
graph TD
R(PROGRAM) --N--> R1(SYN_NODE_ASSIGN)
R1 --L--> R1L(SYN_NODE_INDENTIFIER)
R1 --R--> R1R(SYN_NODE_INTEGER)
R1 --N--> R2(SYN_NODE_ASSIGN)
R2 --L--> R2L(SYN_NODE_INDENTIFIER)
R2 --R--> R2R(SYN_NODE_INTEGER)
R2 --N--> R3(...)
Code generator should have tests. These tests can be written in bash due to complexity of testing its through GoogleTest - target code, output and input may differ in tests. This should be better tested using existing language interpreter and prepared source codes, inputs and output of the code via bash. Usage of bash script can be also useful for tracking interpreter return codes
Syntax tree may contain expressions in the different parts of code. Semantic analysis should be abe to define type of its expression (INT
, FLOAT
, STRING
).
$a = 1 + 2.5; // typeof $a = "float"
Code optimiser must be able to remove unused functions declaration. Function is unused when it is not used anywhere in the code except its own scope. For example, the fib
function can be removed from the example below. It is used in its own block of code, but it is not used anywhere else in the code, so it is unused.
function fib(int $x): int {
if (x == 1 || x == 0) {
return(x);
} else {
return fib(x - 1) + fib(x - 2);
}
}
$a = 2;
write($a);
According to the task, chapter 12.3, project documentation must contain FSM diagram of lexical analyzer. This diagram can be created using any diagram creation tool. Diagram should be in .png format. Also it may be good to save diagram in a format of editor it has been made in. These files should be stored in docs folder of the code repository.
Expressions, variables and function calls always have some type/return type. Some kind of leafs if AST might need type casting for processing invalid types passed.
function test(string $a) {
// ...
}
$a = 1; // typeof $a = "int"
test($a); // typeof $a = "int" => int can be type casted to string => $a = "1"
$a = "Hello"; // typeof $a = "string"
if ($a) // typeof $a = "string" => string can be type casted to int (bool): 1 if $a is not NULL and not empty, 0 otherwise => if-condition: $a != NULL || $a != ""
// ...
$a = ""
while ($a) // typeof $a = "string" => string can be type casted to int (bool) => while-condition: $a != NULL || $a != ""
// ...
Current implementation of defined/undefined variables using symbol table is implemented in syntax tree creation. Tokens into symtable are inserted in l;exical analysis. This behaviour should not be in the mentioned methods. So it is needed to refactor this logic and move it to separate file with all semantic analysis functions.
Syntax analyzer must be capable to parse while loops
Simple while loop
while ($a != 0)
$a = $a - 1;
# OR
while ($a != 0) {
$a = $a - 1;
}
While loop
while ($a != 0) {
$a = $a - 1;
$b = $b + 1;
}
Lexical analyser cannot parse <?php
and ?>
from input string. These are the open and closing brackets of PHP code, which must be parsed by lexical analyser for their processing by next analysers.
Syntax analyzer must be capable to parse multiple if..else conditions.
Simple if conditions
if ($a == 1) $b = 2;
# OR
if ($a == 1) {
$b = 2;
}
If..else conditions
if ($a == 1) $b = 2; else $b = 3;
# OR
if ($a == 1) {
$b = 2;
} else {
$b = 3;
}
Multiple if..else conditions
if ($a == 1) $b = 2; else if ($a == 2) $b = 3; else $b = 4;
# OR
if ($a = 1) {
$b = 2;
} else if ($a == 2) {
$b = 3;
} else {
$b = 4;
}
Syntax analyzer must be capable to parse function calls with any parameters
Simple function call
test();
Function call with simple parameters
test(1);
#OR
test(1, 2);
#OR
test(1, 2, 3, ...); // function with any number of parameters
Function call with parameters
test(1 + 3, $a, f());
Current syntax analyzer implementation supports parsing only non-typed equal. It does not support typed equal parsing and throws and error in this case. This bug should be fixes
Current implementation allows to parse any code without php brackets. This logic must be changed according to grammar rules. Source code must start with open php bracket (<?php
/<?
). Then source code must be parsed as usual. The end of the program can contain close php bracket (?>
), but according to php standards this bracket is optional. Anyway, if there is a close php bracket in the end of source code, there must not be any other tokens except END_OF_FILE
after it
A declarative, efficient, and flexible JavaScript library for building user interfaces.
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google ❤️ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.