Use an abstract syntax tree with the following constructors. Here
Expr denotes the separate abstract syntax tree type for a program expression, Name identifies a variable assignment target, and the square brackets denote an ordered list.Stmt = Assign(Name, Expr)
| Seq(Stmt, Stmt)
| Case(Expr, [(Expr, Stmt)])The list in
Case must be nonempty. Its first field is the controlling program expression; each pair contains a label program expression and the corresponding body. Keep the pairs in source order and keep repeated labels: this is an ordered search, with the first successful equality test choosing the body. A label is an abstract syntax tree for a program expression, not a previously evaluated integer or a key in a map data structure. Evaluating or reordering labels during compilation would change the specified programming language semantics.Seq(s,t) executes s before t. The delimiters begin and end need no surviving constructor: the parser uses them to determine the abstract syntax tree's grouping and then returns the enclosed tree. There are no declarations in these blocks that would require a separate binding environment. A list of statements could replace binary Seq; below we choose right-associated binary trees so that the semantic actions are precise.The essential representation is an ordered, nonempty list of expression/body pairs, together with assignment and sequencing nodes. In constructor notation,
Take the lexical tokens
ID, ASSIGN, SEMI, BEGIN, END, CASE, OF, COLON, and BAR, corresponding to identifiers and the displayed punctuation or keywords. Let E be the already defined context-free grammar category for a program expression, with attribute E.tree; expressions do not consume statement delimiters except inside their own explicitly delimited constructs. ID.name is the recognized program identifier. The following context-free grammar uses S for a statement, C for a closed elementary statement, D for a nonempty sequence of closed statements, and A for a nonempty arm list. The braces in this display are semantic actions, not input lexical tokens.S -> C { S.tree = C.tree }
S -> C SEMI S1 { S.tree = Seq(C.tree, S1.tree) }
S -> CASE E OF A { S.tree = Case(E.tree, A.arms) }
C -> ID ASSIGN E { C.tree = Assign(ID.name, E.tree) }
C -> BEGIN S END { C.tree = S.tree }
D -> C { D.tree = C.tree }
D -> C SEMI D1 { D.tree = Seq(C.tree, D1.tree) }
A -> E COLON S { A.arms = [(E.tree, S.tree)] }
A -> E COLON D BAR A1 { A.arms = [(E.tree, D.tree)] ++ A1.arms }Here
++ is list concatenation, and distinct suffixes distinguish occurrences of the same nonterminal symbol. Every statement and arm body is nonempty; no empty statement or optional trailing semicolon is needed for the supplied language.The distinction between
D and S resolves both possible sources of grammar ambiguity. First, an unbracketed CASE can occur only at the right end of an S: there is no production S -> S SEMI S. Consequently all semicolon-separated statements after such a CASE enter its last arm. Enclosing that whole CASE in BEGIN ... END turns it into a C, which can be followed by another statement outside the CASE.Second, an arm followed by another arm at the same level must have a
D body. Such a body contains no unbracketed CASE. If an arm body does contain an unbracketed CASE, only the final-arm production A -> E COLON S can apply, and every following BAR before the enclosing END or end of input must be consumed by the inner CASE. Thus each bar belongs to the nearest preceding CASE whose block has not ended. A CASE inside BEGIN ... END is hidden from that rule outside its block.For uniqueness, at any statement level an initial
ID or BEGIN determines a C; an immediately following SEMI determines the recursive sequence production. An initial CASE determines the third S production. In an arm, a bar at the current block level either follows an entirely closed body, forcing the second A production, or follows an unbracketed nested CASE, forcing it into that inner arm list. With an unambiguous expression sublanguage these choices leave a unique parse tree. Closed bodies before an outer bar, and a possibly open body only in the final arm, enforce the required interpretation. Thus the context-free grammar implementsLet
expr(e) generate postfix code that evaluates a program expression once, leaving one value above an otherwise unchanged evaluation stack. Let stmt(s) preserve the evaluation stack's height. Use EQ to pop two integers and push their Boolean equality result; JZ L pops that result and jumps to L when it is false. JMP is unconditional. All labels returned by fresh() are distinct, including labels inside recursively generated bodies.generateCase(Case(control, arms)):
done := fresh()
emit expr(control)
for (labelExpression, body) in arms, in source order:
next := fresh()
emit DUP
emit expr(labelExpression)
emit EQ
emit JZ next
emit POP
emit stmt(body)
emit JMP done
emit LABEL next
emit POP
emit LABEL doneTo verify the stack invariant, write the incoming evaluation stack as . Immediately before any label test it is , where is the controlling value.
DUP, evaluation of the label with value , and EQ change this to . JZ removes the Boolean. On failure the surviving is available for the next label; on success POP removes it before the body runs. The body therefore starts and ends with and jumps past every remaining label. If every label fails, the final POP restores .The controlling expression is evaluated once, each reached label is evaluated once, and no later label or arm is evaluated after a match. Keeping on the evaluation stack also preserves its original value if a label evaluation has a side effect that changes a variable appearing in the controlling program expression. A nested
Case uses the same stack invariant relative to whatever stack it receives. The concise contract is Articles by others on the same topic
There are currently no matching articles.