As Fix

Description

AsFix (ASF+SDF fixed format) is a format for representing parse trees in the ATerm format.

Currently two versions of AsFix are in used: AsFix2ME and AsFix2. AsFix2 is extremely verbose since layout and literals have a structured representation in AsFix2. AsFix2ME is a more concise since lists, layout and literals are flattened. This is the parse tree format that is used in the ASF+SDF Meta-Environment.

Application

The SGLR parser outputs the result of parsing an input in the AsFix format. The most recent versions of SGLR produce AsFix2ME by default. SGLR produces AsFix2 when the -2 flag is used.

In StrategoXT program transformation systems usually operate on abstract syntax trees. The AsFix2 output of SGLR is transformed into an abstract syntax tree by implode-asfix.

Format Internals

Usually you don't actually want to see an AsFix2 or AsFix2ME parse tree. AsFix takes the job of representing the result of parsing an input very serious. It includes all information required to reproduce the original input. This unparsing is implemented by the asfix-yield tool. The AsFix format exactly describes what kind of productions are applied. An AsFix representation is self-contained: all grammar information needed to interpret a term is also included.

Example

Consider the following SDF syntax definition.

  definition
  module Exp
  exports
    sorts Exp

    lexical syntax
      [\ \t\n]  -> LAYOUT
      [a-zA-Z]+ -> Id
      [0-9]+    -> IntConst

    context-free syntax
      Id        -> Exp {cons("Var")}
      IntConst  -> Exp {cons("Int")}

      Exp "*"  Exp -> Exp  {left, cons("Mul")}
      Exp "/"  Exp -> Exp  {left, cons("Div")}
      Exp "%"  Exp -> Exp  {left, cons("Mod")}

      Exp "+"  Exp -> Exp  {left, cons("Plus")}
      Exp "-"  Exp -> Exp  {left, cons("Minus")}

    context-free priorities
      {left:
        Exp "*"  Exp -> Exp
        Exp "/"  Exp -> Exp
        Exp "%"  Exp -> Exp
      }
    > {left:
        Exp "+"  Exp -> Exp
        Exp "-"  Exp -> Exp
      }

PGEN's sdf2table produces an SGLR parse table from this syntax definition:

  sdf2table -m Exp -i Exp.def -o Exp.tbl

Parsing to AsFix2ME

Parsing the expression 1 + a to the compact AsFix variant AsFix2ME using:

  echo "1 + a" | sglr -m -A -p Exp.tbl | pp-aterm

produces the following parse tree:

parsetree(
  appl(
    prod(
      [cf(opt(layout)), cf(sort("Exp")), cf(opt(layout))]
    , sort("<START>")
    , no-attrs
    )
  , [ appl(prod([], cf(opt(layout)), no-attrs), [])
    , appl(
        prod(
          [ cf(sort("Exp"))
          , cf(opt(layout))
          , lit("+")
          , cf(opt(layout))
          , cf(sort("Exp"))
          ]
        , cf(sort("Exp"))
        , attrs([assoc(left), term(cons("Plus"))])
        )
      , [ appl(
            prod(
              [cf(sort("IntConst"))]
            , cf(sort("Exp"))
            , attrs([term(cons("Int"))])
            )
          , [ appl(
                prod(
                  [lex(sort("IntConst"))]
                , cf(sort("IntConst"))
                , no-attrs
                )
              , [ appl(
                    list(iter-star(char-class([range(0, 255)])))
                  , [49]
                  )
                ]
              )
            ]
          )
        , appl(
            prod([cf(layout)], cf(opt(layout)), no-attrs)
          , [32]
          )
        , lit("+")
        , appl(
            prod([cf(layout)], cf(opt(layout)), no-attrs)
          , [32]
          )
        , appl(
            prod(
              [cf(sort("Id"))]
            , cf(sort("Exp"))
            , attrs([term(cons("Var"))])
            )
          , [ appl(
                prod(
                  [lex(sort("Id"))]
                , cf(sort("Id"))
                , no-attrs
                )
              , [ appl(
                    list(iter-star(char-class([range(0, 255)])))
                  , [97]
                  )
                ]
              )
            ]
          )
        ]
      )
    , appl(
        prod([cf(layout)], cf(opt(layout)), no-attrs)
      , [10]
      )
    ]
  )
, 0
)

Parsing to AsFix2

Parsing the same expression to AsFix2:

  echo "1 + a" | sglr -2 -A -p Exp.tbl | pp-aterm

results in:

parsetree(
  appl(
    prod(
      [cf(opt(layout)), cf(sort("Exp")), cf(opt(layout))]
    , sort("<START>")
    , no-attrs
    )
  , [ appl(prod([], cf(opt(layout)), no-attrs), [])
    , appl(
        prod(
          [ cf(sort("Exp"))
          , cf(opt(layout))
          , lit("+")
          , cf(opt(layout))
          , cf(sort("Exp"))
          ]
        , cf(sort("Exp"))
        , attrs([assoc(left), term(cons("Plus"))])
        )
      , [ appl(
            prod(
              [cf(sort("IntConst"))]
            , cf(sort("Exp"))
            , attrs([term(cons("Int"))])
            )
          , [ appl(
                prod(
                  [lex(sort("IntConst"))]
                , cf(sort("IntConst"))
                , no-attrs
                )
              , [ appl(
                    prod(
                      [lex(iter(char-class([range(48, 57)])))]
                    , lex(sort("IntConst"))
                    , no-attrs
                    )
                  , [ appl(
                        prod(
                          [char-class([range(48, 57)])]
                        , lex(iter(char-class([range(48, 57)])))
                        , no-attrs
                        )
                      , [49]
                      )
                    ]
                  )
                ]
              )
            ]
          )
        , appl(
            prod([cf(layout)], cf(opt(layout)), no-attrs)
          , [ appl(
                prod([lex(layout)], cf(layout), no-attrs)
              , [ appl(
                    prod(
                      [char-class([range(9, 10), 32])]
                    , lex(layout)
                    , no-attrs
                    )
                  , [32]
                  )
                ]
              )
            ]
          )
        , appl(
            prod([char-class([43])], lit("+"), no-attrs)
          , [43]
          )
        , appl(
            prod([cf(layout)], cf(opt(layout)), no-attrs)
          , [ appl(
                prod([lex(layout)], cf(layout), no-attrs)
              , [ appl(
                    prod(
                      [char-class([range(9, 10), 32])]
                    , lex(layout)
                    , no-attrs
                    )
                  , [32]
                  )
                ]
              )
            ]
          )
        , appl(
            prod(
              [cf(sort("Id"))]
            , cf(sort("Exp"))
            , attrs([term(cons("Var"))])
            )
          , [ appl(
                prod(
                  [lex(sort("Id"))]
                , cf(sort("Id"))
                , no-attrs
                )
              , [ appl(
                    prod(
                      [ lex(
                          iter(
                            char-class([range(65, 90), range(97, 122)])
                          )
                        )
                      ]
                    , lex(sort("Id"))
                    , no-attrs
                    )
                  , [ appl(
                        prod(
                          [char-class([range(65, 90), range(97, 122)])]
                        , lex(
                            iter(
                              char-class([range(65, 90), range(97, 122)])
                            )
                          )
                        , no-attrs
                        )
                      , [97]
                      )
                    ]
                  )
                ]
              )
            ]
          )
        ]
      )
    , appl(
        prod([cf(layout)], cf(opt(layout)), no-attrs)
      , [ appl(
            prod([lex(layout)], cf(layout), no-attrs)
          , [ appl(
                prod(
                  [char-class([range(9, 10), 32])]
                , lex(layout)
                , no-attrs
                )
              , [10]
              )
            ]
          )
        ]
      )
    ]
  )
, 0
)

Producing an Abstract Syntax Tree

Applying implode-asfix to reduce this to an abstract syntax tree:

  echo "1 + a" | sglr -2A -p Exp.tbl | implode-asfix | pp-aterm

  Plus(Int("1"), Var("a"))

implode-asfix only accepts AsFix2. The implodePT (part of the pt-support package, which is in the sdf2-bundle) implements the same implosion for AsFix2ME.

  echo "1 + a" | sglr -mA -p Exp.tbl | implodePT | pp-aterm

  Plus(Int("1"), Var("a"))