下载文档原格式
第四章自顶向下语法分析方法语法分析是编译过程的核心部分。
语法分析的任务是：按照文法，从源程序符号串中识别出各类语法成份，同时进行语法检查，为语义分析和代码生成作准备。
执行语法分析任务的程序称为分析程序。
也称为语法分析器，它是编译程序的主要子程序之一。
在第二章中我们已经介绍过。
通过语法分析可建立起相应的语法树。
按语法树的建立方法，我们将语法分析方法分成两大类，即自顶向下分析和自底向上分析。
下面，我们先介绍自顶向下分析。
本章重点：自顶向下分析、LL（1）分析第一节自顶向下分析方法一、带回溯的自顶向下分析算法这是自顶向下分析的一般方法，即对任一输入符号串，试图用一切可能的方法，从识别符号出发，根据文法自上而下地为输入串建立一棵语法树。
下面用一个简单例子来说明这种过程：假定有文法G[S]：S→cＡdA→ab|a 以及输入串w=cad为了自上而下地构造w的语法树，我们首先按文法的识别符号产生根结点S，并让指示器IP指c的规则（此处左部为S的规则仅有一条）（ a）（b）（c）图3-1-1图3-1-1a。
我们希望用S的子结从左至右匹配整个输入串w。
首先，此树的最左子结是终结符c为标志的子结，它和输入串的第一个符号相匹配。
于是，我们就把IP调整为指向下一输入符号a，并让第二个子结A去进行匹配，非终结符A有二个选择，我们试着用它的第一个选择去匹配输入串，于是把语法树发展为图3-1-1b。
子树A的最左子结和IP所指的符号相符，然后我们再把IP调为指向下一符号d并让A的第二个子结进入工作。
但A 的第二个子结为终结符号b，与IP当前指的符号d不一致。
因此，A宣告失败。
这意味着A的第一个选择此刻不适用于构造w的语法树。
这时，我们应该回头（回溯）看A是否还有别的选择。
为了实现回溯，我们一方面应把A的第一个选择所生长的子树注销掉；另一方面，应把IP恢复为进入A时的原值，也就是让它重新指向第二输入符号a。
现在我们试探用A的第二个选择，即考虑生成图3-1-1c的语法树。
编译原理-⾃顶向下的语法分析1.代替部分由公因⼦就会出现回溯。
2.LL(1)⽂法（1）FIREST集这样说从⽂法的左部找右部相关的⾮终结符号。
若 X->BC..D,则将First（B）所有元素（除了ε）加⼊First（A），然后检测First（B），若First（B）中不存在ε,则停⽌，若存在则向B的后⾯查看，将First（C）中所有元素（除了ε）加⼊First（A），然后再检测First（C）中是否有ε...直到最后，若D之前的所有⾮终结符的First集中都含有ε,则检测到D时，将First（D）也加⼊First（A），若First（D）中含有ε,则将ε加⼊First（A）。
（2）FOLLOW集：记住是从⽂法的右部去找的。
1）S是开始符号,将#放到follow（S）中. 2）存在A→αBβ（且β！=ε），那么first（β）中除ε之外的所有符号都在follow（B）中。
3）存在A→αB或A→αBβ（且first（β）包含ε），那么follow（A）中的所有符号都在follow（B）中。
（注意都没有说α⼀定存在。
）（3）SELECT集对于产⽣式A—>α。
集合select（A—>α）定义如下：1. 若α不能推出ε，则select（A—>α） = first（α）。
2. 若α能推出ε，则select（A—>α）= first（α）∪ follow(A)。
（4）如何判断⼀个⽂法是不是LL（1）⽂法：第⼀消除左递归，先消除去直接左递归，然后看是否有相同最左公因⼦的，提取出来。
第⼆分别求出每个推导的SELECT集，同⼀左部的求SELECT集的交集，所有的这种交集为空的话就是LL(1)⽂法，否则不是。
3.递归下降分析法：只针对LL(1)⽂法的，所以没有左递归。
简单的来说就是为每个⾮终结符号编写⼀个处理程序，⽽处理程序的代码结构是由相应的⾮终结符号的规则右部所决定。
p68.4.预测分析表的构造:p74。
实验报告实验项目列表一、实验名称自顶向下语法分析方法的实现二、实验目的1.掌握自顶向下语法分析的方法；2.运用编程的手段实现自顶向下语法分析。
三、实验内容和要求四、实验环境1．硬件环境：PC机2．软件环境：Windows操作系统，VC++集成开发环境五、算法设计思想六、主要问题与解决方法七、实验结果以下是程序的用户运行界面截图：八、体会、质疑、建议九、源代码#include<fstream>#include<sstream>#include<iostream>#include<vector>#include<string>#include<windows.h>#include<iterator>#include<algorithm>#include<stdlib.h>#define M 20using namespace std;void gotoxy(int x,int y){COORD coord;coord.X=x;coord.Y=y;SetConsoleCursorPosition( GetStdHandle( STD_OUTPUT_HANDLE ), coord );}class table{public:void read();friend class an_process;string find_str(char row,char col);private:string matrix[M][M];char start;vector<string> vec_row;vector<string> vec_col;};class sentence{public:void read_in();friend class an_process;private:string str_input;};class an_process{public:void analyse(const table LL1_table,const sentence input);void write_result();void print2(int x,int y);private:vector<int> step;vector<vector<char> > stack_note;vector<string> remain;vector<string> production;};void table::read(){string a,str;char x,y;int linenum = 0;char line[1024]={0};ifstream infile("table1.txt");if(!infile){cerr<<"错误！无法存储用户数据！\n";}while(infile.getline(line,sizeof(line))){stringstream word(line);if(linenum>1){if(word>>x&&word>>y&&word>>str){matrix[x-48][y-48]=str;/*cout<<x<<" ";cout<<y<<" ";cout<<matrix[x-48][y-48]<<" ";*/}}while(word>>a&&linenum<2){if(linenum==0){vec_col.push_back(a);/*cout<<a<<" ";*/}else if(linenum==1){vec_row.push_back(a);/* cout<<a<<" ";*/}}/*cout<<endl;*/linenum++;}start=vec_col[0][0];/* for(int icnt=0;icnt<vec_col.size();icnt++){cout<<vec_col[icnt]<<" ";}*/}string table::find_str(char row,char col){for(int x=0;x<vec_col.size();x++)for(int y=0;y<vec_row.size();y++){if(row==vec_col[x][0]&&col==vec_row[y][0]){return matrix[x+1][y+1];}}return"";}void an_process::analyse(table LL1_table,sentence input) {int icnt=0,jcnt=0,kcnt;string ac,prod="",re="";vector<char> stack;char Now_word=input.str_input[icnt];char NOW_state=LL1_table.start;string::const_iterator Eiter;string::const_iterator Biter;stack.push_back('#');stack.push_back(NOW_state);for(;icnt<input.str_input.size();){step.push_back(++jcnt);stack_note.push_back(stack);for(kcnt=icnt;kcnt<input.str_input.size();kcnt++){re=re+input.str_input[kcnt];}re=re+"#";remain.push_back(re);re.erase();Now_word=input.str_input[icnt];NOW_state=stack.back();if(NOW_state==Now_word){stack.erase(stack.end()-1);icnt++;production.push_back("(匹配)");}else{ac=LL1_table.find_str(NOW_state,Now_word);Biter=ac.begin();Biter--;Eiter=ac.end();Eiter--;if(ac=="ε"){prod=prod+NOW_state;prod=prod+"→";prod=prod+"ε";stack.erase(stack.end()-1);production.push_back(prod);prod.erase();}else if(ac!=""){stack.erase(stack.end()-1);prod.empty();prod=prod+NOW_state;prod=prod+"→"+ac;production.push_back(prod);prod.erase();for(;Eiter!=Biter;Eiter--){stack.push_back(*Eiter);}}else{cout<<"分析失败\n";exit(0);}}}if(stack.size()!=1||stack.back()!='#'){cout<<"分析失败\n";exit(0);}}void an_process::write_result(){step.push_back(step.back()+1);vector<char> a;a.push_back('#');stack_note.push_back(a);remain.push_back("#");production.push_back("接受");gotoxy(27,1);cout<<"输入串"<<'"'<<remain[0];cout<<"\b"<<'"'<<"的分析过程"<<endl<<endl;print2(step.size()+1,4);vector<int>::const_iterator iter1=step.begin();vector<vector<char> >::const_iterator iter2=stack_note.begin(); vector<string>::const_iterator iter3=remain.begin();vector<string>::const_iterator iter4=production.begin(); gotoxy(8,4);cout<<"步骤";gotoxy(27,4);cout<<"分析栈";gotoxy(44,4);cout<<"剩余输入串";gotoxy(63,4);cout<<"所用产生式";for(int xy=0;iter1!=step.end();iter1++){gotoxy(9,xy+6);cout<<(*iter1);xy=xy+2;}for(xy=0;iter2!=stack_note.end();iter2++) {gotoxy(27,xy+6);for(int icnt=0;icnt<(*iter2).size();icnt++) {cout<<(*iter2)[icnt];}xy=xy+2;}for(xy=0;iter3!=remain.end();iter3++){gotoxy(44,xy+6);cout<<(*iter3);xy=xy+2;}for(xy=0;iter4!=production.end();iter4++){gotoxy(63,xy+6);cout<<(*iter4);xy=xy+2;}cout<<endl<<endl;}void an_process::print2(int x,int y)//简易画线代码，呵呵,画行直线{int i,j;for(int icnt=0;icnt<y-1;icnt++){for(i=0;i<37/y;i++)printf("─");printf("┬");}for(i=0;i<37/y;i++)printf("─");putchar(10);for(icnt=0;icnt<y-1;icnt++) {for(i=0;i<37/y;i++)printf(" ");printf("│");}putchar(10);for(j=0;j<x-1;j++)//画5行直线{for(icnt=0;icnt<y-1;icnt++){for(i=0;i<37/y;i++)printf("─");printf("┼");}for(i=0;i<37/y;i++)printf("─");putchar(10);for(icnt=0;icnt<y-1;icnt++){for(i=0;i<37/y;i++)printf(" ");printf("│");}putchar(10);}for(icnt=0;icnt<y-1;icnt++) {for(i=0;i<37/y;i++)printf("─");printf("┴");}for(i=0;i<37/y;i++)printf("─");putchar(10);}void sentence::read_in(){cout<<"请输入需要分析的句子：\n";cin>>str_input;system("cls");}void main(){table LL1_table;sentence input;an_process A;input.read_in();LL1_table.read();A.analyse(LL1_table,input);A.write_result();}。
