date: 2024-12-21
title: Compiler-As-3
status: DONE
author:
  - AllenYGY
tags:
  - Assignment
  - Compiler
publish: True

Compiler-As-3

Question 1

Use the grammar rules and attribute definitions in Lecture 10 Page 19 to construct the parse tree and syntax tree for expression "" assuming the expression is tokenized as ""

Parse Tree:

Tree

Syntax Tree:

Question 2

Use the grammar rules and attribute definitions in “Grammar+Typing.docx” (the grammar is in Lec 12 on pg 20) to analyze the source code

bool flip(bool x) not x; flip (flase)

Parse Tree

Symbol Table

Name	Type
flip
~~x （Removed）~~

Question 3

The language in Lec 11 on Page 27 has two production rules:

So, it is possible to have valid variable declarations

int *[10]x; int[10]* y;

Please follow the corresponding type checking rules on the same page to give the type of and . You need to explain your answer.

The type of x is
The type of y is

Question 4

The language in Lec 11 on Page 27 is too weak. It cannot make assignment from a memory location to a pointer. Thus, we power-up the language by modifying the grammar rules. (New or modified rules are in red color.) Define the correct type checking rules for the new grammar rules. Type checking for old grammar rules remain unchanged.

no need to define type
no need to define type
no need to define type

Question 5

Let the following grammar rules be the syntax of integer arithmetic.

Remark:

Token "num" is an integer constant.
"+" and "×" are integer addition and multiplication respectively.
Multiplication has the higher precedence. Furthermore, both operators are (left and right) associative.

However, this language is not perfect. It may contain many redundant parentheses.

For example, ((2 × 3) + 4) can be entirely without the parentheses as 2 × 3 + 4.
(You can try to parse them.) Thus, please design semantics for the grammar rules to remove redundant parentheses. (25 pt)

Hint:

The semantics should have at least two attributes.
One attribute is "expression", which holds the expression for each substructure.
After computing the semantics, E.expression has the final outcome — the
arithmetic expression without useless parentheses.
The value of attribute "expression" is treated as a string. And the operator ""
can be used (in semantic rules) to concatenate two strings.

Define the semantics for the grammar rules.

expression: Stores the simplified expression without redundant parentheses.
priority: Stores the priority of the operator in the expression.

denotes the concatenation of two strings.

Define a function for checking whether parentheses are needed for a given expression.

function checkParen(childExpr, childPriority, parentPriority):
    if childPriority < parentPriority then
        return "(" + childExpr + ")"
    else
        return childExpr