Using the grammar for real-number constants discussed in class, write a set of rewrite…
- User
Using the grammar for real-number constants discussed in class, write a set of rewrite rules for signed real-number constants that allow an optional sign at the front of the constants. Use signed-real-const as the new start symbol. You can reuse as much or as little of the real-number constant grammar rules as you deem appropriate. Examples of valid signed real-number constants are: -3.56, +17.E09, 4.95 Using the following rewrite rules for Boolean expressions, give a derivation for the Boolean expression (NOT((F AND T)) OR F). Also draw a derivation tree corresponding to the derivation. bool-exp → T | → F | → NOT ( bool-exp ) | → ( bool-exp AND bool-exp ) | → ( bool-exp OR bool-exp ) Using the following rewrite rules for Boolean expressions, find two different derivation trees for the Boolean expression NOT(T OR T AND F). bool-exp → T | → F | → NOT ( bool-exp ) | → bool-exp AND bool-exp | → bool-exp OR bool-exp Using the following rewrite rules for arithmetic expressions, draw a derivation tree for the expression 53+1+4. expr → expr add-op term | term term → term mult-op factor | factor factor → ( expr ) | digit-seq add-op → + | - mult-op → * | DIV | MOD digit-seq → digit digit-seq | digit digit → 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 Using the following rewrite rules for arithmetic expressions, draw a derivation tree for the expression 53+1+4. expr → term { add-op term } term → factor { mult-op factor } factor → ( expr ) | digit-seq add-op → + | - mult-op → * | DIV | MOD digit-seq → digit digit-seq | digit digit → 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 Note: A pair of new special symbols ('{' and '}') is used in the rewrite rules above. The meaning of {...} is that the string of nonterminal and terminal symbols appearing between { and } can be repeated 0 or more times. For instance, the first rewrite rule:
expr → term { add-op term } is equivalent to the following (infinite) set of rewrite rules:
expr → term | → term add-op term | → term add-op term add-op term | → term add-op term add-op term add-op term | → ...
- Assistant
- Rewrite rules for signed real-number constants:
signed-real-const → sign unsigned-real-const sign → + | → - unsigned-real-const → integer-part decimal-part opt-exponent | → integer-part opt-exponent | → decimal-part opt-exponent integer-part → non-zero-digit digit-seq | → digit decimal-part → . digit-seq opt-exponent → e sign digit-seq | → e digit-seq | → epsilon digit-seq → digit digit-seq | → digit digit → 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 non-zero-digit → 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9- Derivation for the Boolean expression
(NOT((F AND T)) OR F)and derivation tree:
bool-exp → ( bool-exp OR bool-exp ) → ( NOT ( bool-exp ) OR bool-exp ) → ( NOT ( ( bool-exp AND bool-exp ) ) OR bool-exp ) → ( NOT ( ( F AND bool-exp ) ) OR bool-exp ) → ( NOT ( ( F AND T ) ) OR bool-exp ) → ( NOT ( ( F AND T ) ) OR F )Derivation tree:
bool-exp | ----------------- | | NOT ( bool-exp ) OR F | ( bool-exp AND bool-exp ) | | F T- Two different derivation trees for the Boolean expression
NOT(T OR T AND F):
First derivation tree:
NOT ( bool-exp ) | bool-exp OR bool-exp / \ T bool-exp AND bool-exp / \ T FSecond derivation tree:
NOT ( bool-exp ) | bool-exp OR bool-exp / \ bool-exp AND bool-exp T / \ T F- & 5. Derivation tree for the expression
5*3+1+4:
Both exercises ask for the derivation tree for the same arithmetic expression. Below is the derivation tree for
5*3+1+4, which follows the second set of rules:expr | term { add-op term } | factor { mult-op factor } { add-op term } | | | digital-seq * factor + term + term | | | | 5 digital-seq factor factor | | | 3 digit digit | | 1 4Note: Since the question mentions the repeatable patterns with curly braces
{...}, it seems implicit that it asks for a derivation using the second set of rules but refers to5*3+1+4twice, in the fourth and fifth points. However, if a classic derivation tree is required for the "expr → expr add-op term | term" rule set, the correct tree would be different from the one depicted above.