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
results in:
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
produces
Plus(Int("1"), Var("a"))