CS374: Programming Language Principles - Abstract Syntax Trees

Activity Goals

The goals of this activity are:
  1. To define an Abstract Syntax Tree for a given grammar
  2. To augment grammars with attribute grammars

The Activity

Directions

Consider the activity models and answer the questions provided. First reflect on these questions on your own briefly, before discussing and comparing your thoughts with your group. Appoint one member of your group to discuss your findings with the class, and the rest of the group should help that member prepare their response. Answer each question individually from the activity on the Class Activity Questions discussion board. After class, think about the questions in the reflective prompt and respond to those individually in your notebook. Report out on areas of disagreement or items for which you and your group identified alternative approaches. Write down and report out questions you encountered along the way for group discussion.

Model 1: Attribute Grammars

?
1
2
3
4
5
6
7
/* From https://en.wikipedia.org/wiki/Attribute_grammar */
Expr → Expr + Term
Expr → Term
Term → Term * Factor
Term → Factor
Factor → "(" Expr ")"
Factor → integer

?
1
2
3
4
5
6
7
8
/* From https://en.wikipedia.org/wiki/Attribute_grammar */
/* S-Attributed Grammar: Synthesized Values, but no Inherited Attributes (from neighboring nonterminals in the production) */
Expr1 → Expr2 + Term [ Expr1.value = Expr2.value + Term.value ]
Expr → Term [ Expr.value = Term.value ]
Term1 → Term2 * Factor [ Term1.value = Term2.value * Factor.value ]
Term → Factor [ Term.value = Factor.value ]
Factor → "(" Expr ")" [ Factor.value =  Expr.value ]
Factor → integer [ Factor.value = strToInt(integer.str) ]

Questions

  1. Where do you think inherited attributes might come from?
  2. What are some other attributes you might associate with productions?

Model 2: Abstract Syntax Trees (AST)

Abstract syntax tree for Euclidean algorithm
?
1
2
3
4
5
6
7
8
/* From https://en.wikipedia.org/wiki/Abstract_syntax_tree */
euclidean_gcd(a, b):
    while b ≠ 0
      if a > b
        a := a − b
      else
        b := b − a
    return a

Questions

  1. In what ways is this simpler than a full parse tree? What items are retained, and which are omitted?

Submission

Submit your answers to the questions using the Class Activity Questions discussion board. You may also respond to questions or comments made by others, or ask follow-up questions there. Answer any reflective prompt questions in the Reflective Journal section of your OneNote Classroom personal section.