Skip to content
TheChatArchiveThe Chat Archive
gpt-4-1106-preview· openaiHugging Face Suzhen/CodeChat

Using the grammar for real-number constants discussed in class, write a set of rewrite…

  1. 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 | → ...

  2. Assistant
    1. 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
    
    1. 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
    
    1. 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       F
    

    Second derivation tree:

    NOT ( bool-exp )
         |
       bool-exp OR bool-exp
        /                \
    bool-exp AND bool-exp    T
     /    \
    T       F
    
    1. & 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            4
    

    Note: 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 to 5*3+1+4 twice, 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.