just the quesion 3 please
Consider the grammar in Figure 1 where the terminal int denotes an integer and the terminal id S + Atoms Atoms Atoms + Atom Atoms Atom + Atom Atom id Atom int Atom + Atoms ) Figure 1: A simplified grammar for Scheme. denotes an identifier. The only other terminals in this grammar are the quote ', the left parenthesis (, and the right parenthesis ). Scheme, a derivative of Lisp, is a list based language where all programs are represented by lists. For example, a simple Scheme program (+12) adds two numbers together and prints out the result. A scheme interpreter, /local/bin/scheme, is available on timberlea.cs.dal.ca. Feel free to give it a try. A program, which is zero or more atoms is executed by evaluating each of the atoms. An atom is either an integer, an identifier, or a list. The evaluation of an integer is the integer, and the evaluation of an identifier, for now, is simply the identifier. The evaluation of a quoted atom is simply the atom itself. E.g., the evaluation of' ( 123 ) is ( 1 2 3). A list is evaluated by evaluating the first atom of the list and treating the result as a function. Then each of the remaining atoms of the list is evaluated, and passed as parameters to the function. For example, the evaluation of ( + 1 2 ), treats + as a function, and passes 1 and 2 to the function. Applying + to 1 and 2 yields the result 3. Whereas, the evaluation of ( + 1 ( * 23 ) ), evaluates + and 1 as before, but then evaluates ( * 2 3 ), yielding 6, which is then passed to the + function, which yields the result of 7. 1. (8 marks] Consider the following L-attributed grammar, based on the grammar specified in Figure 1. Describe and justify what it is computing. Be sure to explain the purpose of the attributes, and what each of the semantic rules is doing. Your description must include a succinct summary of the purpose of this attribute grammar. I.e., Be sure to state what it is supposed to do, not just how it is doing it. Symbol Attribute Type Atoms calls: int synthesized callable: bool synthesized symbol_table: Symbol Table inherited Atom calls: int synthesized callable: bool synthesized symbol_table: Symbol Table inherited In the attribute grammar below, the symbol indicates a semantic rule that operates on inherited attributes, and the symbol indicates a semantic rule that operates on synthesized attributes. S + Atomsi > Atomsi.symbol_table = getSymbol Table() print(Atoms.calls) Atoms Atoms.calls = 0 Atom .symbol_table = Atoms.symbol_table > Atoms1.symbol_table = Atoms.symbol_table Atoms.calls = Atomi.calls + Atoms.calls Atoms.callable = Atomi.callable Atom + Atomi > Atomi.symbol_table = Atom.symbol_table Atom.calls = 0 Atom.callable = false Atomid Atom.calls = 0 Atom.callable = Atom.symbol_table.is Function(id) Atom int Atom.calls = 0 Atom.callable = false Atom + ( Atoms) > Atoms1.symbol_table = Atom.symbol_table if Atoms.callable then Atom.calls = Atoms.calls + 1 Atom.callable = Atoms.callable 2. (8 marks] Suppose you wanted to construct an abstract syntax tree from parse tree derived by using the grammar specified in Figure 1. Give an S-attributed grammar that creates an abstract syntax tree composed of the following kinds of tree nodes as illustrated in the UML diagram below. ASTNode LiteralASTNode + LiteralASTNode (Number) ListAstNode + ListAstNode (ASTNode) + prependNode(ASTNode) : void + appendNode(ASTNode) : void IdentifierastNode IdentifierASTNode(String) QuotedASTNode + QuotedASTNode (ASTNode) All that is required is to create an abstract syntax tree. Observe that all you will need for most types of nodes is just the constructor (as shown) but for ListASTNode two methods are provided to prepend and append nodes to a list. You will need one of these methods, depending on how you structure your attribute grammar. Please provide both the semantic rules and the attributes using notation similar to that in question 1. Provide a brief explanation of how the grammar works. 3. [9 marks] Suppose that the base ASTNode class had a setNesting(int n) method that sets the nesting level of the node in the abstract syntax tree. The nesting level is simply the number of parentheses surrounding the symbol contained in the node. E.g., for ((a) b (c (de) the outer list is at nesting 0; the atoms (a), b, and (c (d e)) are at nesting 1; atoms a, c, and (de) are at nesting 2; and atoms d and e are at nesting 3. Extend the S-attributed grammar from Question 2 into an L-attributed grammar that also sets the nesting level of each node in the abstract syntax tree as it is created. Provide a brief explanation of how the grammar works. Consider the grammar in Figure 1 where the terminal int denotes an integer and the terminal id S + Atoms Atoms Atoms + Atom Atoms Atom + Atom Atom id Atom int Atom + Atoms ) Figure 1: A simplified grammar for Scheme. denotes an identifier. The only other terminals in this grammar are the quote ', the left parenthesis (, and the right parenthesis ). Scheme, a derivative of Lisp, is a list based language where all programs are represented by lists. For example, a simple Scheme program (+12) adds two numbers together and prints out the result. A scheme interpreter, /local/bin/scheme, is available on timberlea.cs.dal.ca. Feel free to give it a try. A program, which is zero or more atoms is executed by evaluating each of the atoms. An atom is either an integer, an identifier, or a list. The evaluation of an integer is the integer, and the evaluation of an identifier, for now, is simply the identifier. The evaluation of a quoted atom is simply the atom itself. E.g., the evaluation of' ( 123 ) is ( 1 2 3). A list is evaluated by evaluating the first atom of the list and treating the result as a function. Then each of the remaining atoms of the list is evaluated, and passed as parameters to the function. For example, the evaluation of ( + 1 2 ), treats + as a function, and passes 1 and 2 to the function. Applying + to 1 and 2 yields the result 3. Whereas, the evaluation of ( + 1 ( * 23 ) ), evaluates + and 1 as before, but then evaluates ( * 2 3 ), yielding 6, which is then passed to the + function, which yields the result of 7. 1. (8 marks] Consider the following L-attributed grammar, based on the grammar specified in Figure 1. Describe and justify what it is computing. Be sure to explain the purpose of the attributes, and what each of the semantic rules is doing. Your description must include a succinct summary of the purpose of this attribute grammar. I.e., Be sure to state what it is supposed to do, not just how it is doing it. Symbol Attribute Type Atoms calls: int synthesized callable: bool synthesized symbol_table: Symbol Table inherited Atom calls: int synthesized callable: bool synthesized symbol_table: Symbol Table inherited In the attribute grammar below, the symbol indicates a semantic rule that operates on inherited attributes, and the symbol indicates a semantic rule that operates on synthesized attributes. S + Atomsi > Atomsi.symbol_table = getSymbol Table() print(Atoms.calls) Atoms Atoms.calls = 0 Atom .symbol_table = Atoms.symbol_table > Atoms1.symbol_table = Atoms.symbol_table Atoms.calls = Atomi.calls + Atoms.calls Atoms.callable = Atomi.callable Atom + Atomi > Atomi.symbol_table = Atom.symbol_table Atom.calls = 0 Atom.callable = false Atomid Atom.calls = 0 Atom.callable = Atom.symbol_table.is Function(id) Atom int Atom.calls = 0 Atom.callable = false Atom + ( Atoms) > Atoms1.symbol_table = Atom.symbol_table if Atoms.callable then Atom.calls = Atoms.calls + 1 Atom.callable = Atoms.callable 2. (8 marks] Suppose you wanted to construct an abstract syntax tree from parse tree derived by using the grammar specified in Figure 1. Give an S-attributed grammar that creates an abstract syntax tree composed of the following kinds of tree nodes as illustrated in the UML diagram below. ASTNode LiteralASTNode + LiteralASTNode (Number) ListAstNode + ListAstNode (ASTNode) + prependNode(ASTNode) : void + appendNode(ASTNode) : void IdentifierastNode IdentifierASTNode(String) QuotedASTNode + QuotedASTNode (ASTNode) All that is required is to create an abstract syntax tree. Observe that all you will need for most types of nodes is just the constructor (as shown) but for ListASTNode two methods are provided to prepend and append nodes to a list. You will need one of these methods, depending on how you structure your attribute grammar. Please provide both the semantic rules and the attributes using notation similar to that in question 1. Provide a brief explanation of how the grammar works. 3. [9 marks] Suppose that the base ASTNode class had a setNesting(int n) method that sets the nesting level of the node in the abstract syntax tree. The nesting level is simply the number of parentheses surrounding the symbol contained in the node. E.g., for ((a) b (c (de) the outer list is at nesting 0; the atoms (a), b, and (c (d e)) are at nesting 1; atoms a, c, and (de) are at nesting 2; and atoms d and e are at nesting 3. Extend the S-attributed grammar from Question 2 into an L-attributed grammar that also sets the nesting level of each node in the abstract syntax tree as it is created. Provide a brief explanation of how the grammar works
