---++ Description
AsFix (ASF+SDF fixed format) is a format for representing [[Transform.ParseTree][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 Stratego.StrategoXT program transformation systems usually operate on [[Stratego.AbstractSyntaxTree][abstract syntax trees]]. The AsFix2 output of [[Sdf.SGLR][SGLR]] is transformed into an abstract syntax tree by [[%MANUAL%/ref-implode-asfix.html][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 [[AsFixYield][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.WebHome][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("")
, 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("")
, 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 [[%MANUAL%/ref-implode-asfix.html][implode-asfix]] to reduce this to an abstract syntax tree:
echo "1 + a" | sglr -2A -p Exp.tbl | implode-asfix | pp-aterm
results in:
Plus(Int("1"), Var("a"))
[[%MANUAL%/ref-implode-asfix.html][implode-asfix]] only accepts AsFix2. The [[ImplodeParseTree][implodePT]] (part of the pt-support package, which is in the [[Stratego.Sdf2Bundle][sdf2-bundle]]) implements the same implosion for AsFix2ME.
echo "1 + a" | sglr -mA -p Exp.tbl | implodePT | pp-aterm
produces
Plus(Int("1"), Var("a"))