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;