CS 431, Assignment 3, Book Questions on Chapter 2
Plus One Other Question
Questions that you need to answer are listed below, and some solutions or partial solutions are also given. The solutions are not prented as the only possible answers, and what is given may not be complete. It may only be a starting point for thinking about a complete, correct answer. Your goal in working the problems should be to come up with a solution, and if in doubt about your answer, compare with what’s given here. In theory, even if your answer is not exactly the same, you should e the n or understand the direction of the suggestions. If your answer is at odds with what I have suggested you might want to check with me. It is possible that I am off ba. It is also possible that you need some things clarified.
Book problems: 2.1, a-c; 2.2, a-e; 2.3; 2.4, a-e, and 2.8. Suggested answers to the questions are given after the following question.
Last problem: There is an additional problem that is not from the book. It is stated here. Implement Java code that will correctly translate infix expressions with + and – (no parenthes and no other operators) to postfix expressions. A problem solution is given in the book in C code, so your task is ma
inly one of adaptation. A starting point for this problem is posted on the Web page. You may u the file InfixToPostfixCut.java as given and simply add the needed methods. You can also do the problem from scratch if you want to. I think it would be preferable if you left your implementation recursive rather than changing it to a loop, but that is your choice. Hand in a printout of the methods you added along with your answers to the problems listed above.
Starting points for thinking about solutions:
2.1. Consider the following context-free grammar
S → S S + (1)
S → S S * (2)
S → a (3)
a) Show how the string aa+a* can be generated by this grammar.
Production (3) allows you to generate a string S0 which consists of a.
Using S0 as a starting point, production (1) allows you to generate a string S1 which consists of aa+.
大雾天气 英文Production (3) again allows you to generate a string S2 which consists of a.
Then production (2) allows you to generate a string S3 = S1S2* = aa+a*.
b) Construct a par tree for this string.
c) What language is generated by this grammar? Justify your answer.
Assuming a is an identifier for a numeric value, for example, then the grammar generates a language consisting of all possible arithmetic combinations of a using only the operations + and * and postfix notation. (No particular justification is given. Check to e if you agree.)
2.2. What language is generated by the following grammars? In each ca justify your answer. (No justifications are given.)
a) S → 0 S 1 | 0 1
All strings divided evenly between 0’s and 1’s, with the quence of 0’s coming first and the quence of 1’s coming cond.
b) S → + S S | - S S | a
This is the prefix analog to question 2.1.
c) S →S ( S ) S | ε
This will generate arbitrary quences of adjacent and nested, matched pairs of parenthes.
d) S → a S b S | b S a S | ε
All possible strings containing equal numbers of a’s and b’s, with the a’s and b’s arranged in no particular order.
e) S → a | S + S | S S | S * | ( S )
I don’t e a pattern to this that I can verbally describe.
2.3. Which of the grammars in Exerci 2.2 are ambiguous?
To show ambiguity it is sufficient to find any single string that can be pard in more than one way using the grammar. No such strings spring immediately to mind for the grammars of a through d. (That does not mean that there aren’t any.) However, e is clearly ambiguous. Let the string S + S * be given. Here are two possible parsings:java技能培训
2.4. Construct unambiguous context-free grammars for each of the following languages. In each ca show that your grammar is correct. (Correctness is not shown.)
a) Arithmetic expressions in postfix notation.
list → list list +
list → list list –
list → digit
vmas
list → 0 | 1 | 2 | … | 9
b) Left-associative lists of identifiers parated by commas.
list → list, id
list → id
c) Right-associative lists of identifiers parated by commas.
list → id, list
list → id
d) Arithmetic expressions of integers and identifiers with the four binary operators +, -, *, /.
Add the following rule to the grammar given at the end of ction 2.2:什么是动名词
波兰语你好
factor → identifier
green spote) Add unary plus and minus to the arithmetic operators of (d).
Add the following rules to the grammar:
factor → +factor
factor → -factor
水盂
2.8 Construct a syntax-directed translation scheme that translates arithmetic expressions from postfix notation to infix notation. Give annotated par trees for the inputs 95-2* and 952*-.
Here is a simple grammar that can rve as a starting point for the solution of the problem:
string → digit string operator
| string digit operator
| digit
雅思学习技巧
digit →0 | 1 | 2 | … | 9
operator → * | / | + | -
Here is an annotated par tree of the first expression:
The first production applied in forming this tree was: string → string digit operator. Notice that it would have been just as possible to apply the production: string → digit string operator. If that had been done you would have then had to par the string “5-2”. This result would not par and it would be necessary to backtrack and choo to apply the other production. At the next level down it doesn’t matter which production is chon.
In this example there is no choice about which production to apply first. At the cond level there is
a choice but it doesn’t make a difference. The lack of choice at the first level illustrates clearly how you could tell whether or not the production you have chon is the correct one, assuming you could look that far ahead: If the string that you have pard on the right hand side does not end in an operator, then the production choice is not correct. It is also possible to e that if you could specify the order in which productions are tried, you could avoid backtracking. If you always tried to par using this production first: string → string digit operator and tried the other one if that one failed to apply, you would avoid backtracking. But again, such an approach is not allowed. The question of backtracking is discusd on pages 45 and 46 of the book. The upshot of the matter is that this grammar isn’t suitable for predictive parsing.
There is another matter that will require a change in the grammar so that a syntax-directed translation scheme can be devid. At the top of page 39 in the book the term “simple” is defined as it applies to a syntax-directed definition. The requirement is that the order of non-terminals on the right hand side of a production agree with the order of the corresponding symbols generated as the desired output. Other symbols or terminals may come before, between, or after the output for the non-terminals. Under this condition the output can be generated from a depth first traversal of the annotated tree. The problem with the grammar given above is that all of the operators are symbolize
阿糖胞苷英文d using the non-terminal “operator”. However, in the translation from postfix to infix, it is the position of the operator that changes. That means that even though tedious, for practical reasons the productions have to be rewritten with the operator symbols in-line as terminals:
string → digit string *
| digit string /
>pgm
