C++ Library And Build The Parser

At Programming Homework Tutors, we believe in providing our students with practical, real-world examples of how to apply the concepts they learn in class. That’s why we’ve developed a variety of sample projects to help you see how our courses can be used to create impactful solutions in your field of study.

Description

For this assignment, you will be given a program, convert it to an intermediate representation that can be easily run by other code.

Basics

You will be given several files.  It is recommended that you add these files to your solution for assignment 2 as a starting point.  You are allowed to use, modify, or ignore any of the files from your solution for assignment 2, and you may create any other files that are required to implement the program.

Grammar Description

The grammar (given in extended Backus-Naur form) for the grammar description is as follows:

program → variables body

variables → idList SEMICOLON

idList → ID { COMMA ID }

body → LeftBRACE statementList RightBRACE

statementList → statement { statement }

statement → assignStatement | ifStatement | printStatement | switchStatement | whileStatement

assignStatement → ID EQUAL primary SEMICOLON | ID EQUAL expression SEMICOLON

ifStatement → IF conditional body

printStatement → PRINT ID SEMICOLON

switchStatement → SWITCH ID LeftBRACE caseList [ defaultCase ] RightBRACE

whileStatement → WHILE conditional body

expression → primary op primary

conditional → primary relationalOperator primary

primary → ID | NUM

op → PLUS | MINUS | MULT | DIV

relationalOperator → GREATER | LESS | NotEQUAL

caseList  → case { case }

case  → CASE NUM COLON body

defaultCase → DEFAULT COLON body

The tokens in the above grammar are defined as follows:

COLON = :

SEMICOLON = ;

COMMA = ,

LeftBRACE = {

RightBRACE = }

WHILE = WHILE

EQUAL = =

PLUS = +

MINUS = –

MULT = *

DIV = /

GREATER = >

LESS = <

NotEQUAL = <>

ID = letter(letter | digit)*

NUM = 0 | (digit digit*)

IF = IF

PRINT = print

SWITCH = SWITCH

CASE = CASE

DEFAULT = DEFAULT

Things to note about this grammar:

1. Expressions are greatly simplified and are not recursive.
2. There is no explicit typing of variables.  All variables are INT by default.
3. All variables are declared at the beginning of the program.
4. All arithmetic is integer arithmetic.
5. The if statement has no else.
6. The print statement has been added and the print keyword is in lower case.
7. Any terminals are written in capital letters and are defined the same as the previous projects (except for the print keyword).

Tokenizer

Because the list of keywords in this language is different, you will need to modify the tokenizer that was provided in assignment 2 (or you created for assignment 2) to handle those changes.  You may assume that the rules on generating tokens remains the same.

Running the Program

The additional code that was provided will take the list of statements and run them.  You may assume that this works.  If necessary, I will provide updates through the additional code.  This additional code can be used in your unit testing.  These files are identical to the files that are used in Gradescope.

Execution Semantics

All statements are to be executed in the order that they appear in the program except for if, switch, and while statements.  Note that if, switch, and while statements may be nested.

If Statement

An if statement has the following semantics:

1. The conditional is evaluated.
2. If the conditional evaluates to true, the body of the if statement is executed.
3. Execution then proceeds with the statement after the if statement.

Print Statement

A print statement “print a;” prints the value of the variable a at the time of execution.

Switch Statement

A switch statement has the following semantics:

1. The value of the switch statement is checked against each case number in order of appearance.
2. The body of the first case number that matches the value is executed.
3. If none of the cases match, then the body of the default case is executed if it exists.
4. Execution then proceeds with the statement after the switch statement.

A switch statement in the code:

SWITCH expression {

    CASE value1 : { statementList1 }

…

    CASE valuen : { statementListn }

    DEFAULT : { defaultStatementList }

}

nextSectionOfCode

is equivalent to:

IF expression == value1 {

    statementList1

    GOTO label

}

…

IF expression == valuen {

    statementListn

    GOTO label

}

defaultStatementList

label:

nextSectionOfCode

While Statement

A while statement has the following semantics:

1. The conditional is evaluated.
2. If the conditional evaluates to true, the body of the while statement is executed.  Control passes back to step 1.
3. If the conditional evaluates to false, execution then proceeds with the statement after the while statement.

A while loop in the code:

WHILE condition {

    statementList

}

is equivalent to:

label:

IF condition {

    statementList

    GOTO label

}

Generating Code

Your code will need to take the input file and generate a linked list that contains all of the instructions and is easy to execute.  This section describes the types of statements and the information needed for the list you generate to run.

The various types with “Type” in the name in the subsections below are all enumerations that can be found in the file types.h.

Handling Constants and Variables

Constants and variables are handled through the ValueNode class.  The class has one member variable:

            int value;         // Value of the constant or variable

When converting the code, take all constants and store it in value, then pass the pointer to whatever statement needs it.  When converting a variable, the value will also be stored in a ValueNode object.

Handling Simple Assignments

Simple assignments are stored in an AssignmentStatement class.  The class has five member variables:

            ValueNode *leftHandSide;

            ValueNode *operand1;

            ValueNode *operand2;           // Ignored if operator is NO_OPERATOR

            OperatorType operator;          // Set to NO_OPERATOR if there is no operator

            StatementNode *nextStatement;        // Handles the next statement

The variables operator and operand2 are optional.  If they are provided, the value calculated by the expression operand1 operator operand2 will be assigned to leftHandSide.  If they are not provided, the value operand1 will be assigned to leftHandSide instead.

Note that variables are initialized to zero when declared.

Handling Goto Statements

While there is no goto statement in this programming language, goto statements are required by the switch and while statements for the intermediate representation for the code to work.

Goto statements are stored in a GotoStatement class.  The class has one member variable:

            StatementNode *nextStatement;        // Next statement to be run

Handling If and While Statements

If statements are stored in an IfStatement class.  The class has five member variables:

            ConditionType conditionOperation;

            ValueNode *operand1;

            ValueNode *operand2;

            StatementNode *trueBranch;             // Next statement if condition is true

            StatementNode *falseBranch;            // Next statement if condition is false

The two operands are compared using the condition operation.  If the comparison is true, control transfers to the statement indicated by trueBranch.  If the comparison is false, control transfers to the statement indicated by falseBranch.

While statements can be built using a combination of IfStatements and GotoStatements.

Handling No Operation Statements

While there is no noop statement in this programming language, noop statements are useful in situations where there just needs to be a statement to pass control to.

Noop statements are stored in a NoOpStatement class.  The class has one member variable:

            StatementNode *nextStatement;        // Next statement to be run

Handling Print Statements

Print statements are stored in a PrintStatement class.  The class has one member variable:

            ValueNode *ID;          // ID to be printed out

This statement will print out the value of ID->GetValue().

Handling Switch Statements

Switch statements can be built using a combination of IfStatements and GotoStatements in a similar way as while.

Executing the Intermediate Representation

After the list of statements has been built, it needs to be executed.  Execution begins with the first statement in the list.  The pseudocode for execution is as follows:

currentStatement = first statement of program

while (currentStatement != NULL)

            If currentStatement is an assignment, make the assignment, then go to the next statement.

            If currentStatement is a goto, go to the next statement indicated by the goto.

If currentStatement is an if, determine if the condition is true or not.  Go to the next statement based on the result.

If currentStatement is a no operation (do nothing), then go to the next statement.

If currentStatement is a print, print the value, then go to the next statement.

The code that actually runs the program is the function ExecuteProgram in compiler.cpp.

Implementation

You will need to implement the function parseGenerateIntermediateRepresentation and return a linked list containing the statements that need to be run.

Input/Output

The input is provided by a file, and your program will need to return a pointer to the StatementNode that corresponds to the first line of the program.  You do not need to provide anything else, as your program will be tested by running the program and comparing your output with the expected output.

Disclaimer

The sample projects provided on our website are intended to be used as a guide and reference for educational purposes only. While we have made every effort to ensure that the projects are accurate and up-to-date, we do not guarantee their accuracy or completeness. The projects should be used at your own discretion, and we are not responsible for any loss or damage that may result from their use.
At Programming Homework Tutors, we are dedicated to helping students and educators achieve their goals by providing them with the resources they need to succeed. Our website offers a variety of tools and resources that can help you with the project mentioned above.
Whether you need help with research, project management, or technical support, our team of experts is here to assist you every step of the way. We offer online courses, tutorials, and community forums where you can connect with other learners and get the support you need to succeed.
If you’re looking to take your skills to the next level and make an impact in your field, we invite you to explore our website and see how we can help you achieve your goals.