https://doc.lagout.org/science/0_Computer%20Science/1_Principles%20of%20Programming%20Languages/Programming%20Languages%20-%20Principles%20and%20Paradigms.pdf

( book link if u need extra information) ( working on chapter 2 )

Please answer questions 1-10: ( everything you need is provided )

1. Consider the grammar G", obtained from that in Fig. 2.6 by substituting the productions for the non-terminal symbol T with the following: I A E*T. Show that G" is ambiguous. 2. Give the obvious ambiguous grammar for the conditional command if, then, else. 54 2 How to Describe a Programming Language 3. Using the grammar fragment in Fig. 2.7 as a reference point, construct a deriva- tion tree for the string if (expressionl) if (expression2) commandl else command2 Assume that the following derivations exist: Expression expressioni, Expression expression2, StatementWithout TrailingSubstatement =* command, StatementWithout Trailing Substatement command. 4. Define a grammar that will generate all the pairs of balanced curly brackets (braces). 5. Define a grammar that generates the language {a" bn, m > 1} using only pro- ductions of the form N Mor N 1, where N and M are any non-terminal symbol and is any terminal symbol. Try to give an intuitive explanation of why there exists no grammar with these characteristics which generates the language {a"b" |n> 11. 6. Modify the rule of Fig. 2.12 so as to describe a right-to-left evaluation of arith- metic expressions. 7. Calculate the computation of the command X:=1; while -(x == 3) do X := (x+1) starting with a chosen state. 8. In Example 2.5, the last transition has as its right member only a state and not a pair composed of a command and a state). Is this always the case in a finite computation? (Hint: consider the command X:=0; X :=(x - 1), starting with any state whatsoever which includes X.) 9. State what the computation corresponding to the following command is: X:=1; X:=(x - 1); X:=(x - 1); X:=5 10. Considering Exercises 8 and 9, state a criterion which allows the division of finite computations into those which are correct and those which terminate be- cause of an error. Fig. 2.5 Another derivation tree for the string a+b+a E 1 a 1 1 In the tree in Fig. 2.4, we can see that the subexpression a*b appears as a left child of a sum. This expresses the fact that the string a*b+a must be interpreted as first multiply a by b and add the result to a", given that in order to compute the sum, the operand present in the left subtree is needed. Ambiguity Let us consider the following derivation (again using the grammar of Example 2.2): E =3 E*E 1*E > a* E a* E+E a*l+E 8 a*b+E = a*b+1 a*b+a If we construct the corresponding derivation tree, we obtain the tree in Fig. 2.5. Comparing the trees in Figs. 2.4 and 2.5, it can be seen that we have two different trees producing the same string. Reading the leaves of the two trees from left to right, in both cases, we obtain the string a + b + a. Let us observe, however, that the two trees are radically different. The second assigns a structure to the same string that is quite different and therefore reveals a different precedence implicit in the arithmetic operators). If we want to use derivation trees to describe the logical 38 2 How to Describe a Programming Language G' = ({E,T, A, 1}, {a,b, +. *, -, (.)), R', E) Fig. 2.6 An unambiguous grammar for the language of expressions E T| TE|T - E T AA*T A1-A(E) I ab|la|7b We have a grammar which interprets the structure of an expression according to the usual concept of arithmetic operator precedence. Unary minus **-") has the highest precedence, followed by *, followed in their turn by + and binary - (which have the same precedence). The grammar interprets, then, a sequence of operators at the same level of precedence by association to the right. For example, the string a+b+a will be assigned the same structure as the string a +(b+a). The absence of ambiguity is paid for by increased complexity. There are more non-terminals and the intuitive interpretation of the grammar is therefore more difficult. The need to provide unambiguous grammars explains the contortions that appear in the definitions of some programming languages. For example, Fig. 2.7 shows an extract of the official grammar for Java's conditional command (its if) (the non- terminal symbols are printed in italic, while the terminal symbols in this extract are if, else and brackets). This grammar is interesting for two reasons. First, note that what are formally considered single symbols (terminal or non-terminal) in context-free grammars are here represented by words composed of a number of characters. For example, if represents a single terminal symbol and, analogously, IfThenElseStatement repre- sents a non-terminal symbol. This happens because, in the definition of a programming language, it is prefer- ential to use meaningful words (if, then, else) which can, up to certain limits, suggest an intuitive meaning, rather than symbols which would be harder to under- stand by the language user. In other words, as we will better see in the next chap- ters, that the use of (meaningful) symbolic names definitely makes programming easier. Analogously, for non-terminal symbols, they make the grammar easier to understand. It is definitely better to use names such as Statement rather than single symbols. The second interesting aspect of the grammar is its complex nature. This com- plexity is necessary to resolve the ambiguity of strings (programs) such as the one exemplified by the following skeleton program: if (expressionl) if (expression2) commandl; else command2; Java, like a great many other programming languages allows conditional com- mands both with an else branch and without it. When an if command without else is combined with an if with an else branch (as in the case of the program appearing above), it is necessary to determine which of the two ifs is the owr of the single else. The grammar in Fig. 2.7 is an unambiguous one which makes owner 2.3 Contextual Syntactic Constraints 39 Statement := ... IfThenStatement IfThenElse Statement Statement Without Trailing Substatement StatementWithout TrailingSubstatement := ... | Block | Empty Statement | ReturnStatement StatementNoShortlf ::= ... StatementWithout Trailing Substatement IfThenElseStatementNoShortIf IfThen Statement ::= if (Expression Statement IfThenElseStatement ::= if (Expression StatementNoShortlf else Statement ifThenElseStatementNoShortlf ::= if (Expression Statement No Shortlf else StatementNoShortIf Fig. 2.7 Grammar for Java conditional commands "an else clause belong to the innermost if to which it might possibly belong" (from the Java definition [3]). In simple words, the else is paired with the second if (the one which tests expression2). Intuitively, this happens because, once an if command with an else is introduced by use of the non-terminal symbol IfThenElseStatement, the command in the then branch will be unable to hold an if command without an else, as can be seen by inspection of the rules which define the non-terminal symbol StatementNoShortlf. 2.5 Semantics 49 (x,c) (X), o) ((n + m), o) (2.0) ((n - m), o) (po) where p=n+m where p=n-menm (aj,o) (d',o) (a2, o) (a", o) ((a1 + a2),0) + ((a'+a2), o) ((a+a2), o) (lai+a"), o) (aj, a) al.) (a2, c) (a", o) ((a1 - 42),0) + ((a' - a2), o) ((ai - a2), o) (lai - a"), o) Fig. 2.12 Semantics of arithmetic expressions g, and if the command c2, starting in 02, can perform a computational step and transform itself into the command ca in state o, then the command, c, starting in the state o can perform a computational step and transform itself into the command d' in state o'. It is clear that a specific rule will express a number of meaningful relationships between c, ci and c2 (and their respective states). In general, ci and c2 will be subcommands of c.10 Expression semantics Figure 2.12 shows the rules for the semantics of arithmetic expressions. The first three rules are terminal rules (that is, the computation to the right of the arrow is in a form to which no more transitions can be applied). In order of presentation, they define the semantics of a variable, of addition in the case in which both of the summands are constants, of subtraction in the case in which both its arguments are constants and its result is a natural number. Note that no semantics is given for expressions such as 5 7. The second group of four rules is formed of conditional rules. The first pair defines the semantics of sums and expresses the fact that to calculate the value of a sum, it is necessary first to evaluate its two arguments separately. Note how the semantics specifies no order of evaluation for the arguments of an addition. Subtraction is handled in a similar fashion. Figure 2.13 shows the semantics of logical expressions and adopts the same ideas as for arithmetic expressions. Note that in this figure, bv denotes a boolean value (tt or ff). Command semantics It can be seen how the state, o always remains unaltered during the evaluation of an expression and how it is only used to obtain the value of a variable. This changes for the semantics of commands as shown in Fig. 2.14. Note how the rules in the Figure are essentially of two types: those which, for every command, express the actual computational step for that command (this holds for rules (cl), (c2), (c4), (cb), (c7) and (29)), as well as those which serve just to make 10It will not have escaped the attentive reader that what we have called conditional rules are, in reality, inductive rules forming part of the definition of transition relations. 1. Consider the grammar G", obtained from that in Fig. 2.6 by substituting the productions for the non-terminal symbol T with the following: I A E*T. Show that G" is ambiguous. 2. Give the obvious ambiguous grammar for the conditional command if, then, else. 54 2 How to Describe a Programming Language 3. Using the grammar fragment in Fig. 2.7 as a reference point, construct a deriva- tion tree for the string if (expressionl) if (expression2) commandl else command2 Assume that the following derivations exist: Expression expressioni, Expression expression2, StatementWithout TrailingSubstatement =* command, StatementWithout Trailing Substatement command. 4. Define a grammar that will generate all the pairs of balanced curly brackets (braces). 5. Define a grammar that generates the language {a" bn, m > 1} using only pro- ductions of the form N Mor N 1, where N and M are any non-terminal symbol and is any terminal symbol. Try to give an intuitive explanation of why there exists no grammar with these characteristics which generates the language {a"b" |n> 11. 6. Modify the rule of Fig. 2.12 so as to describe a right-to-left evaluation of arith- metic expressions. 7. Calculate the computation of the command X:=1; while -(x == 3) do X := (x+1) starting with a chosen state. 8. In Example 2.5, the last transition has as its right member only a state and not a pair composed of a command and a state). Is this always the case in a finite computation? (Hint: consider the command X:=0; X :=(x - 1), starting with any state whatsoever which includes X.) 9. State what the computation corresponding to the following command is: X:=1; X:=(x - 1); X:=(x - 1); X:=5 10. Considering Exercises 8 and 9, state a criterion which allows the division of finite computations into those which are correct and those which terminate be- cause of an error. Fig. 2.5 Another derivation tree for the string a+b+a E 1 a 1 1 In the tree in Fig. 2.4, we can see that the subexpression a*b appears as a left child of a sum. This expresses the fact that the string a*b+a must be interpreted as first multiply a by b and add the result to a", given that in order to compute the sum, the operand present in the left subtree is needed. Ambiguity Let us consider the following derivation (again using the grammar of Example 2.2): E =3 E*E 1*E > a* E a* E+E a*l+E 8 a*b+E = a*b+1 a*b+a If we construct the corresponding derivation tree, we obtain the tree in Fig. 2.5. Comparing the trees in Figs. 2.4 and 2.5, it can be seen that we have two different trees producing the same string. Reading the leaves of the two trees from left to right, in both cases, we obtain the string a + b + a. Let us observe, however, that the two trees are radically different. The second assigns a structure to the same string that is quite different and therefore reveals a different precedence implicit in the arithmetic operators). If we want to use derivation trees to describe the logical 38 2 How to Describe a Programming Language G' = ({E,T, A, 1}, {a,b, +. *, -, (.)), R', E) Fig. 2.6 An unambiguous grammar for the language of expressions E T| TE|T - E T AA*T A1-A(E) I ab|la|7b We have a grammar which interprets the structure of an expression according to the usual concept of arithmetic operator precedence. Unary minus **-") has the highest precedence, followed by *, followed in their turn by + and binary - (which have the same precedence). The grammar interprets, then, a sequence of operators at the same level of precedence by association to the right. For example, the string a+b+a will be assigned the same structure as the string a +(b+a). The absence of ambiguity is paid for by increased complexity. There are more non-terminals and the intuitive interpretation of the grammar is therefore more difficult. The need to provide unambiguous grammars explains the contortions that appear in the definitions of some programming languages. For example, Fig. 2.7 shows an extract of the official grammar for Java's conditional command (its if) (the non- terminal symbols are printed in italic, while the terminal symbols in this extract are if, else and brackets). This grammar is interesting for two reasons. First, note that what are formally considered single symbols (terminal or non-terminal) in context-free grammars are here represented by words composed of a number of characters. For example, if represents a single terminal symbol and, analogously, IfThenElseStatement repre- sents a non-terminal symbol. This happens because, in the definition of a programming language, it is prefer- ential to use meaningful words (if, then, else) which can, up to certain limits, suggest an intuitive meaning, rather than symbols which would be harder to under- stand by the language user. In other words, as we will better see in the next chap- ters, that the use of (meaningful) symbolic names definitely makes programming easier. Analogously, for non-terminal symbols, they make the grammar easier to understand. It is definitely better to use names such as Statement rather than single symbols. The second interesting aspect of the grammar is its complex nature. This com- plexity is necessary to resolve the ambiguity of strings (programs) such as the one exemplified by the following skeleton program: if (expressionl) if (expression2) commandl; else command2; Java, like a great many other programming languages allows conditional com- mands both with an else branch and without it. When an if command without else is combined with an if with an else branch (as in the case of the program appearing above), it is necessary to determine which of the two ifs is the owr of the single else. The grammar in Fig. 2.7 is an unambiguous one which makes owner 2.3 Contextual Syntactic Constraints 39 Statement := ... IfThenStatement IfThenElse Statement Statement Without Trailing Substatement StatementWithout TrailingSubstatement := ... | Block | Empty Statement | ReturnStatement StatementNoShortlf ::= ... StatementWithout Trailing Substatement IfThenElseStatementNoShortIf IfThen Statement ::= if (Expression Statement IfThenElseStatement ::= if (Expression StatementNoShortlf else Statement ifThenElseStatementNoShortlf ::= if (Expression Statement No Shortlf else StatementNoShortIf Fig. 2.7 Grammar for Java conditional commands "an else clause belong to the innermost if to which it might possibly belong" (from the Java definition [3]). In simple words, the else is paired with the second if (the one which tests expression2). Intuitively, this happens because, once an if command with an else is introduced by use of the non-terminal symbol IfThenElseStatement, the command in the then branch will be unable to hold an if command without an else, as can be seen by inspection of the rules which define the non-terminal symbol StatementNoShortlf. 2.5 Semantics 49 (x,c) (X), o) ((n + m), o) (2.0) ((n - m), o) (po) where p=n+m where p=n-menm (aj,o) (d',o) (a2, o) (a", o) ((a1 + a2),0) + ((a'+a2), o) ((a+a2), o) (lai+a"), o) (aj, a) al.) (a2, c) (a", o) ((a1 - 42),0) + ((a' - a2), o) ((ai - a2), o) (lai - a"), o) Fig. 2.12 Semantics of arithmetic expressions g, and if the command c2, starting in 02, can perform a computational step and transform itself into the command ca in state o, then the command, c, starting in the state o can perform a computational step and transform itself into the command d' in state o'. It is clear that a specific rule will express a number of meaningful relationships between c, ci and c2 (and their respective states). In general, ci and c2 will be subcommands of c.10 Expression semantics Figure 2.12 shows the rules for the semantics of arithmetic expressions. The first three rules are terminal rules (that is, the computation to the right of the arrow is in a form to which no more transitions can be applied). In order of presentation, they define the semantics of a variable, of addition in the case in which both of the summands are constants, of subtraction in the case in which both its arguments are constants and its result is a natural number. Note that no semantics is given for expressions such as 5 7. The second group of four rules is formed of conditional rules. The first pair defines the semantics of sums and expresses the fact that to calculate the value of a sum, it is necessary first to evaluate its two arguments separately. Note how the semantics specifies no order of evaluation for the arguments of an addition. Subtraction is handled in a similar fashion. Figure 2.13 shows the semantics of logical expressions and adopts the same ideas as for arithmetic expressions. Note that in this figure, bv denotes a boolean value (tt or ff). Command semantics It can be seen how the state, o always remains unaltered during the evaluation of an expression and how it is only used to obtain the value of a variable. This changes for the semantics of commands as shown in Fig. 2.14. Note how the rules in the Figure are essentially of two types: those which, for every command, express the actual computational step for that command (this holds for rules (cl), (c2), (c4), (cb), (c7) and (29)), as well as those which serve just to make 10It will not have escaped the attentive reader that what we have called conditional rules are, in reality, inductive rules forming part of the definition of transition relations