The Dangling Else Problem
(Released October 18, 2005)
Note: This was the result of a discussion that appeared in the comp.compilers newsgroup. You can find the original discussion here.
The Motivation for the Study
APG – an ABNF Parser Generator – is, a general-purpose parser generator which I believe is on a peer level with the Earley and GLR algorithms. It can generate parsers for fully context-free grammars(*) and should compete favorably with them both in terms of the speed of the parsers it generates – both the speed of development time and the speed of the actual parsing of strings.
In fact, it should always perform better than those two methods, because in its present form it always selects only one specific parse tree from the multitude when the grammar is ambiguous. While APG could easily be modified to select other trees or even generate them all in parallel, is it really necessary to do so? To preserve the simplicity and parsing performance of selecting only one, well-defined parse tree for ambiguous grammars, this study examines three other alternatives to the multiple parse tree strategy for the "dangling else" problem.
The next section describes the problem and defines the notation that will be used through the remaining sections. Four sections then follow describing the standard solution and three alternatives. The last section gives a C-language program which demonstrates the application of all methods discussed.
(*) OK, non-left recursive grammars for finite string languages. This is not a restriction on the languages that it can parse – you can always eliminate left recursion – but if you really insist on a left-recursive grammar, then, no, you need another algorithm. But, it is not restricted in the LL or LR sense.
The Problem Definition and Notation
I'll be using the definitions and discussion of the "dangling-else" grammar in the Dragon Book, pgs. 174-175 as reference. I'll be examining different grammars, parse trees, translations and semantic actions. To keep things straight I'll use the following notations:
Grammars: G(i), i = 0,1,2 Parse Trees: P(i), i = 1,2,3,4 Translations: T(i), i = 1,2 Semantic Actions: A(i), i=0,1,2,3,4,5,6
All G(i), P(i), T(i) and A(i) referred to in this discussion are given explicit definitions in the Demonstration Program section below. A single function, vTranslate() is also defined there which combines a parse tree and set of semantic actions as input and generates a translation as output:
T(i) = vTranslate( P(j), A(k) );
I'll be using ABNF for the grammar notation, but in most cases this will not differ significantly from the notation in the Dragon Book. The original grammar given in the Dragon Book is:
G(0):
stmt = if expr then stmt /
if expr then stmt else stmt /
other
For this study, rather than consider if, then, else as tokens, we will take them at face value and complete the grammar with:
if = "if" then = "then" else = "else" expr = "E" other = "S"
We consider the string if "E then if E then S else S". (Note: the grammar above does not allow spaces, but are included here for readability.) Using C-style scope notation to bracket all statements except the first, we easily see that there are two ways to interpret this string. The first, translation is to associate the "else" with the closest "then".
T(1):
if E1 then {if E2 then {S1} else S2}}.
The second, translation is to associate the "else" with the furthest "then".
T(2):
if E1 then {if E2 then {S1}} else {S2}.
The translations T(1) and T(2) are the only translations we will be considering here. It is assumed here that if we can insert the scope brackets as shown above, any other type of translation requiring the same "then"/"else" associativity could also be done.
For parse trees, I will use an array notation instead of the tree-branch diagrams. Consider a depth-first traversal of a parse tree diagram in Fig. 4.6 of the Dragon Book. Each node is traversed twice – once going down a branch of the tree and once coming up. Reading off the rule names and traversal direction as we go, we get a linear array of nodes. The first parse tree P(1), would be represented as follows (indentation levels indicate the nesting levels – or tree depth – of the rule names):
P(1): stmt(down) if(down) if(up) expr(down) expr(up) then(down) then(up) stmt(down) if(down) if(up) expr(down) expr(up) then(down) then(up) stmt(down) other(down) other(up) stmt(up) else(down) else(up) stmt(down) other(down) other(up) stmt(up) stmt(up) stmt(up)
Semantic actions can then be attached to a parse tree by creation an array of function pointers. For example, the semantic actions A(0) which translate P(1) to T(1) would be:
A(0):
static int iStmtCount = 0;
void if_up(){printf("if ");}
void expr_up(){printf("(E%d) ",
++iExprCount);}
void then_up(){printf("then ");}
void else_up(){printf(" else ");}
void other_up(){printf("S%d", ++iOtherCount);}
void stmt_down()
{
if(iStmtCount > 0){printf("{");}
++iStmtCount;
}
void stmt_up()
{
--iStmtCount;
if(iStmtCount > 0){printf("}");}
}
Then, assuming an ordering of
enum
{
IF=0, THEN, ELSE, EXPR, OTHER, STMT
};
the semantic actions can be completely specified with an array of function pointers
SEMANTIC_ACTION g_A0[] =
{
{NULL, if_up},
{NULL, then_up},
{NULL, else_up},
{NULL, expr_up},
{NULL, other_up},
{stmt_down, stmt_up},
{NULL, NULL},
{NULL, NULL}
};
All omitted functions, such as if_down(), have pointers and no action is performed.
Now, all that the translation function vTranslate() has to do is iterate through the parse tree and call the appropriate action function, if any, for each node.
Four Strategies
The Multiple-Parse-Tree Strategy
The classical solution is to use the nesting levels of the parse trees to guide the translation. That is, we associate the "else" keyword with the "then" keyword that appears at the same nesting level. This in effect says that after choosing the actions A(0) we change the translation by changing the parse tree. That is:
T(1) = A(0) + P(1) T(2) = A(0) + P(2)
With this approach, we have to know what the parse trees are and which one to use to get the translation we want.
The Simulated-Parse-Tree Strategy
Here I demonstrate that rather than modify the choice of parse tree, we can alternatively modify the semantic actions. If we insist on basing the "else"/"then" association on the parse tree nesting level, it is still possible to get either translation from either parse tree. For this we define A(1) and A(2) such that:
T(1) = A(1) + P(2) T(2) = A(2) + P(1)
The Unambiguous-Grammar Strategy
Another approach is to use an unambiguous grammar that generates the same language. The translation is identical to the multiple parse tree strategy, but we eliminate the need to select the correct parse tree from the multitude. The grammar generates only the one we want. To this end the Dragon Book defines grammar:
G(1):
stmt = matched-stmt /
unmatched-stmt
matched-stmt = if expr then matched-stmt else matched-stmt /
other
unmatched-stmt = if expr then stmt /
if expr then matched-stmt else unmatched-stmt
This will generate a parse tree P(3) which although not exactly the same as P(1), still has the same feature of putting the "else" on the same nesting level as the closest "then". We will then get:
T(1) = A(3) + P(3)
Similarly we can write an unambiguous grammar G(2) which generates P(4) with the same nesting levels as P(2). That is, "else" appears at the same nesting level as the furthest "then". (Note: Grammar G(2) is somewhat contrived, but it illustrates the point that such a grammar can be found.)
G(2):
stmt = if-stmt [else-stmt] /
other-stmt
if-stmt = if-open if-stmt if-close /
if-open other-stmt if-close
if-open = if expr then
if-close = [%d0] ; empty string acceptor
else-stmt = else stmt
other-stmt = other
We then get:
T(2) = A(4) + P(4)
The Universal-Translation Strategy
The universal translation strategy is to recognize that the different translations are making different associations between the "then" and "else" keywords. Putting the translation logic into the "then" and "else" rules for the semantic actions instead of the "stmt" rule, we can define A(5) and A(6) such that:
T(1) = A(5) + P(1) T(1) = A(5) + P(2) T(2) = A(6) + P(1) T(2) = A(6) + P(2)
In fact, A(5) will translate any parse tree from any grammar in this study to T(1) and A(6) will translate any parse tree to T(2). That is because they only depend on the matched string, not on the tree structure.
Discussion
No doubt this is all vulnerable to a certain amount of nitpicking – that doesn't work when you change this, etc. And, in the real world of real computer languages, there may be other issues. I'm not that experienced. However, what I have done here is show that for one specific string for one specific ambiguous grammar, there are at least three other alternatives to the "classical" solution of sorting through the forest of parse trees for just the right one for the wanted interpretation. I've shown that either translation can be had from either parse tree. I've shown that unambiguous grammars can be developed for whichever parse tree is wanted. And I've even shown that there are semantic actions that translate consistently independent of the parse tree.
It would be nice if this were true for all ambiguous grammars. My guess is that at a minimum these results are true for a large class of ambiguous grammars and their matching strings. The mathematics is beyond my reach, but it would be nice if some theoretical work could establish rigorous bounds for these statements.
But at the moment it would seem to me that with a) a clear definition of the language, b) a judiciously chosen grammar and c) a judiciously chosen set of semantic actions the job can be done with a single, well-defined parse tree and with the computational economy that goes along with it.
The Demonstration Program
(download CompCompilersDEDemo.c)
/*************************************************************************
Copyright (c) 2005 Coast to Coast Research, Inc.
author: Lowell Thomas
lowell@coasttocoastresearch.com
http://www.coasttocoastresearch.com
The following program has been run only under Windows XP and
MS Visual Studio 6.0. However, it should be OS independent.
I would be happy if you would report any problems encountered
with other development environments or of any other kind.
*************************************************************************/
//////////////////////////////////////////////////////////////////////////
// HEADER FILES
//////////////////////////////////////////////////////////////////////////
#include <stdio.h>
//////////////////////////////////////////////////////////////////////////
// DECLARATIONS
//////////////////////////////////////////////////////////////////////////
// direction identifiers
enum {DOWN=0, UP} eDirection;
// rule name identifiers
enum
{
IF=0, THEN, ELSE, EXPR, OTHER, STMT, // G(0) identifiers
MATCHED_STMT, UNMATCHED_STMT, // G(1) identifiers
IF_STMT, ELSE_STMT, OTHER_STMT, IF_OPEN, IF_CLOSE, // G(2) identifiers
ACTION_MAX
} eActions;
// semantic action function pointer
typedef void (*PFN_ACTION)();
// parse tree node struct
typedef struct tag_node
{
int iRule;
int iDirection;
} TREE_NODE;
// semantic action struct
typedef struct tag_action
{
PFN_ACTION pfnDown;
PFN_ACTION pfnUp;
} SEMANTIC_ACTION;
//////////////////////////////////////////////////////////////////////////
// TRANSLATOR
// translates a parse tree(P) + semantic actions(A) to a translation(T)
//////////////////////////////////////////////////////////////////////////
// global variables used by the semantic actions
static int g_iExprCount = 0;
static int g_iStmtCount = 0;
static int g_iStmtDirection = 0;
static int g_iOtherCount = 0;
static int g_iBracketCount = 0;
void vTranslate(char* cpHeader, TREE_NODE* spParseTree,
int iNodeCount, SEMANTIC_ACTION* spSemanticActions)
{
// declarations
TREE_NODE* spBeg;
TREE_NODE* spEnd;
int iRule;
int iDirection;
PFN_ACTION pfnAction;
if(cpHeader)
{
// print the header
printf("\n");
printf(cpHeader);
printf("\n");
}
// initialize the global variables
g_iExprCount = 0;
g_iStmtCount = 0;
g_iStmtDirection = DOWN;
g_iOtherCount = 0;
g_iBracketCount = 0;
// iterate over all nodes of the parse tree
spBeg = spParseTree;
spEnd = spBeg + iNodeCount;
while(spBeg < spEnd)
{
// get the rule name and direction
iRule = spBeg->iRule;
iDirection = spBeg->iDirection;
// get the semantic action function
if(iDirection == DOWN){pfnAction = spSemanticActions[iRule].pfnDown;}
else{pfnAction = spSemanticActions[iRule].pfnUp;}
// execute the action, if any
if(pfnAction){pfnAction();}
++spBeg;
}
printf("\n");
}
//////////////////////////////////////////////////////////////////////////
// THE INPUT STRING
// single input string used for all translations and all grammars
//////////////////////////////////////////////////////////////////////////
char* g_cpInputString = "ifEthenifEthenSelseS";
//////////////////////////////////////////////////////////////////////////
// THE TRANSLATIONS
// two translations of the input string
//////////////////////////////////////////////////////////////////////////
char* g_T1 = "if E1 then {if E2 then {S1} else {S2}}"; // T(1)
char* g_T2 = "if E1 then {if E2 then {S1}} else {S2}"; // T(2)
//////////////////////////////////////////////////////////////////////////
// GRAMMARS
// ABNF notation
//////////////////////////////////////////////////////////////////////////
/*
; Ambiguous Grammar G(0)
; Dragon Book, pg. 174
stmt = if expr then stmt /
if expr then stmt else stmt /
other
; UnAmbiguous Grammar G(1)
; Dragon Book, pg. 175
; Generates the same nesting structure as
; Ambiguous Grammar parse tree P(1)
stmt = matched-stmt /
unmatched-stmt
matched-stmt = if expr then matched-stmt else matched-stmt /
other
unmatched-stmt = if expr then stmt /
if expr then matched-stmt else unmatched-stmt
; UnAmbiguous Grammar G(2)
; LDT - Coast to Coast Research, Inc.
; Generates the same nesting structure as
; Ambiguous parse tree P(2)
stmt = if-stmt [else-stmt] /
other-stmt
if-stmt = if-open if-stmt if-close /
if-open other-stmt if-close
if-open = if expr then
if-close = [%d0] ; empty string acceptor
else-stmt = else stmt
other-stmt = other
; rules constant for all grammars
if = "if"
then = "then"
else = "else"
expr = "E"
other = "S"
*/
//////////////////////////////////////////////////////////////////////////
// PARSE TREES
// (indentations indicate rule name nesting levels)
//////////////////////////////////////////////////////////////////////////
// Parse Tree P(1)
// Dragon Book Fig. 4.6, page 175
// first parse tree
TREE_NODE g_P1[] =
{
{STMT, DOWN}, // stmt 1
{IF, DOWN},
{IF, UP},
{EXPR, DOWN},
{EXPR, UP},
{THEN, DOWN},
{THEN, UP},
{STMT, DOWN}, // stmt 2
{IF, DOWN},
{IF, UP},
{EXPR, DOWN},
{EXPR, UP},
{THEN, DOWN},
{THEN, UP},
{STMT, DOWN}, // stmt 3
{OTHER, DOWN},
{OTHER, UP},
{STMT, UP}, // stmt 3
{ELSE, DOWN},
{ELSE, UP},
{STMT, DOWN}, // stmt 4
{OTHER, DOWN},
{OTHER, UP},
{STMT, UP}, // stmt 4
{STMT, UP}, // stmt 2
{STMT, UP}, // stmt 1
};
// Parse Tree P(2)
// Dragon Book Fig. 4.6, page 175
// second parse tree
TREE_NODE g_P2[] =
{
{STMT, DOWN}, // stmt 1
{IF, DOWN},
{IF, UP},
{EXPR, DOWN},
{EXPR, UP},
{THEN, DOWN},
{THEN, UP},
{STMT, DOWN}, // stmt 2
{IF, DOWN},
{IF, UP},
{EXPR, DOWN},
{EXPR, UP},
{THEN, DOWN},
{THEN, UP},
{STMT, DOWN}, // stmt 3
{OTHER, DOWN},
{OTHER, UP},
{STMT, UP}, // stmt 3
{STMT, UP}, // stmt 2
{ELSE, DOWN},
{ELSE, UP},
{STMT, DOWN}, // stmt 4
{OTHER, DOWN},
{OTHER, UP},
{STMT, UP}, // stmt 4
{STMT, UP}, // stmt 1
};
// Parse Tree P(3)
// Generated from Grammar G(1) by APG
TREE_NODE g_P3[] =
{
{STMT, DOWN},
{ UNMATCHED_STMT, DOWN},
{ IF, DOWN},
{ IF, UP},
{ EXPR, DOWN},
{ EXPR, UP},
{ THEN, DOWN},
{ THEN, UP},
{ STMT, DOWN},
{ MATCHED_STMT, DOWN},
{ IF, DOWN},
{ IF, UP},
{ EXPR, DOWN},
{ EXPR, UP},
{ THEN, DOWN},
{ THEN, UP},
{ MATCHED_STMT, DOWN},
{ OTHER, DOWN},
{ OTHER, UP},
{ MATCHED_STMT, UP},
{ ELSE, DOWN},
{ ELSE, UP},
{ MATCHED_STMT, DOWN},
{ OTHER, DOWN},
{ OTHER, UP},
{ MATCHED_STMT, UP},
{ MATCHED_STMT, UP},
{ STMT, UP},
{ UNMATCHED_STMT, UP},
{STMT, UP},
};
// Parse Tree P(4)
// Generated from Grammar G(2) by APG
TREE_NODE g_P4[] =
{
{STMT, DOWN},
{ IF_STMT, DOWN},
{ IF_OPEN, DOWN},
{ IF, DOWN},
{ IF, UP},
{ EXPR, DOWN},
{ EXPR, UP},
{ THEN, DOWN},
{ THEN, UP},
{ IF_OPEN, UP},
{ IF_STMT, DOWN},
{ IF_OPEN, DOWN},
{ IF, DOWN},
{ IF, UP},
{ EXPR, DOWN},
{ EXPR, UP},
{ THEN, DOWN},
{ THEN, UP},
{ IF_OPEN, UP},
{ OTHER_STMT, DOWN},
{ OTHER, DOWN},
{ OTHER, UP},
{ OTHER_STMT, UP},
{ IF_CLOSE, DOWN},
{ IF_CLOSE, UP},
{ IF_STMT, UP},
{ IF_CLOSE, DOWN},
{ IF_CLOSE, UP},
{ IF_STMT, UP},
{ ELSE_STMT, DOWN},
{ ELSE, DOWN},
{ ELSE, UP},
{ STMT, DOWN},
{ OTHER_STMT, DOWN},
{ OTHER, DOWN},
{ OTHER, UP},
{ OTHER_STMT, UP},
{ STMT, UP},
{ ELSE_STMT, UP},
{STMT, UP},
};
//////////////////////////////////////////////////////////////////////////
// SEMANTIC ACTIONS
//////////////////////////////////////////////////////////////////////////
// A(0)
// Translates P(1) to T(1)
// Translates P(2) to T(2)
void A0_if_up(){printf("if ");}
void A0_expr_up(){printf("(E%d) ", ++g_iExprCount);}
void A0_then_up(){printf("then ");}
void A0_else_up(){printf(" else ");}
void A0_other_up(){printf("S%d", ++g_iOtherCount);}
void A0_stmt_down()
{
// except for start rule, open a scope bracket
if(g_iStmtCount > 0){printf("{");}
++g_iStmtCount;
}
void A0_stmt_up()
{
// except for start rule, close a scope bracket
--g_iStmtCount;
if(g_iStmtCount > 0){printf("}");}
}
SEMANTIC_ACTION g_A0[ACTION_MAX] =
{
{NULL, A0_if_up},
{NULL, A0_then_up},
{NULL, A0_else_up},
{NULL, A0_expr_up},
{NULL, A0_other_up},
{A0_stmt_down, A0_stmt_up},
{NULL, NULL},
{NULL, NULL}
};
// actions A(1)
// translates P(1) to T(2)
void A1_if_up(){printf("if ");}
void A1_expr_up(){printf("(E%d) ", ++g_iExprCount);}
void A1_then_up(){printf("then ");}
void A1_else_up(){printf(" else ");}
void A1_other_up(){printf("S%d", ++g_iOtherCount);}
void A1_stmt_down()
{
// except for start rule, open a scope bracket
if(g_iStmtCount > 0){printf("{");}
++g_iStmtCount;
}
void A1_stmt_up()
{
int i;
// close all open scope brackets
for(i = 1; i < g_iStmtCount; i++){printf("}");}
g_iStmtCount = 1;
}
SEMANTIC_ACTION g_A1[ACTION_MAX] =
{
{NULL, A1_if_up},
{NULL, A1_then_up},
{NULL, A1_else_up},
{NULL, A1_expr_up},
{NULL, A1_other_up},
{A1_stmt_down, A1_stmt_up},
{NULL, NULL},
{NULL, NULL}
};
// actions A(2)
// translates P(2) to T(1)
void A2_if_up(){printf("if ");}
void A2_expr_up(){printf("(E%d) ", ++g_iExprCount);}
void A2_then_up(){printf("then ");}
void A2_else_up(){printf(" else ");}
void A2_other_up(){printf("S%d", ++g_iOtherCount);}
void A2_stmt_down()
{
// except for start rule, open a scope bracket
if(g_iStmtCount > 0)
{
printf("{");
++g_iBracketCount;
}
++g_iStmtCount;
g_iStmtDirection = DOWN;
}
void A2_stmt_up()
{
if(g_iStmtDirection == DOWN)
{
// this is a leaf node - close just one bracket
printf("}");
--g_iBracketCount;
}
if(g_iStmtCount == 1)
{
// start rule - close all open scope brackets
while(g_iBracketCount)
{
printf("}");
--g_iBracketCount;
}
}
--g_iStmtCount;
g_iStmtDirection = UP;
}
SEMANTIC_ACTION g_A2[ACTION_MAX] =
{
{NULL, A2_if_up},
{NULL, A2_then_up},
{NULL, A2_else_up},
{NULL, A2_expr_up},
{NULL, A2_other_up},
{A2_stmt_down, A2_stmt_up},
{NULL, NULL},
{NULL, NULL}
};
// actions A(3)
// use A(0) functions with unambiguous grammar G(1) to get T(1)
SEMANTIC_ACTION g_A3[ACTION_MAX] =
{
{NULL, A0_if_up},
{NULL, A0_then_up},
{NULL, A0_else_up},
{NULL, A0_expr_up},
{NULL, A0_other_up},
{NULL, NULL},
{A0_stmt_down, A0_stmt_up},
{A0_stmt_down, A0_stmt_up}
};
// actions A(4)
// use A(0) functions with unambiguous grammar G(2) to get T(2)
void A4_other_stmt_down(){printf("{");++g_iStmtCount;}
void A4_other_stmt_up(){printf("}");--g_iStmtCount;}
SEMANTIC_ACTION g_A4[ACTION_MAX] =
{
{NULL, A0_if_up},
{NULL, A0_then_up},
{NULL, A0_else_up},
{NULL, A0_expr_up},
{NULL, A0_other_up},
{NULL, NULL}, // STMT
{NULL, NULL}, // MATCHED
{NULL, NULL}, // UNMATCHED
{A0_stmt_down, A0_stmt_up}, // IF_STMT
{NULL, NULL}, // ELSE_STMT
{A4_other_stmt_down, A4_other_stmt_up}, // OTHER_STMT
{NULL, NULL}, // IF_OPEN
{NULL, NULL} // IF_CLOSE
};
// actions A(5)
// translates all parse trees to T(1)
void A5_if_up(){printf("if ");}
void A5_expr_up(){printf("(E%d) ", ++g_iExprCount);}
void A5_then_up(){printf("then {");++g_iBracketCount;}
void A5_else_up(){printf(" else {");++g_iBracketCount;}
void A5_other_up(){printf("S%d", ++g_iOtherCount);
if(g_iBracketCount){printf("}");--g_iBracketCount;}}
void A5_stmt_down(){++g_iStmtCount;}
void A5_stmt_up()
{
--g_iStmtCount;
if(g_iStmtCount == 0)
{
// end of start rule - close any open brackets
while(g_iBracketCount)
{
printf("}");
--g_iBracketCount;
}
}
}
SEMANTIC_ACTION g_A5[ACTION_MAX] =
{
{NULL, A5_if_up},
{NULL, A5_then_up},
{NULL, A5_else_up},
{NULL, A5_expr_up},
{NULL, A5_other_up},
{A5_stmt_down, A5_stmt_up},
{NULL, NULL},
{NULL, NULL},
{NULL, NULL},
{NULL, NULL},
{NULL, NULL},
{NULL, NULL},
{NULL, NULL}
};
// actions A(6)
// translates all parse trees to T(2)
void A6_if_up(){printf("if ");}
void A6_expr_up(){printf("(E%d) ", ++g_iExprCount);}
void A6_then_up(){printf("then {");++g_iBracketCount;}
void A6_else_up(){printf(" else {");++g_iBracketCount;}
void A6_other_up(){printf("S%d", ++g_iOtherCount);
if(g_iBracketCount){printf("}");--g_iBracketCount;}}
void A6_else_down()
{
// close all the brackets opened by "then"s
while(g_iBracketCount)
{
printf("}");
--g_iBracketCount;
}
}
SEMANTIC_ACTION g_A6[ACTION_MAX] =
{
{NULL, A6_if_up},
{NULL, A6_then_up},
{A6_else_down, A6_else_up},
{NULL, A6_expr_up},
{NULL, A6_other_up},
{NULL, NULL},
{NULL, NULL},
{NULL, NULL},
{NULL, NULL},
{NULL, NULL},
{NULL, NULL},
{NULL, NULL},
{NULL, NULL}
};
//////////////////////////////////////////////////////////////////////////
// MAIN
//////////////////////////////////////////////////////////////////////////
int main(int argc, char* argv[])
{
// declarations
int iNodeCount;
char* cpHeader;
// print global header
printf("A - semantic actions\n");
printf("P - parse tree\n");
printf("T - translation\n");
// multiple parse tree strategy - ambiguous grammar G(0)
printf("\n");
printf("-------------------------------\n");
printf("*** multiple parse tree strategy");
cpHeader = "*** A(0) + P(1) => T(1)";
iNodeCount = sizeof(g_P1)/sizeof(g_P1[0]);
vTranslate(cpHeader, g_P1, iNodeCount, g_A0);
cpHeader = "*** A(0) + P(2) => T(2)";
iNodeCount = sizeof(g_P2)/sizeof(g_P2[0]);
vTranslate(cpHeader, g_P2, iNodeCount, g_A0);
printf("-------------------------------\n");
// simulate P(2) from P(1) with actions A(1)
printf("\n");
printf("-------------------------------\n");
printf("*** simulated parse tree strategy");
cpHeader = "*** A(1) + P(1) => T(2)";
iNodeCount = sizeof(g_P1)/sizeof(g_P1[0]);
vTranslate(cpHeader, g_P1, iNodeCount, g_A1);
// simulate P(1) from P(2) with actions A(2)
cpHeader = "*** A(2) + P(2) => T(1)";
iNodeCount = sizeof(g_P2)/sizeof(g_P2[0]);
vTranslate(cpHeader, g_P2, iNodeCount, g_A2);
printf("-------------------------------\n");
// unambiguous grammar strategy - unambiguous grammar G(1)
// A(3) + P(3) => T(1)
printf("\n");
printf("-------------------------------\n");
printf("*** unambiguous grammar strategy");
cpHeader =
"*** unambiguous grammar G(1) \n*** A(3) + P(3) => T(1)";
iNodeCount = sizeof(g_P3)/sizeof(g_P3[0]);
vTranslate(cpHeader, g_P3, iNodeCount, g_A3);
// unambiguous grammar strategy - unambiguous grammar G(2)
// A(4) + P(4) => T(2)
cpHeader =
"*** unambiguous grammar G(2) \n*** A(4) + P(4) => T(2)";
iNodeCount = sizeof(g_P4)/sizeof(g_P4[0]);
vTranslate(cpHeader, g_P4, iNodeCount, g_A4);
printf("-------------------------------\n");
// universal translation strategy
// A(5) generates T(1) for all parse trees
printf("\n");
printf("-------------------------------\n");
printf("*** universal translation strategy");
cpHeader = "*** A(5) + all parse trees => T(1)";
iNodeCount = sizeof(g_P1)/sizeof(g_P1[0]);
vTranslate(cpHeader, g_P1, iNodeCount, g_A5);
cpHeader = NULL;
iNodeCount = sizeof(g_P2)/sizeof(g_P2[0]);
vTranslate(cpHeader, g_P2, iNodeCount, g_A5);
iNodeCount = sizeof(g_P3)/sizeof(g_P3[0]);
vTranslate(cpHeader, g_P3, iNodeCount, g_A5);
iNodeCount = sizeof(g_P4)/sizeof(g_P4[0]);
vTranslate(cpHeader, g_P4, iNodeCount, g_A5);
// A(6) generates T(2) for all parse trees
cpHeader = "*** A(6) + all parse trees => T(2)";
iNodeCount = sizeof(g_P1)/sizeof(g_P1[0]);
vTranslate(cpHeader, g_P1, iNodeCount, g_A6);
cpHeader = NULL;
iNodeCount = sizeof(g_P2)/sizeof(g_P2[0]);
vTranslate(cpHeader, g_P2, iNodeCount, g_A6);
iNodeCount = sizeof(g_P3)/sizeof(g_P3[0]);
vTranslate(cpHeader, g_P3, iNodeCount, g_A6);
iNodeCount = sizeof(g_P4)/sizeof(g_P4[0]);
vTranslate(cpHeader, g_P4, iNodeCount, g_A6);
printf("-------------------------------\n");
return 0;
}
