|
- The (optional) abstract syntax of a language
may be specified by a simpler grammar than that for the concrete syntax.
For example,
-
-
<Exp> ::=
<Exp> + <Exp>
| <Exp> - <Exp>
| <Exp> * <Exp>
| <Exp> / <Exp>
| <id>
| - <Exp>
A grammar for the abstract syntax of simple arithmetic expressions
- Compared to the
concrete syntax,
the abstract syntax is ambiguous and is unsuitable
for direct use in building a parser.
However it is simpler than the concrete syntax and
is very suitable to build
the data-structure for the parse-tree returned by a parser, e.g.,
-
- datatype Exp = binexp of Exp * Bopr * Exp
| unexp of Uopr * Exp
| varid of Ide | ...
in [exp.sml].
-
- For example, given the input x+y*z either of the
following trees is possible according to the abstract syntax above
-
- Parse trees for x + y * z
correct bindings
| |
incorrect bindings
|
-
- but only the left tree is correct according to
the conventional concrete syntax.
- However the right tree would be the correct one given the input
(x+y)*z.
Note that there are no parentheses in the
abstract syntax above nor in the parse trees.
Parentheses are only needed to direct the parser to a certain parse and
are not required in a parse tree which shows the binding of
operators to operands by its very structure.
|
key |
::= |
"can be replaced by" |
-> |
| | "or by" |
=> | derivation |
lm |
left most |
rm |
right most |
|
|