Lab 2: Disambiguation

Project
September 14, 2021

In this lab you adapt and extend the syntax definition of the previous lab with disambiguation rules and layout constraints in order to ensure that the syntax definition is unambiguous.

Objectives

Adapt and extend the syntax definition that you developed in the previous lab such that it

  1. is an idiomatic SDF3 definition
  2. realizes disambiguation using declarative disambiguation rules
  3. defines layout constraints to enforce layout-sensitive syntax

Disambiguation Rules

Section 4.1 of the ChocoPy reference manual specifies the precedence and associativity rules of the language. Translate this into associativity and priority rules in SDF3.

You need disambiguation constructs to disambiguate your syntax definition. You can specify the associativity with attributes left, right, or non-assoc (See documentation). These attributes are added to the end of a rule:

context-free syntax
  Exp.Constr1 = ... {left}

You can specify precedence in a context-free priorities section. In this section, you order groups of rules:

context-free priorities
  {
    Exp.Constr1
    Exp.Constr2
  } > { ... } > ...

You can also define the associativity of a group:

context-free priorities
  { left:
    Exp.Constr1
    Exp.Constr2
  } > { ... } > ...

Finally you should also consider specifying a bracket rule for disambiguation of expressions.

Layout Constraints

The syntax of ChocoPy is layout-sensitive, meaning that indentation and newlines are significant. To enable layout-sensitive parsing in Spoofax 3, we need to make some changes to the spoofaxc.cfg file. In the spoofaxc.cfg file, replace:

sdf3 {}

with:

sdf3 {
  parse-table-generator {
    layout-sensitive = true
  }
}

and replace:

parser {
  default-start-symbol = sort Start
}

with:

parser {
  default-start-symbol = sort Start
  variant = jsglr2 {
    preset = LayoutSensitive
  }
}

In the ChocoPy grammar in Figure 3 in the reference manual, layout-sensitive parsing is defined using NEWLINE, INDENT, and DEDENT tokens. Section 3.1 describes the meaning of these tokens.

Translate these tokens into layout constraints and layout declarations as presented in Lecture 3 and in the papers cited below.

Additional documentation on layout constraints can also be found in the Spoofax 2 documentation. Please note that this documentation is for Spoofax 2, and may therefore not fully correspond to Spoofax 3 behavior.

CExpr and Expr

The ChocoPy reference manual uses two separate expression sorts in its grammar, in order to keep compatibility with Python and to disambiguate. SDF3 has disambiguation features that makes this separation of sorts unneccessary. As a result, we expect you to implement a grammar that only uses a single expression sort. For more information on grading, see milestone 1.

One particularity is that ChocoPy does not allow any binary operators that feature expressions such as negation on the right-hand side. Indeed, True == not False is invalid syntax in ChocoPy. In order to emulate this restriction using a flattened grammar in SDF3, you can use the following priority directive syntax:

context-free priorities
  A.CA <n> .> B.CB

This restriction states that the n-th (0-indexed) child of A.CA cannot be a term of type B.CB. For example:

context-free grammar
  Expr.Eq = <<Expr> == <Expr>>
  Expr.Not = <not <Expr>>

context-free priorities
  Expr.Eq <2> .> Expr.Not

This will reject a not expression from appearing on the right-hand side of an equality expression.

Using this syntax and other SDF3 disambiguation features discussed in the lectures, you should be able to implement a ChocoPy grammar in SDF3 that adheres to the reference manual while only using a single sort for expressions.

References