BEST代写-线上留学生作业代写 & 论文代写专家


C/C++代写|COMS W4115: Programming Assignment 2.2 (Syntax Analysis)

C/C++代写|COMS W4115: Programming Assignment 2.2 (Syntax Analysis)


Assignment Objectives

From this assignment:

1. You will learn about the AST structure of the code.
2. You will get familiar with different AST APIs provided by LLVM/Clang.
3. You will get familiar with Clang’s ASTVisitor.
4. You will learn how to traverse an AST.
5. You will learn how to write a simple code reformatter.


You have already implemented a (albeit very simple) lexical analyzer/tokenizer that converts character sequences from a code stream to token sequences. As you learned in lecture, this token sequence is processed by the parser, and an abstract syntax tree (AST) is generated. In this assignment, you will use the clang compiler to generate an AST. Further, you will investigate two different case studies to analyze an AST.

Generating the AST (10 Points)

In Programming Assignment 2.1, you saw how to build LLVM. The Clang compiler front-end leverages the LLVM back-end infrastructure. For any code written in C , C++ , or Objective-C , you can generate (and visualize) the AST using Clang.
First, let the shell/terminal know where you built LLVM. We recommend adding the following line to your $HOME/.bashrc file:

export LLVM_HOME=<base directory where you built your llvm>;

Next, try the following command:

$LLVM_HOME/build/bin/clang -cc1 -ast-dump examples/gcd.c -I /usr/include/ \
-I $LLVM_HOME/build/lib/clang/12.0.0/include/;

You should spend some time looking at the output. Please write a few sentences in the outputs/AST.txt file describing the following: * What information is being presented in the output * What you find interesting about the output

You can also generate a visual representation of the AST. Try running the following command:

export LLVM_HOME=<base directory where you built your llvm>;
$LLVM_HOME/build/bin/clang -cc1 -ast-view gcd.c -I /usr/include/ \
-I $LLVM_HOME/build/lib/clang/12.0.0/include/;

This will generate a dot file in your /tmp/ directory. Locate the created dot file and identify the filename. Run the following:

dot -Tpdf /tmp/<dot file filename> -o output/AstView.pdf

Take a look at the PDF file that is generated, and try to match that with the output generated in the previous step.

Analyzing the AST
The AST is not just for viewing purposes; there are many powerful things you can do with an AST. For example, you can warn developers when a variable name does not follow a convention (e.g., camel casing) by traversing an AST; if you find or “visit” a variable name, you can verify whether that name matches the intended convention. Otherwise, you can generate a warning.

In this particular assignment, you will investigate how to analyze an AST to extract important information for two different tasks.

Task 1: Recursive Functions (40 Points)

Recursive functions are often compact, easy to read, and easy to understand. However, they often incur huge overhead due to call stack maintenance, which is a major concern if you are developing for a resource-constrained system. Your task here is to determine whether a given function is direct recursive or not. We will describe the tools that you will use for this task in a later section.


1. int recursive_factorial(int n1){
2. if (n1 <= 1){
3. return 1;
4. }
5. return n1 * recursive_factorial (n1 – 1);
6. }

In the above C code snippet, the function recursive_factorial is a direct recursive function, since there is a call to itself inside the body (line 5). In contrast, the following function is not direct recursive; even though there is a function call at line 4, the callee is not the function itself:

1. int iterative_factorial(int n1){
2. int res = 1;
3. for(int i = 0; i <= n3; i++){
4. res = mult(res, i); // multiplication of res and i.
5. }
6. return res;
7. }