编译原理-递归子程序 c++源码

编译原理-递归子程序 C++ 源码 本资源摘要信息主要介绍了编译原理中的递归子程序设计，通过实验掌握将非 LL(1) 文法改写为 LL(1) 文法的方法，了解递归下降预测分析的原理和过程，以及可能存在的回溯问题。 一、实验目的 通过本实验，掌握将非 LL(1) 文法改写为 LL(1) 文法的方法；了解递归下降预测分析的原理和过程，以及可能存在的回溯问题。 二、实验内容及要求 递归下降分析法是确定的自上而下的分析法，这种分析法要求文法是 LL(1) 文法。它的基本思想是，对文法中的每一个非终结符编写一个函数，每个函数的功能是识别由该非终结符所表示的语法成分。 1、给定文法：S→（T）|^|a T→T，S|S 由于该文法不是 LL(1) 文法，所以需要将其改写为能用递归下降子程序分析的 LL(1) 文法。对该文法可以通过消除左递归，并反复提取公共左因子对其进行等价变换，将其改写为 LL(1) 文法。经过改写后的文法为：S→（T）|^|a T1→ST1 T1→, ST1|ε 2、编写递归下降子程序，并判断某个句子是否符合该文法。 三、实验程序设计说明 1．实验方案设计 scaner( )函数：从文件中依次读字符 S( )函数：判断表达式是否满足 S→（T）|^|a T( )函数：判断表达式是否满足 T1→ST1 T1( )函数：判断表达式是否满足 →,ST1|ε 2．程序源代码 #include "stdio.h" void scaner(); void error(); void S(); void T(); void T1(); char sym; char str[50]; int j=0; void S(){ if(sym=='a'||sym=='^') scaner(); else if(sym=='('){ scaner(); T(); if(sym==')') scaner(); else error(); }else error(); } void T(){ S(); T1(); } void T1(){ if(sym==','){ scaner(); S(); T1(); }else if(sym!=')') error(); } void error(){ printf("error"); } void scaner(){ sym=str[j]; j++; } int main(){ printf("输入句子以($)结束:"); char ch; int i=0; while(1){ scanf("%c",&ch); str[i++]=ch; if(ch=='$') break; } scaner(); S(); if(sym=='$') printf("success"); else printf("fail"); return 0; } 3．程序测试结果 通过编译和运行该程序，可以测试输入的句子是否符合该文法，输出结果为“success”或“fail”。 四、结论 通过本实验，我们掌握了将非 LL(1) 文法改写为 LL(1) 文法的方法，了解了递归下降预测分析的原理和过程，以及可能存在的回溯问题，并编写了递归下降子程序来判断某个句子是否符合该文法。