实验目的：
针对与给定上下文无关的语法，编制递归下降分析程序。
分析：
递归下降语法分析的前提是保证ll(1)语法递归下降的思路是暴力dfs。 各程序直接不管三七二十一进行检索，尽可能继续检索。 如果找不到，return就会搜索其他东西。
让我们来看看语法：
: lexp-atom|list: atom-number|identifier: list-(lexp-seq ): lexp-seq-lexp-seq lexp|lexp|lexp明显向左递归
: lexp-atom|list: atom-number|identifier: list-(lexp-seq ):lexp-seq-lexp-seq )3360lexp-seq )
# include stdio.h # includecstdlib # include string.h # define maxn 1000 usingnamespacestd； int idx=0； char str[maxn]； int lexp (； void atom (； 语音列表(； void lexp_sep (； void lexp_sep_(int lexp () if ) (str[idx]='0'str[idx]='9' )|(str[idx]='a'str[idx]='z ' 返回1； }elseif(str[idx]==' (' ) printf ) ) lexp-list(n )； list (； 返回1； }else return 0； }void atom () if ) str[idx]='0'str[idx]='9' ) (printf ) atom-number ) )； idx； } else if (str [ idx ]=' a ' str [ idx ]=' z ' ) printf(atom-identifier(n ) )； idx； }}void list () if ) str[idx]！=' ' ' ) {printf('list ) ) error！ n '； exit(-1； }printf(list-(lexp_seq ) ) n )； idx； lexp_sep (； if(str[idx]！=') ' ) {printf('list ) )错误！ n '； exit(-1； (idx； }void lexp_sep () printf (' lexp _ sep-lexplexp _ seq 'n ' )； lexp (； lexp_sep_ (； }void {lexp_sep_ () if ) lexp )==1) ) lexp_sep_ )； }else return； }intmain(intargc，char* argv[] ) scanf ) ' %s '，str )； intlen=strlen(str； str[len ]='$ '； str[len]=' '； lexp (； if(str[idx]=='$ ' ) printf(accept！ n '； else打印(wrong answer！ n '； 返回0； }测试数据：
(a ) b )2) c )输出结果：
lexp-listlist-(lexp_seq ) lexp _ sep-lexp _ seq ' lexp-atom atom-identifierlexp-list-(lexp _ seq ) lexp ) 您可以看到p-atom atom-identifierlexp-list list-(lexp _ seq ) lexp_sep-lexplexp_seq '匹配成功，但希望输出此语法树
仔细想想，我们发现直接递归下降分析无法生成和输出语法树。 虽然匹配正确的结果。
这是因为，因为只有判断递归有效才能输出，所以在决定是否进入时，无法保证输出这次是否进入。 可以通过堆栈简单地判定一次递归有效，但不能多次。因此需要构建first集合和follow集合来构建预测分析表。
当然，cyc通过在各token中添加括号直接进行dfs检索，保证了正确的输出。 在这里贴膜
# include iostream # include stack # include algorithm # includestringusingnamespacestd； stackstringinput； stackstringst； OOLnumber(conststrings ) for ) intI=0； I(int ) s.size )； I ) if (！ (s[i]='0's[i]='9' ) )返回假； }返回真； }boolidentifier(conststrings ) for ) intI=0； I(int ) s.size )； I ) if (！ (s(I )='a's ) I )='z ) )返回假； }返回真； (}int main ) ) input.push ) ' $ '； 字符串s； cins； for(intI=(int ) s.size ) )-1； i=0； I---{字符串tmp； tmp=s[i]； input.push(tmp； }ST.push('$ '； ST.push(lexp )； while(ST.size(1) { string now=st.top )； st.pop (； string cnt=input.top (； if(now=='lexp'(if ) CNT==' ) ) { cout'lexp - list'endl； ST.push(list )； }elseif(number(CNT ) ) { cout'lexp - atom'endl； ST.push(atom )； } else if (标识符(CNT ) ) { cout'lexp - atom'endl； ST.push(atom )； } else{ cout'lexp ()-next error！' endl； exit(-1； }elseif(now=='atom ' ) if (number ) CNT ) ) { cout'atom - number'endl； input.pop (； } else if (标识符(CNT ) ) { cout'atom - identifier'endl； input.pop (； } else{ cout'atom ()-next error！' endl； exit(-1； }elseif(now=='list ' ) if (CNT==' ) ) ) cout'list-(lexp-seq ) ) endl； input.pop (； st.push () ) ) )； ST.push(lexp-seq )； } else{ cout'list ()- next errpr！' endl； exit(-1； }elseif(now=='lexp-seq ' ) if ) CNT==' (((编号) CNT) cout'lexp-seq-leq ) )为ST . ST.push(lexp )； }else{cout'lexp-seq(-nexterror！' endl； exit(-1； }elseif(now=='lexp-seq ' ) if ) CNT==' ) ((|number(CNT ) ) cout'lexp-seq ) )为ST . ST.push(lexp )； } else{ cout'lexp-seq' - NULL'endl； }elseif(now==' ) (cnt==' ) ) { input.pop； } else{ cout'Wrong answer'endl； exit(-1； } } cout'Accept！ ' endl； }输入：
(a ) b )2) c )通过python生成图像：