广义表具有良好的递归结构,利用递归下降分析解析广义表字符串的合法性的C代码如下#includeiostream#includestring#includeutility#includememoryusingnamespacestd;enumclasstoken_type{left_bracket,right_bracket,comma,id};classToken{public:Token(token_type t):type(t),id(){}Token(conststringi):id(i),type(token_type::id){}token_type type;string id;};enumclasslexer_abnormal{end,illegal_char,success};pairshared_ptrToken,lexer_abnormallexer_parse(conststringgen,string::size_typei){if(igen.size())return{nullptr,lexer_abnormal::end};switch(gen[i]){case(:{i;return{make_sharedToken(Token(token_type::left_bracket)),lexer_abnormal::success};}case):{i;return{make_sharedToken(Token(token_type::right_bracket)),lexer_abnormal::success};}case,:{i;return{make_sharedToken(Token(token_type::comma)),lexer_abnormal::success};}default:{if(gen[i]33||gen[i]127){return{nullptr,lexer_abnormal::illegal_char};}string result;while(i!gen.size()gen[i]33gen[i]!127gen[i]!(gen[i]!,gen[i]!)){result.append(1,gen[i]);i;}return{make_sharedToken(Token(result)),lexer_abnormal::success};}}}shared_ptrTokenLex(conststringgen,string::size_typei){pairshared_ptrToken,lexer_abnormaltlexer_parse(gen,i);if(t.secondlexer_abnormal::illegal_char){coutERROR:下标i存在非法的字符endl;exit(-1);}if(t.secondlexer_abnormal::end){coutERROR:字符串已扫描完毕,但解析过程尚未结束,不完整的表达式endl;exit(-1);}returnt.first;}boolparseSubList(conststringgen,string::size_typei){string::size_type starti;while(true){string::size_type posi;shared_ptrTokencurLex(gen,i);if(cur-typetoken_type::id){shared_ptrTokennextLex(gen,i);if(next-typetoken_type::left_bracket){if(parseSubList(gen,i)false)returnfalse;shared_ptrTokenafterLex(gen,i);if(after-typetoken_type::right_bracket)returntrue;if(after-typetoken_type::left_bracket||after-typetoken_type::id){coutERROR:从下标pos开始的子表后遇见意外的结尾,预期为逗号或右括号endl;returnfalse;}}elseif(next-typetoken_type::right_bracket){returntrue;}}elseif(cur-typetoken_type::left_bracket){coutERROR:下标pos处的子表开头缺少标识符endl;returnfalse;}elseif(cur-typetoken_type::right_bracket){if(start!pos){coutERROR:缺少从下标start开头的子表最后一个表项endl;returnfalse;}returntrue;}else{coutERROR:下标pos处的逗号分隔符前缺少表项endl;returnfalse;}}}boolparseGen(conststringgen,string::size_typei){shared_ptrTokencurLex(gen,i);if(cur-type!token_type::id||(curLex(gen,i))-type!token_type::left_bracket){coutERROR:无效的广义表开头endl;returnfalse;}if(parseSubList(gen,i)){if(igen.size()){coutERROR:最外层广义表结尾后存在意外字符endl;returnfalse;}returntrue;}returnfalse;}intmain(){string genf()k();string::size_type i0;if(parseGen(gen,i)){cout解析成功,广义表表达式正确!endl;}else{coutERROR:语法错误!endl;}return0;}