match(‘f’); }else Error(); }//B
int main(){ getToken(); S();
return 0; }//main
问题2：
exp → exp addop term | term addop → + | -
term → term mulop factor | factor mulop → * | /
factor → ( exp ) | number 请写出递归子程序分析算法。
解：先消除左递归，得到 exp → term { addop term } addop → + | -
term → factor { mulop factor } mulop → * | /
factor → ( exp ) | number
程序如下：
void match( expectedToken ){ if( token == expectedToken ) getToken();
else
Error(); }
void exp(){ term();
while( token == ‘+’ || token == ‘-’ ){ match(token); term(); } }
void term(){ factor();
while( token == ‘*’ || token == ‘/’ match(token); factor(); } }
void factor(){
if( token == ‘(’ ){
match(‘(’); exp();
match(‘)’);
){ }else if( token == number ){ match(number); }else Error(); }
int main(){ }
写出递归构建语法树的程序：
void match( expectedToken ){ if( token == expectedToken ) getToken();
else Error(); }
BtreeNode * exp(){
BtreeNode * Node, * tempNode; Node = term();
while( token == ‘+’ || token == ‘-’ ){ tempNode = new BtreeNode; tempNode->data = token; match(token);
tempNode->lchild = Node; tempNode->rchild = term(); Node = tempNode; }
return Node; }
BtreeNode * term(){
BtreeNode * Node, * tempNode; Node = factor();
while( token == ‘*’ || token == ‘/’ ){ tempNode = new BtreeNode; tempNode->data = token; match(token);
tempNode->lchild = Node;
tempNode->rchild = factor(); Node = tempNode; }
return Node; }
getToken(); exp(); return 0;
BtreeNode * factor(){ BtreeNode * Node; if( token == ‘(’ ){
match(‘(’); Node = exp(); match(‘)’);
}else if( token == number ){ Node = new BtreeNode; Node->data = token; match(number);
Node->lchild = Node->rchild = NULL; }else Error(); return Node; }
int main(){ }
例4.3 消除下面文法的左递归 解：
例4.9 考虑简单整型算术表达式的文法： exp → exp addop term | term addop → + | -
term → term mulop factor | factor mulop → * | /
factor → ( exp ) | number
先消除A的直接左递归：
A → Ba{a} | c{a}
B → Bb | Ba{a}b | c{a}b | d B → (d|c{a}b){(b|a{a}b)} 再将其代入到B的文法表达式中： 再消除B的直接左递归： A → Ba | Aa | c B → Bb | Ab | d BtreeNode *root; getToken(); root = exp(); return 0;
