← CS3300

SDD workbench

Input & parse tree

Local tree

● Current● DependencyClick a node to inspect

Grammar & semantic rules

One production per block, followed by its equations. The first production sets the start symbol. Use epsilon for an empty right-hand side. self is the left-hand-side occurrence; E@left names a right-hand-side occurrence left. An unaliased symbol can be referenced by its name if it occurs once.

Rule language and things to try

Equations are declarative: their written order does not determine evaluation order. Each step evaluates one equation whose inputs are available. self.attr defines a synthesized attribute; child.attr defines an inherited attribute on that child. Terminals provide .lexeme. The lexer recognizes identifiers (id), nonnegative decimal numbers (num), relational operators (rel), and literal grammar tokens. The whole-program preset also includes unary minus.

  • Leaf(text), Node(op, left, right): create AST nodes.
  • newTemp(), newLabel(): allocate one fresh name when that equation is evaluated. %t names cannot collide with source identifiers.
  • empty(), concat(code, ...): empty code and code concatenation (the slide’s ||).
  • bin(temp, op, left, right): emit a three-address instruction.
  • branch(addr, yes, no): emit if addr goto yes; goto no.
  • label(name), jump(name): emit a label or unconditional jump.
  • copy(variable, addr), print(addr): emit an assignment or print instruction.

Use double-quoted strings, numeric literals, attribute references, and these helpers. Comments start with # on their own line. Write separate productions instead of | alternatives. Rules are interpreted locally; no JavaScript is executed from the editor.

  1. Compare both AST presets on x - 2 * y - z. Why are their ASTs identical despite different parse trees?
  2. Swap the operands of subtraction in a Node rule. Which dependency edges and AST change?
  3. In the boolean preset, try x=50, then x=150, then x=250, y=250. Which comparisons execute?
  4. Replace self.node = T.node by self.node = self.node to see a dependency-cycle diagnostic.

The parser accepts left recursion and epsilon, and rejects ambiguous inputs. The dependency graph is for this input’s parse tree; a successful run does not prove that the SDD is noncircular for every input. Expression inputs are limited to 60 tokens; whole programs allow 500. IR execution stops at the end of the code, or at L_true/L_false for the standalone boolean preset.

Attribute inspector


    
StepAttributeKindEquationValue

  
  
    
Using the workbench

    

      

      
Build an input, then step through its semantic equations. The current rule shows the attributes it reads and the value it produces. The AST or code grows alongside it.

      
Use Inspect for the full attribute table, and Edit SDD to change the grammar or equations. For IR, Finish the translation and Run IR. Step through execution to see values, output, and the active instruction together.

      
Large trees fit the panel. Long source and IR panels scroll independently; the current line is kept in view automatically.

      
Whole-program language
      

        
This is a small numeric language for the course. Programs are sequences of statements; blocks and control flow can nest.

        
    
          
  • x = expression;, print(expression);, and { statements }.
    • 
          
  • if (condition) { statements }, with an optional else { statements }.
    • 
          
  • while (condition) { statements }. Braces are required for every control-flow body, making nested else clauses unambiguous.
    • 
          
  • Arithmetic: + - * / %, unary minus, and parentheses. Conditions: comparisons < <= > >= == !=, true, false, and short-circuit ! && ||.
    • 
          
  • Comments: // to end of line and /* block comment */.
    • 
        

        
Variables have one program-wide scope and numeric values. Assign before use, or provide initial values before running. Division is real-valued; % is remainder. Conditions are separate from numeric expressions, so write x != 0 rather than if (x). There are no declarations, arrays, functions, strings, or break/continue. Numbers use JavaScript’s finite floating-point arithmetic.

        
Build translates the whole program immediately. Select an IR instruction to find its source line and semantic equation. Use “Replay translation” to revisit attribute evaluation, then “Run IR” to execute and inspect the runtime trace. Generated labels and copies are deliberately left unoptimized so the SDD remains visible.

        
Limits: 500 tokens, 8,000 source characters, and 10,000 executed instructions. A runtime error retains the trace up to the failing instruction.